最小生成树算法
Ø 问题描述
设G=(V,E)是一个无向连通带权图，E中每条边(v,w)的权为c(v,w)。如果G的一个子图G`是一棵包含G的所有顶点的书，则称G`为G的生成树。生成树上各边权的总和称为该生成树的耗费，在G的所有生成树中，耗费最小的生成树就称为G的最小生成树。给定一个无向连通带权图，构造一个最小生成树。
Ø 设计思想
利用Prim算法求最小生成树，Prim算法是利用贪心策略设计的算法。设G=(V,E)是一个连通带权图，V={1，2，…，n}。构造G的一棵最小生成树的Prim算法的基本思想是：首先置U={1},然后，只要U是V的真子集，就做如下的贪心选择：选取满足条件i∈U,j∈V-U,且使c(i,j)达到最小的边(i,j),并将顶点j添加到U中。这个过程一致进行到U=V时为止。在这个过程中选取到的所有边恰好构成G的一棵最小生成树。
Ø 时间复杂度
Prim算法的Pascal语言描述如下：
Procedure PRIM(c:array[1..n,1..n] of real);
Var
lowcost:array[1..n] of real;
closest:array[1..n] of integer;
i,j,k,min,integer;
begin
(1) for i:=2 to n do
(2) begin{初始化，此时U只含有顶点1}
(3) lowcost[i]:=c[1,i];
(4) Closest[i]:=1;
(5) end;
(6) for i:=2 to n do
(7) begin {寻找顶点分别在V-U与U中边权最小的边}
(8) min:=lowcost[i];
(9) j:=i;
(10) For k:=2 to n do
(11) If lowcost[k]<min then
(12) Begin
(13) Min:=lowcost[k];
(14) j:=k;
(15) End;
(16) print(j,closest[j]);{输出找到的边}
(17) Lowcost[j]:=∞;{将j添加到U}
(18) For k:=2 to n do {调整lowcost和closest}
(19) if(c[j,k]<lowcost[k])and(lowcost[k]< ∞)then
(20) Begin
(21) Lowcost[k]:=c[j,k];
(22) Closest[k]:=j;
(23) End
(24) End
(25)End;{PRIM}
上述过程中第(6)~(24)行的for循环要执行n-1次，每次执行时，第(10)~(15)行和第(18)~(23)行的for循环都要O(n)时间，所以Prim算法所需的计算时间为O(n
)。
Ø 实验源代码
图定义头文件Graph.h：
const int MaxV=10;//最多顶点数
const int MaxValue=99;//最大权值
//定义边集数组中的元素类型
struct RCW
{int row,col;
int weight;
};
class adjMList
{
private:
int numE;//当前边数
int GA[MaxV][MaxV];//定义邻接矩阵
public:
//构造函数,初始化图的邻接矩阵与边集数组
adjMList(RCW GE[],int n,int e);
//建立无向带权图的邻接矩阵
void CreateMatrix(int n,int &e,RCW r[]);
//输出边集数组中的每条边
void OutputEdgeSet(RCW ge[],int e);
//根据图的邻接矩阵生成图的边集数组
void ChangeEdgeSet(RCW GE[],int n,int e);
//按升序排列图的边集数组
void SortEdgeSet(RCW GE[],int e);
//利用普里姆算法从顶点v0出发求出用邻接矩阵GA表
//示的图的最小生成树,最小生成树的边集存于数组CT中
void Prim(RCW CT[],int n);
//检查输入的边序号是否越界,若越界则重输
void Check(int n, int& i, int& j);
};
图实现文件Graph.cpp
//20052381 杨松 Graph.cpp
#include"Graph.h"
//构造函数,初始化图的邻接矩阵与边集数组
adjMList::adjMList(RCW GE[],int n,int e)
{int i,j;
for(i=0; i<n; i++)
for(j=0; j<n; j++)
if(i==j) GA[i][j]=0;
else GA[i][j]=MaxValue;
for(i=0;i<e;i++) GE[i].weight=0;
numE=0;
}
//输出边集数组中的每条边
void adjMList::OutputEdgeSet(RCW ge[],int e)
{int i,k=0;
cout<<"{";
for(i=0; i<=e-2; i++)
if(ge[i].weight>0){k++;
cout<<'('<<ge[i].row<<','<<ge[i].col;
cout<<','<<ge[i].weight<<") ";
if(k%5==0) cout<<endl;}
if(e>0&&ge[i].weight>0) {
cout<<'('<<ge[e-1].row<<','<<ge[e-1].col;
cout<<','<<ge[e-1].weight<<')';}
cout<<'}'<<endl;
}
//建立无向带权图的邻接矩阵
void adjMList::CreateMatrix(int n,int &e,RCW r[])
{int i,j,k=0,w;
cout<<"依次输入无向带权图的每条边的起点和终点"<<endl;
cout<<"序号及权值!直到输入权值为0的边为止!"<<endl;
do {i=r[k].row;j=r[k].col;w=r[k].weight;
//cin>>i>>j>>w;
Check(n,i,j);
if(k==e-1) break;
GA[i][j]=GA[j][i]=w;k++;
}while(1);
numE=e=k;
cout<<"邻接矩阵:\n";
for(i=0;i<n;i++)
{for(j=0;j<n;j++)
cout<<setw(4)<<GA[i][j];
cout<<endl;}
}
//检查输入的边序号是否越界,若越界则重输
void adjMList::Check(int n, int& i, int& j)
{while(1) {
if(i<0 || i>=n ||j<0 || j>=n)
cout<<"输入有误,请重输!";
else return;
cin>>i>>j;}
}
//根据图的邻接矩阵生成图的边集数组
void adjMList::ChangeEdgeSet(RCW GE[],int n,int e)
{//假定只考虑无向图的情况
int i,j,k=0;
for(i=0; i<n; i++)
for(j=i+1; j<n; j++)
if(GA[i][j]!=0 && GA[i][j]!=MaxValue)
{if(k==e) {cout<<"数组GE下标越界!\n";
exit(1);}
GE[k].row=i;
GE[k].col=j;
GE[k].weight=GA[i][j];
k++;
}
}
//按升序排列图的边集数组
void adjMList::SortEdgeSet(RCW GE[],int e)
{int i,j;
RCW x;
for(i=1; i<=e-1; i++)
{x=GE[i];
for(j=i-1; j>=0; j--)
if(x.weight<GE[j].weight) GE[j+1]=GE[j];
else break;
GE[j+1]=x;
}
}
//利用普里姆算法从顶点v0出发求出用邻接矩阵GA表示
//的图的最小生成树,最小生成树的边集存于数组CT中
void adjMList::Prim(RCW CT[],int n)
{int i,j, k, min, t, m, w;
//给CT赋初值，对应为v0依次到其余各顶点的边
for(i=0; i<n-1; i++)
{CT[i].row=0;
CT[i].col=i+1;
CT[i].weight=GA[0][i+1];}
//进行n-1次循环，每次求出最小生成树中的第k条边
for(k=1; k<n; k++)
{//从CT[k-1]~CT[n-2]中查找最短边CT[m]
min=MaxValue;
m=k-1;
for(j=k-1; j<n-1; j++)
if(CT[j].weight<min) {
min=CT[j].weight;
m=j;}
//把最短边对调到第k-1下标位置
RCW temp=CT[k-1];
CT[k-1]=CT[m];
CT[m]=temp;
//把新并入最小生成树T中的顶点序号赋给j
j=CT[k-1].col;
//修改有关边，使T中到T外的每一个顶点各保持
//一条到目前为止最短的边
for(i=k; i<n-1; i++) {
t=CT[i].col;
w=GA[j][t];
if(w<CT[i].weight) {
CT[i].weight=w;
CT[i].row=j;
}}}}
主程序文件 Test.cpp：
//图的相关运算的测试graph2M.cpp
#include<iostream.h>
#include<iomanip.h>
#include<stdlib.h>
#include "Graph.cpp"
void main()
{
RCW rcw[20]={{0,1,50},{1,0,50},{0,2,60},{2,0,60},
{1,3,65},{3,1,65},{1,4,40},{4,1,40},{2,3,52},
{3,2,52},{2,6,45},{6,2,45},{3,4,50},{4,3,50},
{3,5,30},{5,3,30},{3,6,42},{6,3,42},{4,5,70},{5,4,70}};
int n,k;//定义图的点数及边数等
cout<<"输入图的点数n=";cin>>n;
cout<<"输入图的边数k=";cin>>k;
static RCW AE[30],BE[30];//定义边集数组
adjMList A(AE,n,k);
A.CreateMatrix(n,k,rcw);
cout<<"输出边集数组中的每条边:\n";
A.ChangeEdgeSet(AE,n,k);
A.OutputEdgeSet(AE,k);
cout<<"输出按升序排列的图的边集数组:\n";
A.SortEdgeSet(AE,k);
A.OutputEdgeSet(AE,k);
A.Prim(BE,n);
cout<<"输出最小生成树的边集数组:\n";
A.OutputEdgeSet(BE,k);
cin.get();cin.get();}
Ø 实验数据
在主程序中直接构造图的边表如下，
{0,1,50},{1,0,50},{0,2,60},{2,0,60},
{1,3,65},{3,1,65},{1,4,40},{4,1,40},{2,3,52},
{3,2,52},{2,6,45},{6,2,45},{3,4,50},{4,3,50},
{3,5,30},{5,3,30},{3,6,42},{6,3,42},{4,5,70},{5,4,70}
共7个顶点，10条边
Ø 实验结果
第二篇：最小生成树的Kruskal算法实验报告
大连民族学院
计算机科学与工程学院实验报告
实验题目： 最小生成树的Kruskal算法
课程名称： 离散数学
实验类型：□演示性 □验证性 □操作性 ■设计性 □综合性
专业：软件工程 班级：111 学生姓名：xx 学号：xx
实验日期：20##年12月6-28日 实验地点：金石滩校区机房201
实验学时： 10学时 实验成绩：
指导教师： 焉德军 姜楠 20##年 12月28 日
[实验原理]
设所给定无向连通加权图具有n个结点，m条边，首先，将各条边的权按从小到大的顺序排序。然后依次将这些边按所给图的结构放到生成树中去。如果在放置某一条边时，使得生成树形成回路，则删除这条边。这样，直至生成树具有n-1条边时，我们所得到的就是一棵最小生成树。
[实验内容]
给定无向连通加权图，编程设计求出其一棵最小生成树。
[实验目的]
通过算法设计并编程实现求出给定无向连通加权图的一棵最小生成树，加深学生对求最小生成树的Kruskal算法的理解。
[实验步骤]
（1） 边依小到大顺序得l1，l2，…，lm。
（2） 置初值：
S，0
i，1j。
（3） 若i=n-1，则转（6）。
（4） 若生成树边集S并入一条新的边lj之后产生的回路，则j+1j，并转（4）。
（5） 否则，i+1i；ljS（i）；j+1j，转（3）。
（6） 输出最小生成树S。
（7） 结束。
具体程序的C++实现如下：
#include <iostream>
using namespace std;
const int MaxVertex = 20;
const int MaxEdge = 100;
const int MaxSize = 100;
struct EdgeType
{
int from;
int to;
int weight;
};
struct EdgeGraph
{
char vertex[MaxVertex];
EdgeType edge[MaxEdge];
int vertexNum;
int edgeNum;
};
int FindRoot(int parent[], int v);
void InputInfo();
void Kruskal(EdgeGraph G)
{
int vex1,vex2,f,t;
int i,num;
int parent[MaxVertex];
for(i=0; i<G.vertexNum; i++)
{
parent[i] = -1;
}
for(num =0,i=0; i<G.edgeNum; i++)
{
vex1 = FindRoot(parent, G.edge[i].from);
vex2 = FindRoot(parent, G.edge[i].to);
if(vex1 != vex2)
{
cout << "(" << G.edge[i].from << "," << G.edge[i].to << ")" << endl;
f = G.edge[i].from;
t = G.edge[i].to;
cout << "(" << G.vertex[f] << "," << G.vertex[t] << ")" << " Weight: " << G.edge[i].weight << endl;
cout << endl;
parent[vex2] = vex1;
num++;
if(num == G.vertexNum-1) return;
}
}
return;
}
int FindRoot(int parent[], int v)
{
int t;
t = v;
if(parent[t] > -1)
{
t = parent[t];
}
return t;
}
void InputInfo()
{
EdgeGraph G;
cout << "Please input vertexNum , edgeNum: " << endl;
cin >> G.vertexNum >> G.edgeNum;
cout << "Please input the information of edges:" << endl;
for(int i=0; i<G.vertexNum; i++)
{
cin >> G.vertex[i];
}
cout << "Please input this edge attaches two vertices subscript and its weight" << endl;
for(int j=0; j<G.edgeNum; j++)
{
cin >> G.edge[j].from >> G.edge[j].to >> G.edge[j].weight;
}
Kruskal(G);
}
int main()
{
InputInfo();
system("pause");
return 0;
}
实验过程中遇到的问题及解决过程
比如不知道如何存储边集数组，以及比知道如何声明一些变量，函数和怎样去调用Kruskal函数……
解决：通过设置结构体EdgeType与结构体EdgeGraph的联合来存储边集，因为在刚开始我在主函数中用EdgeGraph声明变量G，来作为形参去调用Kruskal(G)，编译时就会警告未被初始化的G，的程序出错，后来我将Kruskal(G)在InputInfo()
中调用，因为InputInfo()函数中声明了变量G，并使得G初始化，从而是的程序能正常运行。
测试的图与预期生成的最小树
[实验记录]
实验总结，感想
通过这次的上机实验，加深了我对课本上的理论知识的认识与理解，然我真实的体验到了从研究问题到解决问题的探索中产生的乐趣，并且体会到问题解决的成就感，虽然在上机调试的时候产生了很多的错误，但经过自己查阅资料，请教同学老师而将问题一一的解决让我体会到学习所带来的乐趣，我希望今后能又更多的理论与实践相结合的课程设计作业，而不是单一的理论的学习。