数据结构
网络
RDBMS
操作系统
Java
MS Excel
iOS
HTML
CSS
Android
Python
C 编程
C++
C#
MongoDB
MySQL
JavaScript
PHP
物理学
化学
生物学
数学
英语
经济学
心理学
社会科学
时尚学
法律学邻接表表示下的 Prim 最小生成树
与之前的算法类似。这里唯一的区别是，图 G(V, E) 由邻接表表示。
邻接表表示的时间复杂度是 O(E log V)。
输入和输出
Input: The cost matrix:Output: Edge: A--B And Cost: 1 Edge: B--E And Cost: 2 Edge: A--C And Cost: 3 Edge: A--D And Cost: 4 Edge: E--F And Cost: 2 Edge: F--G And Cost: 3 Total Cost: 15
算法
prims(g: Graph, start)
输入− 图 g 和称为“start”的种子顶点
输出 − 添加边之后的树。
Begin create two set B, N add the start node in B set. for all vertices u in graph g do add u in the set N done while B ≠ N do min := ∞ for all vertices u in graph g do if u is in the set B then for all vertices v which are adjacent with u do if v is in (N – B) then if min > cost of uv edge then min := cost of uv edge parent := u node := v done done insert node in the B set add the edge starting from parent to node in the tree done return the tree End
示例
#include<iostream>
#include<list>
#include<set>
using namespace std;
typedef struct nodes {
int dest;
int cost;
}node;
class Graph {
int n;
list<node> *adjList;
private:
void showList(int src, list<node> lt) {
list<node> :: iterator i;
node tempNode;
for(i = lt.begin(); i != lt.end(); i++) {
tempNode = *i;
cout << "(" << src << ")---("<<tempNode.dest << "|"<<tempNode.cost<<") ";
}
cout << endl;
}
public:
Graph() {
n = 0;
}
Graph(int nodeCount) {
n = nodeCount;
adjList = new list<node>[n];
}
void addEdge(int source, int dest, int cost) {
node newNode;
newNode.dest = dest;
newNode.cost = cost;
adjList[source].push_back(newNode);
}
void displayEdges() {
for(int i = 0; i<n; i++) {
list<node> tempList = adjList[i];
showList(i, tempList);
}
}
friend Graph primsMST(Graph g, int start);
};
set<int> difference(set<int> first, set<int> second) {
set<int> :: iterator it;
set<int> res;
for(it = first.begin(); it != first.end(); it++) {
if(second.find(*it) == second.end())
res.insert(*it); //add those item which are not in the second list
}
return res; //the set (first-second)
}
Graph primsMST(Graph g, int start) {
int n = g.n;
set<int> B, N, diff;
Graph tree(n); //make tree with same node as graph
B.insert(start); //insert start node in the B set
for(int u = 0; u<n; u++) {
N.insert(u); //add all vertices in the N set
}
while(B != N) {
int min = 9999; //set as infinity
int v, par;
diff = difference(N, B); //find the set N - B
for(int u = 0; u < n; u++) {
if(B.find(u) != B.end()) {
list<node>::iterator it;
for(it = g.adjList[u].begin(); it != g.adjList[u].end(); it++) {
if(diff.find(it->dest) != diff.end()) {
if(min > it->cost) {
min = it->cost; //update cost
par = u;
v = it->dest;
}
}
}
}
}
B.insert(v);
tree.addEdge(par, v, min);
tree.addEdge(v, par, min);
}
return tree;
}
main() {
Graph g(7), tree(7);
g.addEdge(0, 1, 1);
g.addEdge(0, 2, 3);
g.addEdge(0, 3, 4);
g.addEdge(0, 5, 5);
g.addEdge(1, 0, 1);
g.addEdge(1, 3, 7);
g.addEdge(1, 4, 2);
g.addEdge(2, 0, 3);
g.addEdge(2, 4, 8);
g.addEdge(3, 0, 4);
g.addEdge(3, 1, 7);
g.addEdge(4, 1, 2);
g.addEdge(4, 2, 8);
g.addEdge(4, 5, 2);
g.addEdge(4, 6, 4);
g.addEdge(5, 0, 5);
g.addEdge(5, 4, 2);
g.addEdge(5, 6, 3);
g.addEdge(6, 4, 4);
g.addEdge(6, 5, 3);
tree = primsMST(g, 0);
tree.displayEdges();
}输出
Edge: A--B And Cost: 1 Edge: B--E And Cost: 2 Edge: A--C And Cost: 3 Edge: A--D And Cost: 4 Edge: E--F And Cost: 2 Edge: F--G And Cost: 3 Total Cost: 15
更新于： 15-6-2020
2K+ 浏览次数
广告