DS图-最小生成树
复习数据结构打OJ顺便梳理一下Prim和Kruskal求最小生成树的思路
题目描述
根据输入创建无向网。分别用Prim算法和Kruskal算法构建最小生成树。（假设：输入数据的最小生成树唯一。）
输入
顶点数n\
n个顶点\
边数m\
m条边信息,格式为：顶点1顶点2权值\
Prim算法的起点v
6\
v1 v2 v3 v4 v5 v6 \
10\
v1 v2 6\
v1 v3 1\
v1 v4 5\
v2 v3 5\
v2 v5 3\
v3 v4 5\
v3 v5 6\
v3 v6 4\
v4 v6 2\
v5 v6 6\
v1输出
输出最小生成树的权值之和\
对两种算法，按树的生长顺序，输出边信息(Kruskal中边顶点按数组序号升序输出)
15\
prim:\
v1 v3 1\
v3 v6 4\
v6 v4 2\
v3 v2 5\
v2 v5 3\
kruskal:\
v1 v3 1\
v4 v6 2\
v2 v5 3\
v3 v6 4\
v2 v3 5
实现思路
Prim
- 维护一个数组dis，表示节点到最小生成树直接距离（有相邻节点在最小生成树中，否则为正无穷，初始为正无穷），已放到最小生成树中则为0。
当有相邻节点被放入最小生成树中，且与该节点直接距离小于原本dis数组中保存的值时，更新dis中的值
- 维护一个数组parent，表示节点与最小生成树相连时，直接连接的另一节点
无需初始化，当dis更新时同步更新parent
- 从起点开始，初始化各点的dis值为各点到起点的直接距离（如有），同时更新parent值也为起点，将起点放入最小生成树（dis值设为0）。
- 进入循环，每次取出dis值最小且非0的节点，将该节点与其父节点相连的边纳入最小生成树，并更新相邻节点的dis值和parent值。当最小生成树的边为节点数-1时退出循环
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34Edge* Prim(const string& start){
int startIndex = strToIndex(start);
for(int i=0;i<n;++i)
dis[i] = INF;
dis[startIndex] = 0; //将起点放入最小生成树（dis值设为0）。
for(int i=0;i<n;++i){
if(mat[i][startIndex]){
dis[i] = mat[i][startIndex]; //初始化各点的dis值为各点到起点的直接距离（如有）
parent[i] = startIndex; //同时更新parent值也为起点，
}
}
Edge *mst = new Edge[n-1];
int cnt = 0;
while(cnt != n-1){//当最小生成树的边为节点数-1时退出循环
//每次取出dis值最小且非0的节点
int minIndex, min = INF;
for(int i=0;i<n;++i){
if(dis[i] && dis[i] < min)
minIndex = i, min = dis[i];
}
//将该节点与其父节点相连的边纳入最小生成树
mst[cnt++] = Edge(parent[minIndex], minIndex, min);
dis[minIndex] = 0;
//更新相邻节点的dis值和parent值
for(int i=0;i<n;++i){
if(mat[i][minIndex] && mat[i][minIndex] < dis[i]){
dis[i] = mat[i][minIndex];
parent[i] = minIndex;
}
}
}
return mst;
}Kruscal
- 维护一个优先队列pq，在初始化边的时候将每一条边放入优先队列，边的权值越小越靠前。
- 维护一个并查集set，当有边被纳入最小生成树时，将该边两点作并操作。一条边的两个点在同一集合中时,说明再将该边纳入最小生成树会使树成环，故丢弃该边。
- 进入循环，每次循环取出pq的队头（未纳入最小生成树的最短的一条边），判断该边是否合法（是否会使最小生成树成环），合法则将其纳入最小生成树，否则丢弃。当最小生成树的边为节点数-1时退出循环
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35//并查集
struct Set{
int *parent;
Set(int range){
parent = new int[range];
for(int i=0;i<range;++i)
parent[i] = -1;
}
void join(int a, int b){
parent[a] = b;
}
int root(int a){
if(parent[a] == -1)
return a;
else
return root(parent[a]);
}
bool is_same(int a, int b){
return root(a) == root(b);
}
};
//Kruskal
Edge *Kruskal(){
Edge *mst = new Edge[n-1];
int cnt = 0;
while(!pq.empty() && cnt != n-1){
Edge temp = pq.top();
pq.pop();
if(!set->is_same(temp.index1, temp.index2)){
mst[cnt++] = temp;
set->join(temp.index1, temp.index2);
}
}
return mst;
}
处理输入输出
- 节点：string类型数组nodes保存所有节点，下标表示节点的id，方便用二维数组表示节点间的权值
- 最小生成树：自定义Edge类型表示一条边，成员变量int index1, index2, val 分别表示边的两个端点下标及边的权重。最小生成树为Edge类型的数组，即一组边。
- int类型二维数组mat(matrix)保存保存节点间的权值(Prim中用于更新dis数组)\
Edge类型数组保存输入的每一条边，在初始化时push到优先队列中(Kruskal中用于贪心)1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
//图
class Graph{
public:
string nodes[MAX];
//用于Prim算法的mat二维数组，dis数组和parent数组
int mat[MAX][MAX];
int dis[MAX];
int parent[MAX];
//用于Kruskal算法的最小堆（优先队列）和并查集
priority_queue<Edge> pq;
Set *set;
int n, m;
void init(){
// init nodes
std::cin>>n;
for(int i=0;i<n;++i)
std::cin>>nodes[i];
//init edges
memset(mat, 0, sizeof(mat));
std::cin>>m;
string node1, node2;
int val;
for(int i=0;i<m;++i){
std::cin>>node1>>node2>>val;
int index1 = strToIndex(node1), index2 = strToIndex(node2);
/初始化mat二维数组
mat[index1][index2] = val;
mat[index2][index1] = val;
//初始化优先队列
pq.push(Edge(index1, index2, val));
}
// init union-find-set
set = new Set(n);
}
int strToIndex(const string &str){
//找到字符串对应id
for(int i=0;i<n;++i)
if(str == nodes[i])
return i;
return -1;
}
Edge* Prim(const string& start){
//上面已实现
}
Edge *Kruskal(){
//上面已实现
}
void FindMST(const string &start){
Edge *mst1 = Prim(start);
int sum = 0;
for(int i=0;i<n-1;++i)
sum += mst1[i].val;
std::cout<<sum<<std::endl;
std::cout<<"prim:"<<std::endl;
for(int i=0;i<n-1;++i){
std::cout<<nodes[mst1[i].index1]<<" "
<<nodes[mst1[i].index2]<<" "
<<mst1[i].val<<std::endl;
}
std::cout<<"kruskal:"<<std::endl;
Edge *mst2 = Kruskal();
for(int i=0;i<n-1;++i){
std::cout<<nodes[mst2[i].index1]<<" "
<<nodes[mst2[i].index2]<<" "
<<mst2[i].val<<std::endl;
}
}
}
int main() {
Graph *graph = new Graph;
graph->init();
string start;
std::cin>>start;
graph->FindMST(start);
return 0;
}