數據結構—prim最小生成樹

原理：參考趣學數據結構

代碼：

#include<stdio.h> #include<stdlib.h> #define N 100 #define elemType int //const int MAX_INT = (1 << 31) - 1; //const int MAX_INT = 0X7fffffff; #define INF (((unsigned int)(-1)) >> 1) bool visited[N]; typedef struct GraphMatrix {elemType vNode[N][N];int vNum, eNum; }GraphMatrix; void initGMaxtix(GraphMatrix &G) {//初始化鄰接矩陣printf("輸入頂點數和邊數\n");scanf_s("%d%d", &G.vNum, &G.eNum);for (int i = 0; i < G.vNum; i++) {//初始化鄰接矩陣for (int j = 0; j < G.vNum; j++) {G.vNode[i][j] = INF;}}printf("輸入頂點v1到頂點v2和其邊的權重\n");for (int i = 0; i < G.eNum; i++) {int v1, v2, weights;scanf_s("%d%d%d", &v1, &v2, &weights);G.vNode[v1][v2] = weights;} } void print15(GraphMatrix G) {printf("鄰接矩陣如下:\n");for (int i = 0; i < G.vNum; i++) {for (int j = 0; j < G.vNum; j++) {printf("%d ", G.vNode[i][j]);}printf("\n");} } void prim(GraphMatrix G, int u0) {//最小生成樹int lowcost[N], closeV[N];for (int i = 0; i < G.vNum; i++) {//初始化lowcost[i] = G.vNode[u0][i];closeV[i] = u0;if (u0 == i) {lowcost[u0] = 0;}}visited[u0] = true;printf("%d ", u0);for (int k = 0; k < G.vNum - 1; k++) {//最小生成樹 頂點數-1條邊int t = u0, Temp = INF;for (int i = 0; i < G.vNum; i++) {//尋找連接兩個集合最短邊（已經訪問和未被訪問）if (!visited[i] && Temp > lowcost[i]) {Temp = lowcost[i];t = i;}}if (t == u0) {break;}visited[t] = true;printf("%d ", t);for (int i = 0; i < G.vNum; i++) {//因為新結點的加入，可能會縮短兩個頂點集合之間的距離,更新操作if (!visited[i]&&G.vNode[t][i] < lowcost[i]) {lowcost[i] = G.vNode[t][i];closeV[i] = t;}}}printf("\n哪些邊有關系:\n");for (int i = 0; i < G.vNum; i++) {if (i != u0) {printf("%d---%d有邊\n", i, closeV[i]);}} } int main() {GraphMatrix G;initGMaxtix(G);print15(G);printf("\n");for (int i = 0; i < G.vNum; i++) {visited[i] = false;}printf("prim最小生成樹\n");prim(G, 0);printf("\n");system("pause");return 0; }

測試截圖：

時間復雜度O(n x n),空間復雜度O(n)

如果存在什么問題，歡迎批評指正！謝謝！

總結

以上是生活随笔為你收集整理的数据结构---prim最小生成树的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。