最近看图论 ，把Prim和Kruskal又写了一遍。 觉得Prim算法和Dijkstra算法还是很相似的。也算记录一次啊。这次只放出Prim的写法。
Kruskal算法 由并查集算法搭建而成，找出最小生成树。 她把所有的路径的权值输入到一个数组里面，排序，然后根据权值合并，直至找到一条最短的路径（或者连不起来）
Prim算法 从起点开始，在能够通过的路上找到最小的权值，连接处一条最短的路径出来。
以下代码 第一行输入结点数， 然后输入一个矩阵（邻接表） 输出由Prim算法所输出的每一个过程的邻接表的变化。
struct record{ int a;//起点 int b;//终点 int way;//权值 }prim_vec[len];//结构体 来存储一条路 void prim(){ for (int i=0; i<num; i++){ for (int j=0; j<num; j++){ cout << book_map[i][j] << " "; } cout << endl; }//输出当前数组 cout << endl; if (Road == num) return;//结束判断 for (int i=0; i<flag; i++) { if (vis[prim_vec[i].b] == 0){ book_map[prim_vec[i].a][prim_vec[i].b] = prim_vec[i].way; book_map[prim_vec[i].b][prim_vec[i].a] = prim_vec[i].way; vis[prim_vec[i].b]++; Road++; //在标记途中把两个点连起来 for (int j=0; j<num; j++) { if (map[prim_vec[i].b][j] != 0 ){ prim_vec[flag].a = prim_vec[i].b; prim_vec[flag].b = j; prim_vec[flag].way = map[prim_vec[i].b][j]; flag ++; } }//把新点的能到达的路径放入数组之中 break; } } sort(prim_vec,prim_vec+flag,cmp);//路径新排序 prim(); } //main函数里面 主要是对起点的设置 int main() { cin >> num; for (int i=0; i<num; i++){ for (int j=0; j<num; j++){ cin >> map[i][j]; } } cout << "Prim: " << endl; for (int i=0; i<num; i++){ if (map[0][i] != 0){ prim_vec[flag].a = 0; prim_vec[flag].b = i; prim_vec[flag].way = map[0][i]; flag ++; } } vis[0] ++;Road++; sort(prim_vec,prim_vec+flag,cmp); prim(); return 0; }