求最小生成樹演算法代碼及運行圖片

① 用破圈法求最小生成樹

感覺上你那裡的「演算法基本思想」實現難度很大，因為圖的連通性不好維護
找圈的話，隨便找個節點為根DFS整個圖，然後在這樣的DFS生成樹中，每條非樹邊都對應了一個圈，每次找一條非樹邊，刪去所在圈中最長邊生成一個新樹，直到不存在非樹邊為止，剩下的就是最小生成樹了
具體實現的時候，先求出一個DFS生成樹，然後遞歸處理每棵子樹

假設要處理的子樹根節點為u，對該子樹破圈法的粗略偽代碼如下：

void 破圈法(u)
{
for ( v是u的每個子節點 ) 破圈法(v);
for ( e是連接u與其後繼的每條非樹邊 )
{
v=e的另一個端點;
e'=u到v之間的最長樹邊;
if (w[e]>=w[e']) 刪除邊e;//w[e]表示e的權
else
{
//用w表示原先e'的在樹中較深的端點,p[v]表示v的親節點
刪除邊e';
if (v!=w)
{
將v列入u的子節點列表;
將p[v]、p[p[v]]、...、w這條路徑反向，並將p[v]列入v的子節點列表;
}
}
}
}

上述過程不加優化的時間復雜度為O(VE)，效率非常差
貌似其中找最長邊和將v的若干祖先節點路徑反向的兩步優化空間比較大，或許可將整個時間復雜度下降到O(ElgV)，研究中

② c加加提問，克魯斯卡爾演算法是什麼

克魯斯卡爾演算法，從邊的角度求網的最小生成樹，時間復雜度為O(eloge)。和普里姆演算法恰恰相反，更適合於求邊稀疏的網的最小生成樹。

對於任意一個連通網的最小生成樹來說，在要求總的權值最小的情況下，最直接的想法就是將連通網中的所有邊按照權值大小進行升序排序，從小到大依次選擇。

由於最小生成樹本身是一棵生成樹，所以需要時刻滿足以下兩點：

• 生成樹中任意頂點之間有且僅有一條通路，也就是說，生成樹中不能存在迴路；

• 對於具有 n 個頂點的連通網，其生成樹中只能有 n-1 條邊，這 n-1 條邊連通著 n 個頂點。

連接 n 個頂點在不產生迴路的情況下，只需要 n-1 條邊。

• 所以克魯斯卡爾演算法的具體思路是：將所有邊按照權值的大小進行升序排序，然後從小到大一一判斷，條件為：如果這個邊不會與之前選擇的所有邊組成迴路，就可以作為最小生成樹的一部分；反之，捨去。直到具有 n 個頂點的連通網篩選出來 n-1 條邊為止。篩選出來的邊和所有的頂點構成此連通網的最小生成樹。



判斷是否會產生迴路的方法為：在初始狀態下給每個頂點賦予不同的標記，對於遍歷過程的每條邊，其都有兩個頂點，判斷這兩個頂點的標記是否一致，如果一致，說明它們本身就處在一棵樹中，如果繼續連接就會產生迴路；如果不一致，說明它們之間還沒有任何關系，可以連接。

• 假設遍歷到一條由頂點 A 和 B 構成的邊，而頂點 A 和頂點 B 標記不同，此時不僅需要將頂點 A 的標記更新為頂點 B 的標記，還需要更改所有和頂點 A 標記相同的頂點的標記，全部改為頂點 B 的標記。


（6）



• 當選取的邊的數量相比與頂點的數量小 1 時，說明最小生成樹已經生成。所以最終採用克魯斯卡爾演算法得到的最小生成樹為（6）所示。



• 實現代碼：#include "stdio.h"#include "stdlib.h"#define MAX_VERtEX_NUM 20#define VertexType inttypedef struct edge{VertexType initial;VertexType end;VertexType weight;}edge[MAX_VERtEX_NUM];//定義輔助數組typedef struct {VertexType value;//頂點數據int sign;//每個頂點所屬的集合}assist[MAX_VERtEX_NUM];assist assists;//qsort排序函數中使用，使edges結構體中的邊按照權值大小升序排序int cmp(const void *a,const void*b){return ((struct edge*)a)->weight-((struct edge*)b)->weight;}//初始化連通網void CreateUDN(edge *edges,int *vexnum,int *arcnum){printf("輸入連通網的邊數： ");scanf("%d %d",&(*vexnum),&(*arcnum));printf("輸入連通網的頂點： ");for (int i=0; i<(*vexnum); i++) {scanf("%d",&(assists[i].value));assists[i].sign=i;}printf("輸入各邊的起始點和終點及權重： ");for (int i=0 ; i<(*arcnum); i++) {scanf("%d,%d,%d",&(*edges)[i].initial,&(*edges)[i].end,&(*edges)[i].weight);}}//在assists數組中找到頂點point對應的位置下標int Locatevex(int vexnum,int point){for (int i=0; i<vexnum; i++) {if (assists[i].value==point) {return i;}}return -1;}int main(){int arcnum,vexnum;edge edges;CreateUDN(&edges,&vexnum,&arcnum);//對連通網中的所有邊進行升序排序，結果仍保存在edges數組中qsort(edges, arcnum, sizeof(edges[0]), cmp);//創建一個空的結構體數組，用於存放最小生成樹edge minTree;//設置一個用於記錄最小生成樹中邊的數量的常量int num=0;//遍歷所有的邊for (int i=0; i<arcnum; i++) {//找到邊的起始頂點和結束頂點在數組assists中的位置int initial=Locatevex(vexnum, edges[i].initial);int end=Locatevex(vexnum, edges[i].end);//如果頂點位置存在且頂點的標記不同，說明不在一個集合中，不會產生迴路if (initial!=-1&& end!=-1&&assists[initial].sign!=assists[end].sign) {//記錄該邊，作為最小生成樹的組成部分minTree[num]=edges[i];//計數+1num++;//將新加入生成樹的頂點標記全不更改為一樣的for (int k=0; k<vexnum; k++) {if (assists[k].sign==assists[end].sign) {assists[k].sign=assists[initial].sign;}}//如果選擇的邊的數量和頂點數相差1，證明最小生成樹已經形成，退出循環if (num==vexnum-1) {break;}}}//輸出語句for (int i=0; i<vexnum-1; i++) {printf("%d,%d ",minTree[i].initial,minTree[i].end);}return 0;}


• 測試數據：



輸入連通網的邊數：
6 10
輸入連通網的頂點：
1
2
3
4
5
6
輸入各邊的起始點和終點及權重：
1,2,6
1,3,1
1,4,5
2,3,5
2,5,3
3,4,5
3,5,6
3,6,4
4,6,2
5,6,6
1,3
4,6
2,5
3,6
2,3

③ 最小生成樹演算法描述

最小生成樹的求解步驟如下：

• 定義一個初始為空的樹T，表示頂點集和邊集。


• 重復以下操作，直到T成為圖G的生成樹：在T中尋找一條安全邊（u，v），即加入這條邊後T仍保持為MST的子集。


• 將找到的安全邊(u，v)添加到T中，擴大T的范圍。

這可以用Pascal、Prim演算法或Kruskal演算法等具體實現，它們的區別在於尋找安全邊的方式不同：

• Prim演算法：從一個起點v0開始，逐步加入與生成樹距離最近的未加入頂點，更新邊集。


• Kruskal演算法：按權值遞增順序挑選邊，每次選擇不形成迴路的邊加入到最小生成樹中。

一個有 n 個結點的連通圖的生成樹是原圖的極小連通子圖，且包含原圖中的所有 n 個結點，並且有保持圖聯通的最少的邊。

④ 求最小生成樹的kruska演算法，效率盡量高，盡量多點注釋！c++代碼

/*
基本演算法思想：
為使生成樹上總的權值之和達到最小，則應使每一條邊上的權值盡可能地小，自然應從權值最小的邊選起，直至選出 n-1 條互不構成迴路的權值最小邊為止。
具體作法如下：首先構造一個只含 n 個頂點的森林，然後依權值從小到大從連通網中選擇不使森林中產生迴路的邊加入到森林中去，直至該森林變成一棵樹為止，這棵樹便是連通網的最小生成樹。
由於生成樹上不允許有迴路，因此並非每一條居當前權值最小的邊都可選。

用並查積 和 克魯是卡爾演算法實現查找最短邊
利用快排按邊遞增排列，每次從中選出最短邊,同時將最短邊的兩個頂點並入到集合中
心得：利用並查積 和 kruskal演算法結合找最短路徑可以使查找的效率更高
加入集合中的邊都是構成最小生成樹的邊，所以每家一次sum 都要加上這兩個頂點之間的距離
*/
/*下面的代碼輸入n個節點，然後輸入n*（n-1）/2條邊及權值，輸出是連通這些邊的最小權值*/
#include<cstdio>
#include<iostream>
#include<algorithm>
using namespace std;

struct ed
{
int u; //起始點
int v; //終結點
int w; //權重
};
bool cmp(ed a,ed b)
{
return a.w<b.w; //從小到大排序
}
struct ed edge[100000];
int p[105];

int find(int x) //查找x的父親
{
while(p[x]!=x)
x=p[x];
return x;
}
int kruskal(int n)
{
int i,count=1,sum=0;
for(i=0;i<=n;i++)
p[i]=i; //並查集初始化，每個節點到父親是自己
int x,y;
sort(edge,edge+n*(n-1)/2,cmp); //快速排序
for(i=0;count<n;i++)
{
x=find(edge[i].u); //點edge[i].u的父親是x
y=find(edge[i].v); //點edge[i].v的父親是y
if(x!=y) //判斷是否會路
{
count++; //加上一條邊
p[x]=y; //把x和y加入統一個集合
sum+=edge[i].w;
}
}
return sum;
}
int main()
{
int n;
while(scanf("%d",&n)!=EOF&&n) //輸入n個節點
{
int i;
for(i=0;i<n*(n-1)/2;i++) //輸入 n*（n-1）/2條邊
scanf("%d%d%d",&edge[i].u,&edge[i].v,&edge[i].w); //表示點edge[i].u和點edge[i].v之間的權重為 edge[i].w
printf("%d\n",kruskal(n));
}
return 0;
}

樓主，這可是本人一個字一個字敲出來點，要給分啊