Prim的邻接表表示的MST
它类似于先前的算法。这里唯一的区别是，图G(V,E)用邻接表表示。
时间复杂度邻接表的表示形式为O（ElogV）。
输入输出
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