前幾天考試，最后一題是有關最小生成樹的，但是由于好久沒有看數據結構了，把最小生成樹和最短路徑算法搞混了 （二者本來就很相近）。今天首先寫了最小生成樹的算法，

然后將其代碼復制粘貼，在原來的基礎上稍作修改，就變成了最短路徑算法。（二者最大的區別應該是對某一個標志數組的更新上，最小生成樹是將集合V中的點，更新為到集合U中任意一點的最短距離，而最短路徑則是將集合V中點更新為到源點的最短距離）。并且采用了同一個測試用例。

? 希望對這兩種算法模糊的同學起到一定的幫助作用，下面是最小生成樹代碼

//最小生成樹 /* 6 0 6 1 5 0 0 6 0 5 0 3 0 1 5 0 5 6 4 5 0 5 0 0 2 0 3 6 0 0 6 0 0 4 2 6 0 */#include <stdio.h> #include<string.h> #define MAX_SIZE 100int n ; int closedge[MAX_SIZE]; int min_road(int a[]);int main (){int sum;int i, j ;int G[MAX_SIZE][MAX_SIZE];scanf("%d",&n);for (i = 0 ; i < n ; i ++)for ( j = 0 ; j < n ; j++){scanf("%d",&G[i][j]);if (G[i][j]==0)G[i][j]=0x7fffffff;}sum = MinSpanTree_prim(G , 0);printf("總花費 = %d\n",sum);return 0;}int MinSpanTree_prim(int G[][MAX_SIZE] ,int v){int i,j;int sum = 0 ;//總花費int new_point ;//新節點for ( i = 0 ; i < n ; i ++){closedge[i] = G[v][i];}closedge[v] = 0;printf("%d\n",v);for (i = 1 ; i < n ; i++){new_point = min_road(closedge);//從數組中找出最小的非零邊，沒有返回-1printf("%d\n",new_point);if (new_point^-1){sum += closedge[new_point] ;closedge[new_point] = 0 ;//加入生成樹}else{printf("圖不連通\n");}for ( j = 0 ; j < n ; j ++){if (closedge[j] && G[new_point][j]){closedge[j] = G[new_point][j]<closedge[j]?G[new_point][j]:closedge[j];}// printf(" %d ",closedge[j]);}printf("\n");}return sum;} int min_road(int a[]){int min = 0x7fffffff ;int v = -1 , i ;for ( i = 0 ; i< n ; i++){if (closedge[i] && closedge[i]<min){min = closedge[i] ;v = i ;}}return v;}

最短路徑算法代碼：

//最段路徑 /* 6 0 6 1 5 0 0 6 0 5 0 3 0 1 5 0 5 6 4 5 0 5 0 0 2 0 3 6 0 0 6 0 0 4 2 6 0 */#include <stdio.h> #include<string.h> #define MAX_SIZE 100int n ; int closedge[MAX_SIZE];//記錄各點到源點的距離 int visited[MAX_SIZE] ;//記錄該點是否已經加入集合V int min_road(int a[]);int main (){int sum;int i, j ;int G[MAX_SIZE][MAX_SIZE];scanf("%d",&n);for (i = 0 ; i < n ; i ++)for ( j = 0 ; j < n ; j++){scanf("%d",&G[i][j]);if (G[i][j]==0)G[i][j]=0x7fffffff;}MinSpanTree_prim(G , 0);return 0;}int MinSpanTree_prim(int G[][MAX_SIZE] ,int v){int i,j;//int sum = 0 ;//總花費int new_point ;//新節點for ( i = 0 ; i < n ; i ++){visited[i] = 0;closedge[i] = G[v][i];}closedge[v] = 0;visited[v] = 1;// printf("%d\n",v);for (i = 1 ; i < n ; i++){new_point = min_road(closedge);//從數組中找出最小的非零邊，沒有返回-1// printf("%d\n",new_point);if (new_point^-1){visited[new_point] = 1;//加入集合U// sum += closedge[new_point] ;//closedge[new_point] = 0 ;//加入生成}else{printf("圖不連通\n");}for ( j = 0 ; j < n ; j ++){if ( !visited[j] && G[new_point][j]!=0x7fffffff){closedge[j] = (G[new_point][j] + closedge[new_point])<closedge[j]?(G[new_point][j] + closedge[new_point]):closedge[j];//更新集合V中的最短路徑}printf(" %d ",closedge[j]);}printf("\n");}// return sum;} int min_road(int a[]){int min = 0x7fffffff ;int v = -1 , i ;for ( i = 0 ; i< n ; i++){if (!visited[i] && closedge[i]<min){min = closedge[i] ;v = i ;}}return v;}

總結

以上是生活随笔為你收集整理的由最小生成树算法改到最短路径算法代码----为了区分两者的区别的全部內容，希望文章能夠幫你解決所遇到的問題。

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