1）普里姆算法
可取图中任意一个顶点v作为生成树的根，之后若要往生成树上添加顶点w，则在顶点v和顶点w之间必定存在一条边，并且
该边的权值在所有连通顶点v和w之间的边中取值最小。一般情况下，假设n个顶点分成两个集合：U（包含已落在生成树上
的结点）和V-U（尚未落在生成树上的顶点），则在所有连通U中顶点和V-U中顶点的边中选取权值最小的边。
例如：起始生成树上面就一个顶点。为了连通两个集合，在可选的边中，选择权值最小的。需要辅助数组，V-U中所有顶点。
具体实例如下图所示：求下图的最小生成树
我们以a点为起始点，此时的U集合={a}，V-U到U集合的路径有a-b=4,a-c=2,取最小的a-c，所以将c点添加到U集合中，U={a,c}。
此时，V-U到U集合的路径有b-a=4,b-c=3,取最小，更新b点到U集合的最短路径为3，此外还有c-d=5,c-h=5,所以，取V-U到Ｕ集
合的最小值为b-c=3，将b点添加到U集合中。U={a,c,b}。此时V-U到U集合存在以下点：c-d=5,c-h=5,b-d=5(与现有的c-d=5一样，
所以不更新，仍旧采用c-d)，b-e=9，取最小的，此时可以有两个选择，假设选择c-d，所以将d点添加到U集合中。U={a,c,b,d}。
此时V-U到U的路径，因为e-d=7<e-b=9,所以e点进行更新，更新为d-e=7;同理d-h=4<c-h=5，所以点h到U的路径更新为d-h=4。
新增加的路径为d-f和d-g。此时选择V-U到U集合的最短路径为d-h=4,所以将h添加到U集合，此时U={a,c,b,d,h}。依次不断选择
下一个距离U集合最短路径的点，并将其添加到U集合，直到将所以顶点添加完毕。实现过程如下图所示：
接下来的代码示例图:
代码如下:
1 #include "stdafx.h" 2 #include<iostream> 3 #include<string> 4 using namespace std; 5 typedef struct MGraph 6 { 7 string vexs[60]; //存放顶点 8 int arcs[100][100]; //存放邻接矩阵矩阵 9 int vexnum, arcum; //总顶点数以及总边数 10 }MGraph; 11 typedef struct Closedge 12 { 13 string adjvex; 14 int lowcost; //存放相关顶点间边的权值 15 }minside[100]; 16 17 int locateVex(MGraph G, string u) //找到则返回i，否则返回-1 18 { 19 for (int i = 0; i < G.vexnum; i++) 20 if (G.vexs[i] == u) 21 return i; 22 return -1; 23 } 24 25 void CreateGraphUDG(MGraph &G) //构造无向图 26 { 27 string v1, v2; //两个顶点信息 28 int w; //两顶点间边的权值 29 int i, j, k; 30 cout << "请输入顶点数和边数:"; 31 cin >> G.vexnum >> G.arcum; 32 33 cout << "请输入顶点:"; 34 for (i = 0; i < G.vexnum; i++) 35 cin >> G.vexs[i]; 36 37 for (i = 0; i < G.vexnum; i++) //先将邻接矩阵中所有元素都设为无穷大，这里默认10000为无穷大 38 for (j = 0; j < G.vexnum; j++) 39 G.arcs[i][j] = 10000; 40 41 cout << "请输入边和权值:" << endl; 42 for (k = 0; k < G.arcum; k++) 43 { 44 cin >> v1 >> v2 >> w; 45 i = locateVex(G, v1); 46 j = locateVex(G, v2); 47 G.arcs[i][j] = G.arcs[j][i] = w;//关于主对角线对称的元素是相等的 48 } 49 50 } 51 52 int minimum(minside sz, MGraph G) //寻找最小 53 { 54 int i = 0, j, k, min; 55 while (!sz[i].lowcost) //如果sz中的第i个元素的权值为0，则i移动到下一个位置 56 i++; 57 min = sz[i].lowcost; //将上一步操作后得到的i此步利用，并将此位置对应的权值出入min 58 k = i; 59 for (j = i + 1; j < G.vexnum; j++)//权值进行比较，找出不重复且最小的 60 { 61 if (sz[j].lowcost > 0 && min > sz[j].lowcost) 62 { 63 min = sz[j].lowcost; 64 k = j; 65 } 66 } 67 return k; 68 } 69 70 void MiniSpanTree_PRIM(MGraph G, string u)//Prim算法 71 { 72 int i, j, k; 73 minside closedge; 74 k = locateVex(G, u); 75 for (j = 0; j < G.vexnum; j++) 76 { 77 closedge[j].adjvex = u; //存放顶点 78 closedge[j].lowcost = G.arcs[k][j]; 79 } 80 closedge[k].lowcost = 0; //该点用过后权值归0 81 82 cout << "最小生成树各边为:" << endl; 83 for (i = 1; i < G.vexnum; i++) 84 { 85 k = minimum(closedge, G); 86 cout << closedge[k].adjvex << "-" << G.vexs[k] << endl; 87 closedge[k].lowcost = 0; //同样权值归0 88 for (j = 0; j < G.vexnum; j++) 89 { 90 if (G.arcs[k][j] < closedge[j].lowcost) 91 { 92 closedge[j].adjvex = G.vexs[k]; 93 closedge[j].lowcost = G.arcs[k][j]; 94 } 95 } 96 } 97 } 98 99 int main() 100 { 101 MGraph G; 102 CreateGraphUDG(G); 103 MiniSpanTree_PRIM(G, G.vexs[0]);//这里是默认从第一个顶点开始使用Prim算法 104 cout << endl; 105 return 0; 106 }
输出结果:
关于克鲁斯卡尔算法博主明天会更新，请耐心等待...