目錄
0.構造連通網的最小代價生成樹（Minimun Cost Spanning Tree)，簡稱最小生成樹。
1.求UDN的最小生成樹Prim算法
2.Kruscal算法
2.1樹的存儲結構之雙親表示法
2.2樹與等價問題：集合的樹型結構表示：查找某個元素屬于哪一個子集，合并兩個非空子集；等價類劃分
2.3求UDN的最小生成樹之Kruscal算法
小結：
1.Prim算法使用了帶權無向圖（網）的鄰接矩陣存儲結構，輔助數組closedge的使用是關鍵！
2.Kruskal算法就較為難實作：要掌握好樹的雙親表示法，用雙親表示法去實作集合的樹型表示，并實作幾個集合的操作！
另外要依據執行個體記錄什麼是等價問題，怎麼劃分等價類？樹與等價類問題的關系！具體到圖中就是區分結點屬于哪一個連通分量！
3.Prim算法的時間複雜度O(n*n);Kruckal算法的時間複雜度O(eloge)，，其中n為圖頂點個數，e為圖中邊的條數
0.構造連通網的最小代價生成樹（Minimun Cost Spanning Tree)，簡稱最小生成樹。
MST性質：
設N=（V，{E})是一個連通網絡，U是頂點集合V的一個非空子集。若(u,v)是一條具有最小權值（代價)的邊，其中u屬于U，
v屬于V-U，則必存在一棵包含邊(u,v)的最小生成樹。
1.求UDN的最小生成樹Prim算法
設N=（V，{E}）是連通網，TE是N上最小生成樹中邊的集合(Tree Edge)。
Prim算法從U={u0}（u0屬于V）,TE={}(空集合）開始，重複執行下列操作：
在所有u(u屬于U），v（v屬于V-U)的邊(u,v) ((u,v)屬于E）中找一條代價最小的邊(u0,v0)并入集合TE,
同時v0并入U，
直至U=V為止。
此時TE中必有n-1條邊，則T=(V,{TE})為N的最小生成樹。
圖的存儲結構之數組表示法：
#define INFINITE INT_MAX
#define MAX_VERTEX_NUM 6
#define VRType int
#define VertexType int
typedef struct ArcCell{
VRType adj;
}ArcCell, AdjMatrix[MAX_VERTEX_NUM][MAX_VERTEX_NUM];
typedef struct{
VertexType vexs[MAX_VERTEX_NUM];
AdjMatrix arcs;
int vexnum, arcnum;
}MGraph;
//sizeof(MGraph) = 176 44*4=176
會采用數組（鄰接矩陣）表示法，構造無向網UDN：
#define INFINITE INT_MAX
#define MAX_VERTEX_NUM 6
#define VRType int
#define VertexType int
typedef struct ArcCell{
VRType adj;
}ArcCell, AdjMatrix[MAX_VERTEX_NUM][MAX_VERTEX_NUM];
//AdjMatrix[MAX_VERTEX_NUM][MAX_VERTEX_NUM];可以了解這個為ArcCell類型的二維結構體數組，數組的次元是指定好的！
//數組名AdjMatrix就是ArcCell類型的二維結構體數組的指針類型！
typedef struct{
VertexType vexs[MAX_VERTEX_NUM];
AdjMatrix arcs;
int vexnum, arcnum;
}MGraph;
//sizeof(MGraph) = 176 44*4=176
下面代碼構造無向網UDN：
bool CreateUDN(MGraph& G)
{
cin >> G.vexnum >> G.arcnum;
for (int i = 0; i < G.vexnum; i++)
{
//cin >> G.vexs[i];
G.vexs[i] = i;
}
//初始化鄰接矩陣
for (int i = 0; i < G.vexnum; i++)
{
for (int j = 0; j < G.vexnum; j++)
{
G.arcs[i][j] = { INFINITE };
}
}
//構造鄰接矩陣，輸入一條邊依附的頂點及權值
for (int k = 0; k < G.arcnum; k++)
{
int v1, v2, w;//輸入一條邊依附的頂點及權值
cin >> v1 >> v2 >> w;
G.arcs[v1-1][v2-1].adj = w;
G.arcs[v2-1][v1-1].adj = w;//設定<v1,v2>的對弧<v2,v1>
}
return true;
}//CreateUDN
Prim算法實作時的輔助數組：closedge:
typedef struct{
VertexType adjvex;
VRType lowcost;
}ClosEdge[MAX_VERTEX_NUM];
下面為Prim算法實作：
Prim算法的關鍵就是通過輔助數組closedge中元素中lowcost分量值是否為0來區分該節點是否是屬于U，還是屬于V-U；
第二個循環過程就是在closedge中查找lowcost分量最小的值，找到後并更新closedge數組的過程！
其中查找lowcost最小的代碼在函數miniEdge()中實作：
int mimiEdge(ClosEdge& closedge)
{//在數組closedge中找分量lowcost>0且最小的那個元素
VRType mini = INT_MAX;
int index;
for (int i = 0; i < MAX_VERTEX_NUM; i++)
{
if (closedge[i].lowcost >0 && closedge[i].lowcost < mini)
{
mini = closedge[i].lowcost;
index = i;
}
}
return index;
}
void MiniSpanTree_Prim(MGraph G, VertexType u, ClosEdge& closedge)
{
int k = u-1;//k=LocateVex(u);
for (int j = 0; j < G.vexnum; j++)
{
closedge[j] = { k, G.arcs[k][j].adj };
}
closedge[k].lowcost = 0;
for (int i = 1; i < G.vexnum; i++)
{
int k = mimiEdge(closedge);
cout << closedge[k].adjvex +1<< "->" << G.vexs[k] +1<< endl;//輸出生成樹的邊
closedge[k].lowcost = 0;
for (int j = 0; j < G.vexnum; j++)
{//更新closedge數組
if (G.arcs[k][j].adj < closedge[j].lowcost)
{
closedge[j] = { G.vexs[k], G.arcs[k][j].adj };
}
}
}
}//MiniSpanTree_Prim
下面是測試代碼：
int _tmain(int argc, _TCHAR* argv[])
{
MGraph G;
cout << "sizeof(MGraph)=" << sizeof(MGraph) << endl;//sizeof(MGraph)=176
CreateUDN(G);
ClosEdge closedge;
MiniSpanTree_Prim(G, 6, closedge);
system("pause");
return 0;
}
輸入輸出：
輸入輸出：（注：輸入的頂點下标都是從1計起，即V1的下标就是1，而在程式裡存儲的下标都是0計起
輸出的頂點也為了友善閱讀，下标從1計起，即V1的編号為1
6 10
1 2 6
1 3 1
1 4 5
2 3 5
3 4 5
2 5 3
3 5 6
3 6 4
4 6 2
5 6 6
1->3
3->6
6->4
3->2
2->5
請按任意鍵繼續. . .
2.Kruscal算法
2.1樹的存儲結構之雙親表示法
2.2樹與等價問題：集合的樹型結構表示：查找某個元素屬于哪一個子集，合并兩個非空子集；等價類劃分
2.3求UDN的最小生成樹之Kruscal算法
首先構造樹的雙親表示法：（這裡的樹是廣義樹，不僅是二叉樹）
樹結點（頂點）;
typedef struct PTNode{
int No; //頂點編号
int parent;//該結點雙親的位置域
}PTNode;
下面的PTree類提供了依照樹的雙親表示法，得到的幾個的樹型結點表示法，并提供了構造函數，析構函數，元素屬于哪一個子集的查找函數fix_mfser()和兩個非空子集的合并函數mix_mfset()以及，判斷兩個頂點是否屬于同一集合（同一連通分量）的函數isEqualClass():
//typedef PTree MFSet;
class PTree{
public:
vector<PTNode*> nodes;
int root;//根的位置
int n; //結點數目
PTree(int vexNum)
{
n = vexNum;
for (int i = 0; i < n; i++)
{
PTNode* ptnodePtr = new PTNode;
ptnodePtr->No = i;
ptnodePtr->parent = -1;
nodes.push_back(ptnodePtr);
}
}
~PTree()
{
for (int i = 0; i < n; i++)
{
delete nodes[i];
nodes[i] = nullptr;
}
}
int fix_mfset(int i)//查找i所在子集合
{//确定i所在子集合，并把從i至根路徑上是以結點都變成根的孩子結點
if (i<0 || i>n-1)
{
return -1;
}
int j, k,t;
for (j = i; nodes[j]->parent >= 0; j = nodes[j]->parent);//注意：下标從0計算起，是以nodes[j]->parent >= 0
for (k = i; k != j; k = t)
{
t = nodes[k]->parent;
nodes[k]->parent = j;
}
return j;
}
void mix_mfset(int i, int j)
{//nodes[i]和node[j]分别為集合S的互不相交的兩個子集Si和Sj的根結點。
if (i<0 || i>n-1 || j<0 || j>n-1)
{
throw new std::invalid_argument("mix_mfset()參數錯誤");
}
if (nodes[i]->parent > nodes[j]->parent)
{
nodes[j]->parent += (nodes[i]->parent);
nodes[i]->parent = j;
}
else
{
nodes[i]->parent += (nodes[j]->parent);
nodes[j]->parent = i;
}
}
bool isEqualClass(int i, int j)
{
return (fix_mfset(i) == fix_mfset(j));
}
};
下面是無向網邊的結構定義：
typedef struct Edge{
int vex1, vex2;
int weight;
}Edge;
下面是無向網類的定義:
class UDN
{
public:
int vexnum, arcnum;
//vector<Vex*> vexPtrVec;
PTree* ptree;
vector<Edge*> edgePtrVec;
priority_queue<Edge*, vector<Edge*>, edgePtrQueue_SortRule> edgePtrQueue;
//優先隊列内部自動用堆排序，使用top()、pop()函數實作元素的有序輸出！存儲結構時樹（堆）的存儲結構
void printEdgeWeight(priority_queue<Edge*, vector<Edge*>, edgePtrQueue_SortRule> edgePtrQueue)
{
for (int i = 0; i < arcnum; i++)
{
Edge* edge = edgePtrQueue.top();
edgePtrQueue.pop();
cout << edge->weight << " ";
}
cout << endl;
}
bool CreateUDN()
{
cin >> vexnum >> arcnum;
ptree = new PTree(vexnum);
//for (int i = 0; i < udn.vexnum; i++)
//{//這裡可以輸入每個頂點的資訊！
//}
for (int i = 0; i < arcnum; i++)
{
int v1, v2, w;
cin >> v1 >> v2 >> w;
Edge* edgePtr = new Edge;
edgePtr->vex1 = v1 - 1;
edgePtr->vex2 = v2 - 1;
edgePtr->weight = w;
edgePtrVec.push_back(edgePtr);
edgePtrQueue.push(edgePtr);
}
return true;
}
bool DestroyUDN()
{
delete ptree;
ptree = nullptr;
for (int i = 0; i < arcnum; i++)
{
delete edgePtrVec[i];
}
edgePtrVec.clear();
//delete &udn;//這條語句報錯！
return true;
}
vector<Edge*> MiniSpanTree_Kruscal()
{//miniTree裡存儲最小生成樹的邊邊集合的指針
vector<Edge*> miniSpanTree;
while ( !edgePtrQueue.empty())
{
Edge* edge = edgePtrQueue.top();
edgePtrQueue.pop();
int v1, v2;
v1 = edge->vex1;
v2 = edge->vex2;
//if (!ptree->isEqualClass(v1, v2))
//{//這裡有一個合并集合時概念的錯誤！，下面進行糾正！
// ptree->mix_mfset(v1, v2);//不是合并v1和v2這兩個結點！，
// miniSpanTree.push_back(edge);
//}
if (!ptree->isEqualClass(v1, v2))
{
ptree->mix_mfset(ptree->fix_mfset(v1), ptree->fix_mfset(v2));//而是合并v1和v2所屬集合的根節點！合并的時候通過根節點進行合并！
miniSpanTree.push_back(edge);
}
}
return miniSpanTree;
}
void printMiniSpanTree(vector<Edge*> edgeVec)
{
for (int i = 0; i < edgeVec.size(); i++)
{
cout << edgeVec[i]->vex1 + 1 << "->" << edgeVec[i]->vex2 + 1 << endl;
}
}
};
UDN類中有一個存儲邊的指針的優先隊列，起排序規則如下仿函數：即依據邊的權值升序排序：
class edgePtrQueue_SortRule
{//邊的權值優先隊列排序規則類(仿函數）
public:
bool operator()(Edge* e1, Edge* e2)
{
return (e1->weight > e2->weight);
}
};
UDN類中提供了構造無向網：CreateUDN()、析構無向網DestroyUDN()
和利用kruskal算法求該無向網的最小生成樹的方法：vector<Edge*> MiniSpanTree_Kruscal()
以及列印所得最小生成樹邊的方法：void printMiniSpanTree(vector<Edge*> edgeVec)
下面是測試結果：
#include "stdafx.h"
#include<iostream>
#include<vector>
#include<queue>
using namespace std;
int _tmain(int argc, _TCHAR* argv[])
{
UDN udn;
udn.CreateUDN();
//udn.printEdgeWeight(udn.edgePtrQueue);
vector<Edge*> miniSpanTreeEdge;
miniSpanTreeEdge = udn.MiniSpanTree_Kruscal();
udn.printMiniSpanTree(miniSpanTreeEdge);
miniSpanTreeEdge.clear();
udn.DestroyUDN();
system("pause");
return 0;
}
輸入輸出：
輸入輸出：
6 10
1 2 6
1 3 1
1 4 5
2 3 5
3 4 5
2 5 3
3 5 6
3 6 4
4 6 2
5 6 6
1->3
4->6
2->5
3->6
2->3
請按任意鍵繼續. . .
參考資料：
[1]//參考《資料結構C語言版（第三版）P176 Kruskal算法和 P139樹與等價問題，樹的雙親表示法，集合的樹型結構表示，集合的并操作，元素屬于哪一個集合的查找操作！
帶權圖的最小生成樹
Prim算法
Kruskal算法
樹與等價類問題
小結：
1.Prim算法使用了帶權無向圖（網）的鄰接矩陣存儲結構，輔助數組closedge的使用是關鍵！
2.Kruskal算法就較為難實作：要掌握好樹的雙親表示法，用雙親表示法去實作集合的樹型表示，并實作幾個集合的操作！
另外要依據執行個體記錄什麼是等價問題，怎麼劃分等價類？樹與等價類問題的關系！具體到圖中就是區分結點屬于哪一個連通分量！