最小生成树问题,主要的解法有两种,一种是Prim算法,不优化的时候是O(n^2)的时间复杂度,一般在稠密图的时候考虑使用。另一种是Kruskal算法,使用幷查集使用的复杂度是O(eloge),一般在稀松图的时候比较有利,所以一般Prim算法采用邻接矩阵,Kruskal一般采用邻接表。
朴素的Prim算法(未使用堆优化)
思路是:closedge 记录各节点到当前生成树的距离(到这棵生成树的最短边)
visited 记录每个结点是否已经被访问
每次都未被访问的结点中选一条距离最短的结点,并入生成树,这其实可以看做树的生长
/*图中顶点的数目*/ const int vexnum = 4; /*图中表示不可达的长度*/ const float maxval = 65536; /*closedge辅助记录数组*/ struct{ int dest; float cost;}closedge[vexnum]; void prim(float G[][vexnum],int v) { /*初始化closedge数组*/ for(int i=0; i<vexnum; ++i) { closedge[i].dest = v; closedge[i].cost = G[v][i]; } /*初始化visited辅助数组*/ bool visited[vexnum]={}; visited[v] = true; /*n-1次选择最小边*/ for(int count=0; count<vexnum-1; ++count) { /*选择最小边*/ int min_node = -1; float min_cost = maxval; for(int i=0; i<vexnum; ++i) { if(!visited[i] && min_cost>closedge[i].cost) { min_cost = closedge[i].cost; min_node = i; } } /*更新visited数组*/ visited[min_node] = true; /*更新closedge数组*/ for(int i=0; i<vexnum; ++i) { if(!visited[i] && G[i][min_node]<closedge[i].cost) { closedge[i].dest = min_node; closedge[i].cost = G[i][min_node]; } } } }
上述算法,只能在无向图的时候给出正确答案,下面修正错误,给出正确算法:
const int maxnum = 100; /*顶点的数目 */ int vexnum = 0; const int maxval = 0x77777777; /*表示无穷的距离*/ float G[maxnum][maxnum]; /*邻接矩阵存储 */ struct ENode { int from; float cost; }closedge[maxnum]; /*生成树的存储*/ void prim(int v=0) { /*初始化辅助数组*/ for(int i=0; i<vexnum; ++i) { closedge[i].from = v; closedge[i].cost = G[v][i]; } bool visited[maxnum] = {}; visited[v] = true; for(int k=0; k<vexnum-1; ++k) { int min_node = -1; float min_cost = (float)maxval; for(int i=0; i<vexnum; ++i) if(!visited[i] && min_cost > closedge[i].cost) { min_node = i; min_cost = closedge[i].cost; } visited[min_node] = true; for(int i=0; i<vexnum; ++i) if(!visited[i] && G[min_node][i] < closedge[i].cost) { closedge[i].from = min_node; closedge[i].cost = G[min_node][i]; } } }
注意事项是输入矩阵前,需要先置矩阵内所有元素为无穷:
for(int i=0; i<n; ++i) for(int j=0; j<n; ++j) G[i][j] = maxval;
如果不置无穷则会出现错误。
Kruskal算法的思路更加简单,那就是在所有邻接到未访问点的边中,选择一条最短的,直到所有点都被访问。幷查集在Kruskal算法中的运用是经典的数据结构和算法的结合。
const int maxvex = 100; struct edge { int tail;/*存储每条边的起始结点*/ int head;/*存储每条边的目的结点*/ int cost;/*存储的每条边的权重*/ }; bool cmp(edge a,edge b){ return a.cost<b.cost; }/*用于排序边的函数*/ int findSet(int *p,int x)/*十分精巧的一种写法,一行代码完成幷查集的所有精髓*/ { return p[x]==x ? x: p[x] = findSet(p,p[x]);} void unionSet(int *p,int a,int b) { p[a]= b; } int kruskal(edge* G ,int edgnum, /*图中所有边*/ int* p ,int vexnum) /*结果中所有边数为vexnum-1,true表示G[i]在最小生成树中*/ { for(int i=0; i<vexnum; ++i) p[i] = i; /*初始化幷查集*/ sort( G,G+edgnum,cmp );/*排序所有边*/ /*在所有边中选出vexnum-1条边*/ int count = 0; int total =0; for(int i=0; i<edgnum &&count<vexnum; ++i) { /*对每条边,如果其头结点和尾结点不同一集合中*/ if( findSet( p,G[i].head )!= findSet(p,G[i].tail)) { p[G[i].head]=p[G[i].tail];/*顶点合并到同一集合*/ ++count; /*计数增加*/ total +=G[i].cost; /*生成树总权重增加*/ } } if(count<vexnum-1) total = 0;/*没能生成连通整个图的生成树*/ return total; } /*测试代码*/ int main() { int p[maxvex];/*幷查集存储的每个点的父节点*/ int m,n; while(cin>>n>>m)/*n为顶点数,m为边数*/ { edge *G = new edge[m]; for(int i=0;i<m;++i) { cin>>G[i].tail>>G[i].head>>G[i].cost;} int total = kruskal(G,m,p,n); if(total) cout<<total<<endl; else cout<<0<<endl; } return 0; }