|
最小生成树
什么是最小生成树求法Kruskal算法简述图例伪代码C语言代码时间复杂度分析
Prim算法简述图例伪代码C语言代码时间复杂度分析
完整代码
什么是最小生成树
在一个无向图中，连接每两个不同顶点的每一条边都有一个长度，叫做权，最小生成树就是在这个图中找到一棵树，这棵树可以把每一个点连接起来，同时保证权和是所有生成树中最小的。 讲的专业点就是这样： 
求法
计算最小生成树的办法最经典的有两个，Kruskal和Prim。Kruskal算法更好理解，但是实际上的的代码编写可能比Prim还要更复杂。
有空建议看看视频（点我），这个视频的动画演示非常清晰的展现了这两个算法的运算思路。
Kruskal算法
简述
对与一个图而言，每条边都有权，那么我们可以把所有的权列出来，然后从小到大排序。 同时把你纸上的图的所有边擦掉，然后依次选择最小的边，填回这张被擦掉边的图，也就是那一堆点中。 依次选择最小的边代回，如果在代回的时候发现这条边所属的两个点都分别有另外的边与之相连了，那么这个时候就不要强人所难，就不将这条边再放回去了，如果放回去的话就会在图中形成一个回路，无法构成树的条件。
这次感觉书上讲的比我的简洁 
图例
下面深色边则表示我所讲的所选择的边 
伪代码
这个伪代码相当抽象，但是主旨也就是这样 
C语言代码
typedef struct//邻接矩阵
{
int edges[MAXV][MAXV];
int n,e;
VertexType vexs[MAXV];
}MatGraph;
typedef struct//边信息
{
int u;
int v;
int w;
}Edge;
bool cmp(Edge a,Edge b)//排序条件
{
return a.w
for(j=0;j
E[k].u=i;
E[k].v=j;
E[k].w=g.edges[i][j];
k++;
}
}
}
sort(E,E+k,cmp); //从小到大排序
for(i=0;i
ul=E[j].u;vl=E[j].v; //两个端点
snl=vset[ul];
sn2=vset[vl];
if(snl!=sn2) //判断是否已经被连接了，没有则连接
{
printf("边(%d,%d)权为:%d\n",ul,vl,E[j].w );
k++;
for(i=0;i
int lowcost[MAXV]; //距离数组
int MIN; //记录最小距离
int closest[MAXV]; //连接点地址
int i,j,k; //k记录最小距离对应的连接点
for(i=0;i
MIN=INF;
for(j=0;j
MIN=lowcost[j];
k=j;
}
}
printf("边(%d,%d)权为:%d\n",closest[k],k,MIN);
lowcost[k]=0; //在输出之后将距离置0，判断为加入已选择的点集
for(j=0;j
lowcost[j]=g.edges[k][j];
closest[j]=k;
}
}
}
}
时间复杂度分析
困惑+n 智商-n 害怕.jpg 
完整代码
#include
#include
#include
using namespace std;
#define INF 32767
#define MAXV 100
typedef char InfoType;
typedef struct
{
int no;
InfoType info;
}VertexType;
typedef struct
{
int edges[MAXV][MAXV];
int n,e;
VertexType vexs[MAXV];
}MatGraph;
//创建图的邻接矩阵
void CreateMat(MatGraph &g,int A[MAXV][6],int n,int e)
{
int j,i;
g.n=n;g.e=e;
for(i=0;i
g.edges[i][j]=A[i][j];
}
}
}
//输出图的邻接矩阵
void DispMat(MatGraph g)
{
int i,j;
for(i=0;i
if(g.edges [i][j]!=INF)
printf("%4d",g.edges[i][j] );
else
printf("%4s","∞");
}
printf("\n");
}
}
void Prim(MatGraph g,int v )
{
int lowcost[MAXV]; //距离数组
int MIN; //记录最小距离
int closest[MAXV]; //连接点地址
int i,j,k; //k记录最小距离对应的连接点
for(i=0;i
MIN=INF;
for(j=0;j
MIN=lowcost[j];
k=j;
}
}
printf("边(%d,%d)权为:%d\n",closest[k],k,MIN);
lowcost[k]=0; //在输出之后将距离置0，判断为加入已选择的点集
for(j=0;j
lowcost[j]=g.edges[k][j];
closest[j]=k;
}
}
}
}
typedef struct
{
int u;
int v;
int w;
}Edge;
bool cmp(Edge a,Edge b)
{
return a.w
for(j=0;j
E[k].u=i;
E[k].v=j;
E[k].w=g.edges[i][j];
k++;
}
}
}
sort(E,E+k,cmp); //从小到大排序
for(i=0;i
ul=E[j].u;vl=E[j].v; //两个端点
snl=vset[ul];
sn2=vset[vl];
if(snl!=sn2) //判断是否已经被连接了，没有则连接
{
printf("边(%d,%d)权为:%d\n",ul,vl,E[j].w );
k++;
for(i=0;i
MatGraph g;
int A[MAXV][6]={
{0,5,8,7,INF,3},
{5,0,4,INF,INF,INF},
{8,4,0,5,INF,9},
{7,INF,5,0,5,6},
{INF,INF,INF,5,0,1},
{3,INF,9,6,1,0}
};
int n=6,e=10;
CreateMat(g,A,n,e);
printf("\n用Prim算法计算最小生成树：\n");
Prim(g,0);
printf("\n用Kruskal算法计算最小生成树：\n");
Kruskal(g);
}
|