登 录
/*用克鲁斯尔<span class='wp_keywordlink'><a href="http://www.xuebuyuan.com/category/%E7%AE%97%E6%B3%95" title="算法" target="_blank">算法</a></span>求最小生成树*/<br /> #include <iostream><br /> using namespace std;<br /> /*邻接矩阵的类型定义*/<br /> #define MAX 10000000<br /> #define MAX_VERTEX_NUM 20<br /> typedef struct<br /> {<br /> char vexs[MAX_VERTEX_NUM];//用一维数组存储顶点信息<br /> int edges[MAX_VERTEX_NUM][MAX_VERTEX_NUM];//用二维数组充当矩阵，来存储顶点边的信息<br /> int vexnum,edgenum;//顶点树和边数<br /> }MGraph;<br /> /*构造无向联通网的邻接矩阵*/<br /> void CreateUDN_AM(MGraph &G,int n,int e)<br /> {<br /> G.vexnum=n;<br /> G.edgenum=e;</p> <p> int i,j,k;<br /> for(i=0;i<n;i++)<br /> cin>>G.vexs[i];//输入顶点信息<br /> for(i=0;i<n;i++)<br /> for(j=0;j<n;j++)<br /> G.edges[i][j]=MAX;//将矩阵初始化为无穷大<br /> for(k=0;k<e;k++)<br /> {<br /> cin>>i>>j;<br /> cin>>G.edges[i][j];//这里只用输入对称的边就行，也就是输入下矩阵或是上矩阵<br /> G.edges[j][i]=G.edges[i][j];<br /> }<br /> }<br /> //边表结点类型的定义<br /> typedef struct<br /> {<br /> int begin,end;//边的起点和终点<br /> int cost;//边上的权值<br /> }EDGE;<br /> EDGE edge[MAX_VERTEX_NUM];<br /> //冒泡排序<br /> void bubble_sort(EDGE edge[],int n)<br /> {<br /> int i,j;<br /> int t;<br /> for(i=0;i<n;i++)<br /> for(j=i+1;j<n;j++)<br /> if(edge[i].cost>edge[j].cost)<br /> {<br /> t=edge[i].cost;<br /> edge[i].cost=edge[j].cost;<br /> edge[j].cost=t;<br /> t=edge[i].begin;<br /> edge[i].begin=edge[j].begin;<br /> edge[j].begin=t;<br /> t=edge[i].end;<br /> edge[i].end=edge[j].end;<br /> edge[j].end=t;//将位置及权值都进行交换<br /> }<br /> }<br /> //找f这个元素所在的连通分量中的标记元素的位置<br /> int find(int forest[],int f)<br /> {<br /> while(forest[f]>0)<br /> f=forest[f];<br /> return f;<br /> }<br /> //求最小生成树<br /> void MiniSpanTree_Kruskal(MGraph &G)<br /> {<br /> int i,j,k=0;<br /> int LocationOfBegin,LocationOfEnd;<br /> int forest[MAX_VERTEX_NUM];<br /> for(i=0;i<G.vexnum;i++)<br /> for(j=i+1;j<G.vexnum;j++)<br /> if(G.edges[i][j]<MAX)<br /> {<br /> edge[k].begin=i;<br /> edge[k].end=j;<br /> edge[k].cost=G.edges[i][j];<br /> k++;<br /> }//将边及边的信息赋值到edge数组中<br /> bubble_sort(edge,G.edgenum);//对edge里的元素按权值进行由小到大进行排序<br /> for(i=0;i<G.edgenum;i++)<br /> forest[i]=0;//初始化每个顶点，将每个顶点看做一个连通分量，并且置标识为0<br /> for(i=0;i<G.edgenum;i++)<br /> {<br /> LocationOfBegin=find(forest,edge[i].begin);<br /> LocationOfEnd=find(forest,edge[i].end);//找该顶点所在连通分量的标记元素的位置<br /> if(LocationOfBegin!=LocationOfEnd)<br /> {//如果起点和终点所在的连通分量的标记元素的地址相同，说明起点和终点在同一个连通分量中<br /> forest[LocationOfBegin]=LocationOfEnd;//该句的作用是将两个连通分量连成一个连通分量<br /> cout<<edge[i].begin<<"-"<<edge[i].end<<":"<<edge[i].cost<<endl;<br /> }<br /> }</p> <p>}<br /> void main()<br /> {<br /> freopen("a.txt","r",stdin);<br /> MGraph G;<br /> CreateUDN_AM(G,6,9);<br /> MiniSpanTree_Kruskal(G);<br /> }<br />
抱歉!评论已关闭.