文章目錄

• 前言
• 一、目的與要求
• • 設(shè)計(jì)目的
  • 設(shè)計(jì)要求
• 二、原理及方案
• • 1.克魯斯卡爾（Kruskal）算法
  • 2.方案思路
• 三、設(shè)計(jì)過程
• 四、設(shè)計(jì)結(jié)果
• 五、例題測試
• 總結(jié)
• 結(jié)語

---

前言

問題描述：用克魯斯卡爾算法求無向網(wǎng)圖的最小生成樹。本文編程軟件是Visual Studio 2019，使用的是C語言進(jìn)行課程設(shè)計(jì)。

---

提示：以下是本篇文章正文內(nèi)容，下面案例可供參考。

一、目的與要求

設(shè)計(jì)目的

該課題的源碼必須能夠調(diào)試成功；

提供一個(gè)main函數(shù)完成的程序源碼版本。基本數(shù)據(jù)結(jié)構(gòu)有詳細(xì)說明，每個(gè)功能函數(shù)有詳細(xì)說明；

全文關(guān)鍵代碼須加上注釋。

設(shè)計(jì)要求

生成一個(gè)無向網(wǎng)圖；

要求采用鄰接矩陣或鏈接表存儲(chǔ)來完成；

最后打印輸出最小生成樹；

每一個(gè)函數(shù)要有必要的注釋，在課程設(shè)計(jì)中有流程圖。

二、原理及方案

1.克魯斯卡爾（Kruskal）算法

克魯斯卡爾算法的思想是：假設(shè)G=（V,E）是一個(gè)具有n給頂點(diǎn)的連通網(wǎng)，T=（U,TE）是G的最小生成樹。U的初值等于V，即擁有G中的全部頂點(diǎn)。算法開始時(shí)，TE的初值為空值。將圖G中的邊按權(quán)值從小到大的順序依次選取，若選取的邊使生成樹T不形成回路，則把它并入TE中，保留作為T的一條邊；若選取的邊使生成樹T形成回路，則將其舍棄，如此進(jìn)行下去，直到TE中包含n-1條邊為止，此時(shí)的T即為最小生成樹。
🎈這里我們通過一個(gè)例子了解如何對一個(gè)無向帶權(quán)圖采用克魯斯卡爾算法求其最小生成樹：

---

例，對于下圖所示的無向帶權(quán)圖，采用克魯斯卡爾算法求最小生成樹的過程為：

通過該圖，可知其中的邊按權(quán)值由小到大的順序是：
從頂點(diǎn)5開始，連接5和4，權(quán)值為1

再連接3，4，權(quán)值為2，此時(shí)選取的邊使生成樹T形成回路，舍棄；從另一邊連接5，0，權(quán)值為3；再連接0，2，權(quán)值為4，形成回路舍棄；連接5，1，權(quán)值為5，如下圖，即得到最小生成樹：

步驟生成樹中各頂點(diǎn)集合生成樹的邊生成樹的權(quán)值

初始狀態(tài)	{0}，{1}，{2}，{3}，{4}，{5}
1	{0}，{1}，{2}，{3},{4,5}	(4,5)	1
2	{0}，{1}，{2}，{3,4,5}	(3,4)	2
3	{1}，{2}，{0,3,4,5}	(0,5)	3
4	{1}，{2,0,3,4,5}	(0,2)	4
5	{1,2,0,3,4,5}	(1,5)	5

---

實(shí)現(xiàn)該算法需要設(shè)一個(gè)邊集合數(shù)組E，其中包括邊的起始點(diǎn)u，終止點(diǎn)v和這條邊的權(quán)值w。首先編寫函數(shù)CreateEdge循環(huán)建立一個(gè)邊集合E，并返回邊的數(shù)目n。因?yàn)榭唆斔箍査惴ㄒ筮吋仨毷前磸男〉酱蟮捻樞蚺藕?#xff0c;所以編寫函數(shù)seeks實(shí)現(xiàn)對數(shù)組E進(jìn)行排序的功能，函數(shù)sort排序的結(jié)果是E中各邊按從小到大排好序。
克魯斯卡爾算法的編程思路是首先要用到輔助數(shù)組set，用來存放各頂點(diǎn)所在的最小生成樹頂點(diǎn)集合，然后從邊集E中順序取出各條邊，判斷該邊的兩個(gè)頂點(diǎn)是否在同一集合中（需要編寫一個(gè)判斷頂點(diǎn)所在集合的函數(shù)seeks），若不在同一集合，則該邊為最小生成樹的一條邊，輸出該條邊的頂點(diǎn)序列和權(quán)值，并在set數(shù)組中將頂點(diǎn)v2加到頂點(diǎn)v1集合中，重復(fù)以上操作直到所有頂點(diǎn)都在一個(gè)集合中結(jié)束。

2.方案思路

Prim算法是找點(diǎn)，而我們所用的Kruscal算法則是從邊出發(fā)。
具體思路：
1.把所有的邊和這條邊代表的權(quán)值用一個(gè)數(shù)組存儲(chǔ)起來，并按權(quán)值大小給數(shù)組排序（升序）。
2.按順序從數(shù)組中拿出一條邊，檢查這條邊是否與到目前為止形成的樹構(gòu)成環(huán)，如果形成了環(huán)，就丟棄它；如果沒有，就把這條邊加入樹中。
3.重復(fù)步驟2，直到樹中有 n-1 條邊為止。

