③普里姆算法实现最小生成树逻辑
这个算法的核心思路是，从一个节点开始，每次放入以放入节点里权最小的那个节点，重复上述操作直到所有顶点都被放入，光说有点抽象下面看例子。
①把V0放进
②再找V0相邻的所有权值最小的点放进，从带权图中我们可以得到与V0相邻的节点有V1和V5，而它们之间的边的权值分别是3和4，毫无疑问V1就是我们这一步要找的节点
第③步，接着再找V0和V1所有相邻的点有V2 V8 V5 V6，同理可以得出V5为顶点的边权值最小，所以把V5放进A类中
第④步再找V0 V1 V5所有相邻的点有V2 V8 V6 V4，V8是最小权值的边的顶点，放入V8
第⑤步再找V0 V1 V5 V8的所有邻接点V2 V3 V6 V4，同理放入V2
第⑥步找V0 V1 V5 V8 V2的所有邻接点V3 V6 V4，放入V6
第⑦步重复上述的操作，先后放入V7 V4 V3
至此，所有的节点都放进了A类当中，回顾上述的这些操作，根据放入A类的节点的先后顺序，我在带权图上也标记了相对应的边，如下图所示，这些顶点和边就是我们要找的最小生成树
④普里姆算法实现最小生成树代码实现
这里用的是邻接矩阵构建带权图，那我要先将图存入到邻接矩阵中，代码如下
1. void creategrahp(AdjMatrix* G) 2. { 3. int n, e;//n代表顶点数 e代表边数 4. int vi, vj;//vi vj代表边的两个顶点对 5. int w;//表示边的权值 6. printf("要输入的顶点数和边数\n"); 7. scanf("%d%d",&n,&e); 8. G->numV = n; 9. G->numE = e; 10. //图的初始化 11. for(int i = 0; i < n; i++) 12. { 13. for(int j = 0; j < n; j++) 14. { 15. if(i == j) 16. { 17. //一个非带权的图 0代表没有边 1代表有边 18. //边不指向自己 即对角线为0 19. G->Arc[i][j] = 0; 20. } 21. else 22. { 23. //如果是带权的图 初始化为0或者为一个不可能的值 24. G->Arc[i][j] = 65535; 25. } 26. } 27. } 28. //将顶点存入数组 29. for(int i = 0; i < G->numV; i++) 30. { 31. printf("请输入第%d个节点的信息\n",i + 1); 32. scanf("%d", &G->Vertices[i]); 33. } 34. //输入边的信息 35. for(int i = 0; i< G->numE; i++) 36. { 37. //如果输入的是顶点的值 需要从顶点集中查找对应的下标 38. //如果是带权图 还要输入权的信息 39. printf("请输入边的信息Vi,Vj和权值w\n"); 40. scanf("%d%d%d",&vi,&vj,&w); 41. G->Arc[vi][vj] = w; 42. //如果是带权图 等于权值 43. //如果是有向图 就不对称 44. //如果是无向图 矩阵对称 45. G->Arc[vj][vi] = w; 46. } 47. }
接下来我们初始化两个数组adjvex和lowcast，其中adjvex是表示用来保存节点的下标的（存入到树里的节点），lowcast用来保存相关边的权值；这里我们仍用V0为例：开始节点为V0，那么在应该在lowcast数组中存入所有与V0有关的边的权值，如果不存在边就用inf表示。adjvex数组中，第 i 号元素的下标对应连接的另一个节点。
这里我们先把adjvex中的所有元素赋值为0，因为具体不方便确定哪个元素与V0相连，而后面每次新加入节点时又会对该节点相连的节点（即adjvex）做一次更新，方便起见我们就全部初始化为0
1. void Prim(AdjMatrix* G) 2. { 3. int adjvex[MAXVEX];//用来保存相关节点的下标 4. int lowcast[MAXVEX];//用来保存相关边的权值 5. lowcast[0] = 0;//初始化第一个权值为0 表示v0加入最小生成树 6. adjvex[0] = 0;//第一个顶点下标为0 7. for(int i = 1; i <= G->numV; i++) 8. //循环除了0以外的全部顶点 9. { 10. //将与v0有关的边的权值全部存入数组 11. lowcast[i] = G->Arc[0][i]; 12. adjvex[i] = 0; 13. }
接下来就是要去找权值最小的边，并记录这条边的结束节点K，边（V0,Vk）就是最小生成树的一条边，把k放进生成树中，并做上标记表示已经访问过该节点
1. //找寻最小权值 2. for(int i = 1; i < G->numV; i++) 3. { 4. int min = INFINTIY; 5. int k = 0;//返回最小值的下标 6. int j = 1; 7. for(; j <= G->numV; j++)//Vj是除V0以外的顶点 8. { 9. //如果Vi和Vj有边或这条边没有被找到，且边的权值最小 10. if(lowcast[j] != 0 && lowcast[j] < min) 11. { 12. min = lowcast[j];//就让当前权值成为最小值 13. k = j; 14. } 15. } 16. //打印当前找到的顶点的边中 权值最小的边 17. printf("(%d %d)--%d ", adjvex[k], k, lowcast[k]); 18. //将当前顶点的权值设置为0 代表加入了生成树中 19. lowcast[k] = 0;
接下来我们要找的是V0节点和Vk节点的所有邻接点，继续找权值最小的边，所以我们应该更新lowcast和adjvex数组，把与Vk有关的边（之前没被访问过的）的权值放进lowcast中，并把这个边的另一个节点Vj在adjvex中所对应的下标的值改为k，重复上述步骤，直到所有点都加入。
1. for(j = 1; j <= G->numV; j++) 2. { 3. //如果下标为k的顶点相邻的各边的权值小于此前未被加入的顶点的权值 则加入生成树中 4. if(lowcast[j] != 0 && G->Arc[j][k] < lowcast[j]) 5. { 6. //更新lowcast和adjvex数组 7. lowcast[j] = G->Arc[j][k]; 8. adjvex[j] = k; 9. } 10. } 11. }
下面是全部的代码
1. #include<stdio.h> 2. #include<stdlib.h> 3. #define MAXVEX 200 4. #define INFINTIY 65535 5. //prim算法 6. //邻接矩阵 7. typedef struct AdjacentMatrix 8. { 9. //顶点集 10. int Vertices[MAXVEX]; 11. //边集 12. int Arc[MAXVEX][MAXVEX]; 13. //顶点数 边数 14. int numV, numE; 15. }AdjMatrix; 16. //用带权无向邻接矩阵生成图 17. 18. void creategrahp(AdjMatrix* G) 19. { 20. int n, e;//n代表顶点数 e代表边数 21. int vi, vj;//vi vj代表边的两个顶点对 22. int w;//表示边的权值 23. printf("要输入的顶点数和边数\n"); 24. scanf("%d%d",&n,&e); 25. G->numV = n; 26. G->numE = e; 27. //图的初始化 28. for(int i = 0; i < n; i++) 29. { 30. for(int j = 0; j < n; j++) 31. { 32. if(i == j) 33. { 34. //一个非带权的图 0代表没有边 1代表有边 35. //边不指向自己 即对角线为0 36. G->Arc[i][j] = 0; 37. } 38. else 39. { 40. //如果是带权的图 初始化为0或者为一个不可能的值 41. G->Arc[i][j] = 65535; 42. } 43. } 44. } 45. //将顶点存入数组 46. for(int i = 0; i < G->numV; i++) 47. { 48. printf("请输入第%d个节点的信息\n",i + 1); 49. scanf("%d", &G->Vertices[i]); 50. } 51. //输入边的信息 52. for(int i = 0; i< G->numE; i++) 53. { 54. //如果输入的是顶点的值 需要从顶点集中查找对应的下标 55. //如果是带权图 还要输入权的信息 56. printf("请输入边的信息Vi,Vj和权值w\n"); 57. scanf("%d%d%d",&vi,&vj,&w); 58. G->Arc[vi][vj] = w; 59. //如果是带权图 等于权值 60. //如果是有向图 就不对称 61. //如果是无向图 矩阵对称 62. G->Arc[vj][vi] = w; 63. } 64. } 65. 66. void Prim(AdjMatrix* G) 67. { 68. int adjvex[MAXVEX];//用来保存相关节点的下标 69. int lowcast[MAXVEX];//用来保存相关边的权值 70. lowcast[0] = 0;//初始化第一个权值为0 表示v0加入最小生成树 71. adjvex[0] = 0;//第一个顶点下标为0 72. for(int i = 1; i <= G->numV; i++) 73. //循环除了0以外的全部顶点 74. { 75. //将与v0有关的边的权值全部存入数组 76. lowcast[i] = G->Arc[0][i]; 77. adjvex[i] = 0; 78. } 79. //找寻最小权值 80. for(int i = 1; i < G->numV; i++)//用来循环生成边的次数 81. { 82. int min = INFINTIY; 83. int k = 0;//返回最小值的下标 84. int j = 1; 85. for(; j <= G->numV; j++)//Vj是除V0以外的顶点 86. { 87. //如果Vi和Vj有边或这条边没有被找到，且边的权值最小 88. if(lowcast[j] != 0 && lowcast[j] < min) 89. { 90. min = lowcast[j];//就让当前权值成为最小值 91. k = j; 92. } 93. } 94. //打印当前找到的顶点的边中 权值最小的边 95. printf("(%d %d)--%d ", adjvex[k], k, lowcast[k]); 96. //将当前顶点的权值设置为0 代表加入了生成树中 97. lowcast[k] = 0; 98. for(j = 1; j <= G->numV; j++)//从k之后节点开始，进入下一轮迭代 99. { 100. //如果下标为k的顶点相邻的各边的权值小于此前未被加入的顶点的权值 则加入生成树中 101. if(lowcast[j] != 0 && G->Arc[j][k] < lowcast[j]) 102. { 103. //更新lowcast和adjvex数组 104. lowcast[j] = G->Arc[j][k]; 105. adjvex[j] = k; 106. } 107. } 108. } 109. } 110. 111. int main() 112. { 113. AdjMatrix G; 114. creategrahp(&G); 115. Prim(&G); 116. system("pause"); 117. return 0; 118. }
8.最短路径
①最短路径基本概念
在一条路径中，起始的第一个节点叫做源点，在一条路径中，最后一个的节点叫做终点。源点和终点都只是相对于一条路径而言，每一条路径都会有相同或者不相同的源点和终点。
最短路径：在图中，对于非带权无向图而言，从源点到终点边最少的路径（可以用BFS实现），而对于带权图而言，从源点到终点权值之和最少的路径叫最短路径
实现最短路径有两种算法：Dijkstra迪杰斯特拉算法和Floyd弗洛伊德算法
②迪杰斯特拉（Dijkstra）最短路径算法
Dijkstra迪杰斯特拉是一种处理单源点的最短路径算法，就是求从某一个节点到其他所有节点的最短路径算法。在原来的存储基础上，我们还要引入三个变量来帮助我们实现最短路径，D变量：标志着后面的数据与原点到下标为B的变量有关，P变量：记录使该处D发生改变的最后一个节点（这个看不懂可以跳过），Final变量：用来标记是否已经求出源点到该点的最短路径。
对于上图我们要求他的最短路径，现列出那几个变量组成的数组，初始化0节点相连的变量并记录其权值，若不与0相连则写inf，具体如下。
在辅助向量D中，与源点V0有边的就填入边的权值，没边就是无穷大，构建了D、P和Final，那么我们要开始遍历V0，找V0的所有边中权值最短的的边，把它在D、P、Final中更新。
比如在上述带权无向图中，我们可以得到与源点有关的边有（V0，V1）和（V0，V2），它们的权值分别是1和5，那么我们要找到的权值最短的的边，就是权值为1 的（V0，V1），所以把Final[1]置1，表示这个边已经加入到最短路径之中了。而原本从V0到V2的距离是5，现在找到了一条更短的从V0 -> V1 -> V2距离为4，所以D[2]更新为4，P[2]更新为1，表示源点到V2经过了V1的中转
继续遍历，找到从V0出发，路径最短并且final的值为0的节点。因为经过节点V1的中转，源点到V3和V4有了路径，从源点到V3的距离是1+7==8，到V4的距离是1+5==6，把它们在D中更新；再以V1为中心，去找与V1有关的边是否有能更新的边，可以得到此时V0到V2的距离为4，比原来的5小，于是把V2的三个变量更新
重复此步骤直到我们除8以外的节点Final都为1，此时表格如下。
至此，源点和终点都被加入到了最短路径当中，Dijkstra算法结束；我们从P[8]开始从后往前推，就可以得到这个带权无向图的从V0到V8的最短路径；
如图，所示从P[8]开始从后往前推算，数组P中的值就是在最短路径中该节点的上一个节点。可以得到：V8<-V7<-V6<-V3<-V4<-V2<-V1<-V0；即如下图所示：
③迪杰斯特拉算法代码实现
因为是带权的无向图，所以这里是以邻接矩阵去构建图。
1. void creategrahp(AdjMatrix* G) 2. { 3. int n, e;//n代表顶点数 e代表边数 4. int vi, vj;//vi vj代表边的两个顶点对 5. int w;//表示边的权值 6. printf("要输入的顶点数和边数\n"); 7. scanf("%d%d",&n,&e); 8. G->numV = n; 9. G->numE = e; 10. //图的初始化 11. for(int i = 0; i < n; i++) 12. { 13. for(int j = 0; j < n; j++) 14. { 15. if(i == j) 16. { 17. //一个非带权的图 0代表没有边 1代表有边 18. //边不指向自己 即对角线为0 19. G->Edge[i][j] = 0; 20. } 21. else 22. { 23. //如果是带权的图 初始化为0或者为一个不可能的值 24. G->Edge[i][j] = 65535; 25. } 26. } 27. } 28. //将顶点存入数组 29. for(int i = 0; i < G->numV; i++) 30. { 31. printf("请输入第%d个节点的信息\n",i + 1); 32. scanf("%d", &G->Vertices[i]); 33. } 34. //输入边的信息 35. for(int i = 0; i< G->numE; i++) 36. { 37. //如果输入的是顶点的值 需要从顶点集中查找对应的下标 38. //如果是带权图 还要输入权的信息 39. printf("请输入边的信息Vi,Vj和权值w\n"); 40. scanf("%d%d%d",&vi,&vj,&w); 41. G->Edge[vi][vj] = w; 42. //如果是带权图 等于权值 43. //如果是有向图 就不对称 44. //如果是无向图 矩阵对称 45. G->Edge[vj][vi] = w; 46. } 47. }
④弗洛伊德（Floyd）最短路径算法
我们现在只能通过Dijkstra求从某一个节点到其他所有节点的最短路径，如果我们想要求出任意两个节点之间的最短路径，就需要执行 N 次的 Dijkstra 算法。在Dijkstra的实现中，我们用到了长度为 N 的辅助向量和路径向量，这时候如果要想知道任意两个节点之间的最短路径，就需要用到 N * N 个大小的二维数辅助向量和路径向量。这也是Floyd的算法核心和出现的原因，但是Floyd只是思想巧妙，在复杂度上没有提升多少。
总结
未完待续
