文章目錄
- 定義
- 解決問題類型
- 基本算法
-
- 1、Prime算法---“加點法”
- 2、Kruskal算法---“加邊法”
- 代碼(2個):
定義
給定一張圖,圖中有許多的節點還有許多長度不同的邊将這些點點互相連接配接(連通網),找出連接配接所有點的最短方式就是最小生成樹,可以證明,這樣一種最小的情況是不會出現環的,由于所有的無環圖都可以看作樹,是以成為最小生成樹。
解決問題類型
因為是求最小的,一般是修路問題(代價最小且連接配接所有點)。
基本算法
1、Prime算法—“加點法”
主要步驟:
1.将圖儲存鄰接矩陣之中(便于通路是否鄰接);
2.任選一點作為起始點;
3.将此點加入到已确定點集之中;
4.依此點為原點,更新與之相關聯的節點到點集的距離(最小);
5. 選中剩餘點中距離點集最近的點,加入點集,并以其為原點更新和他相鄰接的點的距離;
6. 循環,直到點集中有n個點為止。
圖形表示:以下來源為這位大大(通俗易懂)
原圖為:
1.首先先找一個點,把這個點看成一個集合
2.找與這個點最近的一個點,也就是找與這個集合最近的一個點,由圖可知與1點相鄰的有2,3,4三個點,但最近的是2點,并且2點沒在已選的集合中,是以把2點加到已選的集合中。
3.現在1和2是在已選的集合中,然後再找與已選集合最近的點,其中相鄰的有3,4,5三個點,但最近的隻有點4,是以把4點加到已選集合中。
4.然後再找與已選集合最近的點,以此類推下個點為3
6.再下個點為6
7.最後一個點為5,選完所有點後結束
(經過六個圖形描述,最後一個自己動手畫吧~~~)
2、Kruskal算法—“加邊法”
算法思路:
(1)将圖中的所有邊都去掉。
(2)将邊按權值從小到大的順序添加到圖中,保證添加的過程中不會形成環
(3)重複上一步直到連接配接所有頂點,此時就生成了最小生成樹。這是一種貪心政策。
主要步驟:
1.将圖儲存在臨接矩陣之中(便于通路是否鄰接);
2先把所有的路徑進行排序;
3.先選一天路徑最小的邊然後判斷這兩個點是否在同一個集合中,如果沒有就把這兩個點加到一個集合中;
4.然後依次找路徑最小的邊,并判斷這條邊上的兩個點是否在同一個集合中,如果沒在同一個集合中且這兩個點沒有都被标記過,就把這兩個點合到同一個集合中;
5.循環來找,直到點找完為止。
圖形表示:
代碼(2個):
/************************************************************************
CSDN 勿在浮沙築高台 http://blog.csdn.net/luoshixian099算法導論--最小生成樹(Prim、Kruskal)2016年7月14日
************************************************************************/
#include <iostream>
#include <vector>
#include <queue>
#include <algorithm>
using namespace std;
#define INFINITE 0xFFFFFFFF
#define VertexData unsigned int //頂點資料
#define UINT unsigned int
#define vexCounts 6 //頂點數量
char vextex[] = { 'A', 'B', 'C', 'D', 'E', 'F' };
struct node
{
VertexData data;
unsigned int lowestcost;
}closedge[vexCounts]; //Prim算法中的輔助資訊
typedef struct
{
VertexData u;
VertexData v;
unsigned int cost; //邊的代價
}Arc; //原始圖的邊資訊
void AdjMatrix(unsigned int adjMat[][vexCounts]) //鄰接矩陣表示法
{
for (int i = 0; i < vexCounts; i++) //初始化鄰接矩陣
for (int j = 0; j < vexCounts; j++)
{
adjMat[i][j] = INFINITE;
}
adjMat[0][1] = 6; adjMat[0][2] = 1; adjMat[0][3] = 5;
adjMat[1][0] = 6; adjMat[1][2] = 5; adjMat[1][4] = 3;
adjMat[2][0] = 1; adjMat[2][1] = 5; adjMat[2][3] = 5; adjMat[2][4] = 6; adjMat[2][5] = 4;
adjMat[3][0] = 5; adjMat[3][2] = 5; adjMat[3][5] = 2;
adjMat[4][1] = 3; adjMat[4][2] = 6; adjMat[4][5] = 6;
adjMat[5][2] = 4; adjMat[5][3] = 2; adjMat[5][4] = 6;
}
int Minmum(struct node * closedge) //傳回最小代價邊
{
unsigned int min = INFINITE;
int index = -1;
for (int i = 0; i < vexCounts;i++)
{
if (closedge[i].lowestcost < min && closedge[i].lowestcost !=0)
{
min = closedge[i].lowestcost;
index = i;
}
}
return index;
}
void MiniSpanTree_Prim(unsigned int adjMat[][vexCounts], VertexData s)
{
for (int i = 0; i < vexCounts;i++)
{
closedge[i].lowestcost = INFINITE;
}
closedge[s].data = s; //從頂點s開始
closedge[s].lowestcost = 0;
for (int i = 0; i < vexCounts;i++) //初始化輔助數組
{
if (i != s)
{
closedge[i].data = s;
closedge[i].lowestcost = adjMat[s][i];
}
}
for (int e = 1; e <= vexCounts -1; e++) //n-1條邊時退出
{
int k = Minmum(closedge); //選擇最小代價邊
cout << vextex[closedge[k].data] << "--" << vextex[k] << endl;//加入到最小生成樹
closedge[k].lowestcost = 0; //代價置為0
for (int i = 0; i < vexCounts;i++) //更新v中頂點最小代價邊資訊
{
if ( adjMat[k][i] < closedge[i].lowestcost)
{
closedge[i].data = k;
closedge[i].lowestcost = adjMat[k][i];
}
}
}
}
void ReadArc(unsigned int adjMat[][vexCounts],vector<Arc> &vertexArc) //儲存圖的邊代價資訊
{
Arc * temp = NULL;
for (unsigned int i = 0; i < vexCounts;i++)
{
for (unsigned int j = 0; j < i; j++)
{
if (adjMat[i][j]!=INFINITE)
{
temp = new Arc;
temp->u = i;
temp->v = j;
temp->cost = adjMat[i][j];
vertexArc.push_back(*temp);
}
}
}
}
bool compare(Arc A, Arc B)
{
return A.cost < B.cost ? true : false;
}
bool FindTree(VertexData u, VertexData v,vector<vector<VertexData> > &Tree)
{
unsigned int index_u = INFINITE;
unsigned int index_v = INFINITE;
for (unsigned int i = 0; i < Tree.size();i++) //檢查u,v分别屬于哪顆樹
{
if (find(Tree[i].begin(), Tree[i].end(), u) != Tree[i].end())
index_u = i;
if (find(Tree[i].begin(), Tree[i].end(), v) != Tree[i].end())
index_v = i;
}
if (index_u != index_v) //u,v不在一顆樹上,合并兩顆樹
{
for (unsigned int i = 0; i < Tree[index_v].size();i++)
{
Tree[index_u].push_back(Tree[index_v][i]);
}
Tree[index_v].clear();
return true;
}
return false;
}
void MiniSpanTree_Kruskal(unsigned int adjMat[][vexCounts])
{
vector<Arc> vertexArc;
ReadArc(adjMat, vertexArc);//讀取邊資訊
sort(vertexArc.begin(), vertexArc.end(), compare);//邊按從小到大排序
vector<vector<VertexData> > Tree(vexCounts); //6棵獨立樹
for (unsigned int i = 0; i < vexCounts; i++)
{
Tree[i].push_back(i); //初始化6棵獨立樹的資訊
}
for (unsigned int i = 0; i < vertexArc.size(); i++)//依次從小到大取最小代價邊
{
VertexData u = vertexArc[i].u;
VertexData v = vertexArc[i].v;
if (FindTree(u, v, Tree))//檢查此邊的兩個頂點是否在一顆樹内
{
cout << vextex[u] << "---" << vextex[v] << endl;//把此邊加入到最小生成樹中
}
}
}
int main()
{
unsigned int adjMat[vexCounts][vexCounts] = { 0 };
AdjMatrix(adjMat); //鄰接矩陣
cout << "Prim :" << endl;
MiniSpanTree_Prim(adjMat,0); //Prim算法,從頂點0開始.
cout << "-------------" << endl << "Kruskal:" << endl;
MiniSpanTree_Kruskal(adjMat);//Kruskal算法
return 0;
}