三、設(shè)計(jì)過程

程序中無向網(wǎng)采用鄰接矩陣存儲(chǔ)，c程序如下：

//克魯斯卡爾（Kruscal）算法求最小生成樹 #include <stdio.h> #define MAX 100 //定義最大頂點(diǎn)數(shù) typedef struct //建立一個(gè)邊集合數(shù)組，其中包括邊的起始點(diǎn)、終止點(diǎn)以及這條邊的權(quán)值 {int u; //一條邊的起始頂點(diǎn)int v; //一條邊的終止頂點(diǎn)int w; //邊的權(quán)值（權(quán)重） }Edge; //邊的類型定義 Edge E[MAX]; //定義一個(gè)全局?jǐn)?shù)組E，用于存儲(chǔ)圖的各條邊（創(chuàng)建邊的數(shù)組） //創(chuàng)建一個(gè)無向網(wǎng)圖 int CreateEdge() {int i;int anum;printf("\n輸入無向網(wǎng)的邊數(shù)：");scanf_s("%d", &anum);for (i = 0; i < anum; ++i){printf("\n輸入第%d條邊的起始頂點(diǎn)、終止頂點(diǎn)以及該邊的權(quán)值（v1、v2、w）：\n",i+1);scanf_s("%d %d %d", &E[i].u, &E[i].v, &E[i].w);}return anum; }//對邊表進(jìn)行從小到大排序算法 void sort(int n) {int i, j;Edge t;for (i = 0; i < n-1; i++)for(j=i+1;j<n;j++)if(E[i].w>E[j].w){t = E[i];E[i] = E[j];E[j] = t;} }//在邊表中查看頂點(diǎn)v在哪個(gè)連通集合中 int seeks(int set[], int v) {int i = v;while (set[i] > 0)i = set[i];return(i); }//克魯斯卡爾算法的核心環(huán)節(jié) void Kruskal(Edge E[], int n) //算法核心環(huán)節(jié) {int set[MAX]; //創(chuàng)建狀態(tài)臨時(shí)數(shù)組(輔助標(biāo)志數(shù)組)int v1, v2, i; //數(shù)組中的下標(biāo)的臨時(shí)變量for (i = 0; i < MAX; i++)set[i] = 0; //給set數(shù)組中的每個(gè)元素賦予初值i = 0; //i表示特獲取的生成樹種的邊數(shù)，初值為1while(i<n) //按邊權(quán)遞增順序，逐邊檢查該邊是否應(yīng)加入到生成樹中 {v1 = seeks(set, E[i].u); //確定頂點(diǎn)v所在的連通集v2 = seeks(set, E[i].v);if (v1!=v2) //當(dāng)v1，v2不在同一頂點(diǎn)集合，確定該邊應(yīng)當(dāng)選入生成樹{printf("(%d,%d) %d\n",E[i].u,E[i].v,E[i].w);set[v1]=v2; //將v2加入到v1的集合中}i++;} }void main() {int n;n=CreateEdge(); //調(diào)用生成邊表函數(shù)if(n>0) //判斷輸入的n值是否合法（n>0）{sort(n); //對邊表集合進(jìn)行排序printf("\n最小生成樹為( (頂點(diǎn),頂點(diǎn)) 權(quán)值 ):\n");}elseprintf("\n輸入邊數(shù)錯(cuò)誤，請重新輸入！\n");Kruskal(E,n); //調(diào)用克魯斯卡爾算法求最小生成樹 }

四、設(shè)計(jì)結(jié)果

五、例題測試

剛剛更新，我們通過一道題由以上代碼可解決，直接上張圖：

總結(jié)

以上就是今天要講的內(nèi)容，本文利用克魯斯卡爾（Kruscal）算法求最小生成樹中（無向網(wǎng)采用鄰接矩陣存儲(chǔ)），最后我們要知道克魯斯卡爾算法的時(shí)間復(fù)雜度是主要由排序方法決定的，其排序方法只與網(wǎng)中邊的條數(shù)有關(guān)，而與網(wǎng)中頂點(diǎn)的個(gè)數(shù)無關(guān)，當(dāng)使用時(shí)間復(fù)雜度為O（elog2e）的排序方法時(shí)，克魯斯卡爾算法的時(shí)間復(fù)雜度即為O（log2e），因此當(dāng)網(wǎng)的頂點(diǎn)個(gè)數(shù)較多、而邊的條數(shù)較少時(shí)，使用克魯斯卡爾算法構(gòu)造最小生成樹效果較好。

結(jié)語

本文參考《數(shù)據(jù)結(jié)構(gòu)》–上海交大
如有錯(cuò)誤，歡迎指正！

總結(jié)

以上是生活随笔為你收集整理的数据结构题：克鲁斯卡尔（Kruscal）算法求最小生成树的全部內(nèi)容，希望文章能夠幫你解決所遇到的問題。

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