prim最小生成樹算法

對于幾個圖G{V,E};首先從V中任意選擇一個頂點Vo 將其加入到頂點集合U中，在頂點集合V-U中計算所有到V中任意頂點假設是Vo最近的頂點Voo,將其加入到U中，并且記錄邊E{Vo,Voo}，一直重復以上操作直到頂點集合V等于集合U結(jié)束。

代碼實現(xiàn)

#include "stdio.h" #include "stdlib.h" #include "io.h" #include "math.h" #include "time.h"#define OK 1 #define ERROR 0 #define TRUE 1 #define FALSE 0#define MAXEDGE 20 #define MAXVEX 20 #define INFINITY 65535typedef int Status; /* Status是函數(shù)的類型,其值是函數(shù)結(jié)果狀態(tài)代碼，如OK等 */typedef struct {int arc[MAXVEX][MAXVEX];int numVertexes;int numEdges; }MGraph;void CreateMGraph(MGraph* G)/* 構(gòu)件圖 */ {int i, j;/* printf("請輸入邊數(shù)和頂點數(shù):"); */G->numEdges = 15;G->numVertexes = 9;for (i = 0; i < G->numVertexes; i++)/* 初始化圖 */{for (j = 0; j < G->numVertexes; j++){if (i == j)G->arc[i][j] = 0;elseG->arc[i][j] = G->arc[j][i] = INFINITY;}}G->arc[0][1] = 10;G->arc[0][5] = 11;G->arc[1][2] = 18;G->arc[1][8] = 12;G->arc[1][6] = 16;G->arc[2][8] = 8;G->arc[2][3] = 22;G->arc[3][8] = 21;G->arc[3][6] = 24;G->arc[3][7] = 16;G->arc[3][4] = 20;G->arc[4][7] = 7;G->arc[4][5] = 26;G->arc[5][6] = 17;G->arc[6][7] = 19;for (i = 0; i < G->numVertexes; i++){for (j = i; j < G->numVertexes; j++){G->arc[j][i] = G->arc[i][j];}}}void MiniSpanTree_Prim(MGraph G) {int min, i, j, k;int adjvex[MAXVEX];/* 保存相關頂點下標 */int lowcost[MAXVEX];/* 保存相關頂點間邊的權(quán)值 *//* 初始化第一個權(quán)值為0，即v0加入生成樹 *//* lowcost的值為0，在這里就是此下標的頂點已經(jīng)加入生成樹 */lowcost[0] = 0;adjvex[0] = 0; /* 初始化第一個頂點下標為0 */for (int i = 1; i < G.numVertexes; i++){lowcost[i] = G.arc[0][i]; // //lowcost[j] 記錄的是待加入的頂點中距離adjvex[j]元素的最小值adjvex[i] = 0; /* 初始化都為v0的下標 */}for (int i = 1; i < G.numVertexes; i++){min = INFINITY;j = 1;k = 0;//循環(huán)全部頂點while (j < G.numVertexes){if (lowcost[j] != 0 && lowcost[j] < min){min = lowcost[j];k = j;}j++;}printf("(%d, %d)\n", adjvex[k], k);/* 打印當前頂點邊中權(quán)值最小的邊 */lowcost[k] = 0;/* 將當前頂點的權(quán)值設置為0,表示此頂點已經(jīng)完成任務 */for (j = 1; j < G.numVertexes; j++) /* 循環(huán)所有頂點 */{if (lowcost[j] != 0 && G.arc[k][j] < lowcost[j]){/* 如果下標為k頂點各邊權(quán)值小于此前這些頂點未被加入生成樹權(quán)值 */lowcost[j] = G.arc[k][j];/* 將較小的權(quán)值存入lowcost相應位置 */adjvex[j] = k; /* 將下標為k的頂點存入adjvex */}}} } int main(void) {MGraph G;CreateMGraph(&G);MiniSpanTree_Prim(G);return 0;}

克魯斯卡爾算法

算法原理 先把所有邊排序 依次將最小的邊加入到選擇中，加入的過程要保證不能出現(xiàn)環(huán)

保證不出現(xiàn)環(huán)的方法：很多 大話數(shù)據(jù)結(jié)構(gòu)中給了一個方法 就是利用一個數(shù)組保存已經(jīng)選擇的邊，具體解釋起來比較麻煩

