資料結構
網路
RDBMS
作業系統
Java
MS Excel
iOS
HTML
CSS
安卓
Python
C 程式設計
C++
C#
MongoDB
MySQL
Javascript
PHP
物理
化學
生物
數學
英語
經濟
心理學
社會學科
時尚學科
法律學科普里姆最小生成樹演算法
有一個連通圖 G(V, E)，並且給出了每條邊的權重或成本。普里姆演算法將找到圖 G 的最小生成樹。
這是一種不斷發展的樹的方法。此演算法需要一個種子值來開始該樹。種子頂點不斷增長，形成整個樹。
該問題將使用兩個集合來解決。一個集合包含已選擇的節點，另一個集合則包含尚未考慮的專案。它從種子頂點開始，根據最小邊成本，採用相鄰頂點，因此它透過逐個選取節點來發展樹。
此問題的複雜度為 O(V^2)。其中 V 是頂點數。
輸入和輸出
Input: The adjacency list:Output: (0)---(1|1) (0)---(2|3) (0)---(3|4) (1)---(0|1) (1)---(4|2) (2)---(0|3) (3)---(0|4) (4)---(1|2) (4)---(5|2) (5)---(4|2) (5)---(6|3) (6)---(5|3)
演算法
prims(g: Graph, t: tree, start)
輸入 − 圖形 g、一個空白樹和一個名為“start”的種子頂點
輸出 − 新增邊後的樹。
Begin define two sets as usedVert, unusedVert usedVert[0] := start and unusedVert[0] := φ for all vertices except start do usedVert[i] := φ unusedVert[i] := i //add all vertices in unused list done while number of vertices in usedVert ≠ V do //V is number of total nodes min := ∞ for all vertices of usedVert array do for all vertices of the graph do if min > cost[i,j] AND i ≠ j then min := cost[i,j] ed := edge between i and j, and cost of ed := min done done unusedVert[destination of ed] := φ add edge ed into the tree t add source of ed into usedVert done End
範例
#include<iostream>
#define V 7
#define INF 999
using namespace std;
//Cost matrix of the graph
int costMat[V][V] = {
{0, 1, 3, 4, INF, 5, INF},
{1, 0, INF, 7, 2, INF, INF},
{3, INF, 0, INF, 8, INF, INF},
{4, 7, INF, 0, INF, INF, INF},
{INF, 2, 8, INF, 0, 2, 4},
{5, INF, INF, INF, 2, 0, 3},
{INF, INF, INF, INF, 4, 3, 0}
};
typedef struct {
int u, v, cost;
}edge;
class Tree {
int n;
edge edges[V-1]; //as a tree has vertex-1 edges
public:
Tree() {
n = 0;
}
void addEdge(edge e) {
edges[n] = e; //add edge e into the tree
n++;
}
void printEdges() { //print edge, cost and total cost
int tCost = 0;
for(int i = 0; i<n; i++) {
cout << "Edge: " << char(edges[i].u+'A') << "--" << char(edges[i].v+'A');
cout << " And Cost: " << edges[i].cost << endl;
tCost += edges[i].cost;
}
cout << "Total Cost: " << tCost << endl;
}
friend void prims(Tree &tre, int start);
};
void prims(Tree &tr, int start) {
int usedVert[V], unusedVert[V];
int i, j, min, p;
edge ed;
//initialize
usedVert[0] = start; p = 1;
unusedVert[0] = -1; //-1 indicates the place is empty
for(i = 1; i<V; i++) {
usedVert[i] = -1; //all places except first is empty
unusedVert[i] = i; //fill with vertices
}
tr.n = 0;
//get edges and add to tree
while(p != V) { //p is number of vertices in usedVert array
min = INF;
for(i = 0; i<p; i++) {
for(j = 0; j<V; j++) {
if(unusedVert[j] != -1) {
if(min > costMat[i][j] && costMat[i][j] != 0) {
//find the edge with minimum cost
//such that u is considered and v is not considered yet
min = costMat[i][j];
ed.u = i; ed.v = j; ed.cost = min;
}
}
}
}
unusedVert[ed.v] = -1; //delete v from unusedVertex
tr.addEdge(ed);
usedVert[p] = ed.u; p++; //add u to usedVertex
}
}
main() {
Tree tr;
prims(tr, 0); //starting node 0
tr.printEdges();
}輸出
(0)---(1|1) (0)---(2|3) (0)---(3|4) (1)---(0|1) (1)---(4|2) (2)---(0|3) (3)---(0|4) (4)---(1|2) (4)---(5|2) (5)---(4|2) (5)---(6|3) (6)---(5|3)
更新於: 2020-06-15
2K+ 瀏覽量
廣告