问题描述
设G = (V, E)是一个无向连通带权图，即一个网络。E的每条边(v, w)的权为c[v][w]。
如果G的一个子图G’是一棵包含G的所有顶点的树，则称G’为G的生成树。
生成树的各边权的总和称为该生成树的耗费。
在G的所有生成树中，耗费最小的生成树称为G的最小生成树MST(minimum spanning tree) 。
算法思想
在保证连通的前提下依次选出权重较小的n – 1条边。G=(V, E)为无向连通带权图，令V={1, 2, …, n}。设置一个集合S ，初始化S = {1}，生成树T = Φ。贪心策略：如果V–S中的顶点j与S中的某个点i连接, 且(i, j)是E中的权重最小的边，则选择j(将j加入S)，并将(i, j) 加入生成树T中。重复执行贪心策略，直至V–S为空。
Prim算法中的数据结构
图用连接矩阵C[i][j]给出，即C[i][j]为结点i到结点j的权重。为了有效地找出V–S中满足与S中的某个点i连接且(i, j) 权重最小的顶点j，对其中的每个顶点j设立两个数组closest[j]和lowcost[j]：对于每一个j ∈ V–S , 定义closest[j] 数组，closest[j]是j 在S中的邻居邻接顶点，它与j在S中的其它邻居节点k比较，有c[j][closest[j]]c[j][k]；定义lowcost[j]数组， lowcost[j]的值就是c[j][closest[j]]。Prim算法执行过程中每一个j ∈ V–S，先找出使得lowcost[j]最小的顶点j，根据数组closest[j]选取边（j, closest[j] ）,最后，将j添加到S中。
核心算法
Prim(int n
, Type
**c
) {
int j
= 1; s
[j
] = true;
for (int i
= 2; i
<= n
; i
++) {
closest
[i
] = 1; lowcost
[i
]=c
[1][i
]; s
[i
]=false;}
for (int i
= 1; i
< n
; i
++) {min
= inf
;
for (int k
= 2; k
<= n
; k
++) {
if (lowcost
[k
]<min
&&!s
[k
])
{min
= lowcost
[k
]; j
= k
}
s
[j
] = true;
for (int k
= 2; k
<= n
; k
++) {
if (c
[j
][k
]< lowcost
[k
]&&!s
[k
])
{lowcost
[k
] = c
[j
][k
]; closest
[k
] = j
}
}
}
例子
给定一个连通带权图如下：
假如从顶点A出发，顶点 B、C、D 到顶点 A 的权值分别为 2、4、2，所以，对于顶点 A 来说，顶点 B 和顶点 D 到 A 的权值最小，假设先找到的顶点 B： 继续分析顶点 C 和 D，顶点 C 到 B 的权值为 3，到 A 的权值为 4；顶点 D 到 A 的权值为 2，到 B 的权值为无穷大（如果之间没有直接通路，设定权值为无穷大）。所以顶点 D 到 A 的权值最小：
最后，只剩下顶点 C，到 A 的权值为 4，到 B 的权值和到 D 的权值一样大，为 3。所以该连通图有两个最小生成树：
完整代码
#include
<bits
/stdc
++.h
>
using namespace std
;
const int max_
= 0x3f3f3f;
int Graph
[110][110];
int visited
[110];
int closest
[110];
int prepos
[110];
int pointnum
, edgenum
;
int FindMinLen()
{
int pos
, min_
= max_
;
for(int i
= 1; i
<= pointnum
; ++i
)
if(min_
> closest
[i
] && closest
[i
])
{
min_
= closest
[i
];
pos
= i
;
}
return pos
;
}
void Prim()
{
for(int i
= 2; i
<= pointnum
; ++i
)
{
closest
[i
] = Graph
[1][i
];
prepos
[i
] = 1;
}
closest
[1] = 0;
for(int i
= 1; i
< pointnum
; ++i
)
{
int pos
;
pos
= FindMinLen();
closest
[pos
] = 0;
for(int j
= 2; j
<= pointnum
; ++j
)
{
if(closest
[j
] > Graph
[pos
][j
])
{
closest
[j
] = Graph
[pos
][j
];
prepos
[j
] = pos
;
}
}
printf("%d -> %d\n", prepos
[pos
], pos
);
}
}
void InPut()
{
int pos1
, pos2
, len
;
scanf("%d %d", &pointnum
, &edgenum
);
memset(Graph
, max_
, sizeof(Graph
));
for(int i
= 1; i
<= edgenum
; ++i
)
{
scanf("%d %d %d", &pos1
, &pos2
, &len
);
Graph
[pos1
][pos2
] = len
;
Graph
[pos2
][pos1
] = len
;
}
}
int main()
{
InPut();
Prim();
}
测试用例
输入 4 5 1 2 2 1 3 2 1 4 4 2 4 3 3 4 3
输出 1 -> 2 1 -> 3 2 -> 4