#include "stdio.h" #include "stdlib.h" #include "io.h" #include "math.h" #include "time.h"#define OK 1 #define ERROR 0 #define TRUE 1 #define FALSE 0typedef int Status; /* Status是函數(shù)的類型,其值是函數(shù)結(jié)果狀態(tài)代碼，如OK等 */#define MAXEDGE 20 #define MAXVEX 20 #define INFINITY 65535typedef struct {int arc[MAXVEX][MAXVEX];int numVertexes;int numEdges; }MGraph;typedef struct {int begin;int end;int weight; }Edge; /* 對邊集數(shù)組Edge結(jié)構(gòu)的定義 *//* 構(gòu)件圖 */ void CreateMGraph(MGraph* G) {int i, j;/* printf("請輸入邊數(shù)和頂點數(shù):"); */G->numEdges = 15;G->numVertexes = 9;for (i = 0; i < G->numVertexes; i++)/* 初始化圖 */{for (j = 0; j < G->numVertexes; j++){if (i == j)G->arc[i][j] = 0;elseG->arc[i][j] = G->arc[j][i] = INFINITY;}}G->arc[0][1] = 10;G->arc[0][5] = 11;G->arc[1][2] = 18;G->arc[1][8] = 12;G->arc[1][6] = 16;G->arc[2][8] = 8;G->arc[2][3] = 22;G->arc[3][8] = 21;G->arc[3][6] = 24;G->arc[3][7] = 16;G->arc[3][4] = 20;G->arc[4][7] = 7;G->arc[4][5] = 26;G->arc[5][6] = 17;G->arc[6][7] = 19;for (i = 0; i < G->numVertexes; i++){for (j = i; j < G->numVertexes; j++){G->arc[j][i] = G->arc[i][j];}}}/* 交換權(quán)值 以及頭和尾 */ void Swapn(Edge* edges, int i, int j) {int temp;temp = edges[i].begin;edges[i].begin = edges[j].begin;edges[j].begin = temp;temp = edges[i].end;edges[i].end = edges[j].end;edges[j].end = temp;temp = edges[i].weight;edges[i].weight = edges[j].weight;edges[j].weight = temp; }/* 對權(quán)值進行排序 */ void sort(Edge edges[], MGraph* G) {int i, j;for (i = 0; i < G->numEdges; i++){for (j = i + 1; j < G->numEdges; j++){if (edges[i].weight > edges[j].weight){Swapn(edges, i, j);}}}printf("權(quán)排序之后的為:\n");for (i = 0; i < G->numEdges; i++){printf("(%d, %d) %d\n", edges[i].begin, edges[i].end, edges[i].weight);}}/* 查找連線頂點的尾部下標 */ int Find(int* parent, int f) {while (parent[f] > 0){f = parent[f];}return f; }/* 生成最小生成樹 */ void MiniSpanTree_Kruskal(MGraph G) {int i, j, n, m;int k = 0;int parent[MAXVEX];/* 定義一數(shù)組用來判斷邊與邊是否形成環(huán)路 */Edge edges[MAXEDGE];/* 定義邊集數(shù)組,edge的結(jié)構(gòu)為begin,end,weight,均為整型 *//* 用來構(gòu)建邊集數(shù)組并排序********************* */for (i = 0; i < G.numVertexes - 1; i++){for (j = i + 1; j < G.numVertexes; j++){if (G.arc[i][j] < INFINITY){edges[k].begin = i;edges[k].end = j;edges[k].weight = G.arc[i][j];k++;}}}sort(edges, &G);/* ******************************************* */for (i = 0; i < G.numVertexes; i++)parent[i] = 0; /* 初始化數(shù)組值為0 */printf("打印最小生成樹：\n");for (i = 0; i < G.numEdges; i++) /* 循環(huán)每一條邊 */{n = Find(parent, edges[i].begin);m = Find(parent, edges[i].end);if (n != m) /* 假如n與m不等，說明此邊沒有與現(xiàn)有的生成樹形成環(huán)路 */{parent[n] = m; /* 將此邊的結(jié)尾頂點放入下標為起點的parent中。 *//* 表示此頂點已經(jīng)在生成樹集合中 */printf("(%d, %d) %d\n", edges[i].begin, edges[i].end, edges[i].weight);}} }int main(void) {MGraph G;CreateMGraph(&G);MiniSpanTree_Kruskal(G);return 0; }

總結(jié)

以上是生活随笔為你收集整理的大话数据结构18：最小生成树算法的全部內(nèi)容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網(wǎng)站內(nèi)容還不錯，歡迎將生活随笔推薦給好友。