Question

数据结构，无向图

希望写出详细的步骤

Answer 1

克鲁斯卡尔算法过程：

1.将原图中所有的边按权值从小到大排序；

2.从权值最小的边开始，如果这条边连接的两个节点于图G中不在同一个连通分量中，则添加这条边到图G中；

3.重复3，直至图G中所有的节点都在同一个连通分量中。

--源自百度百科

所有边有{<a,b,19>,<b,c,5>,<c,d,3>,<b,d,7>,<a,e,14>,<b,e,12>,<d,e,8>,<d,f,21>,<e,g,16>,<a,g,18>}，排序完后有{<c,d,3>,<b,c,5>,<b,d,7>,<d,e,8>,<b,e,12>,<a,e,14>,<e,g,16>,<a,g,18>,<a,b,19>,<d,f,21>,<f,g,27>}共11条边，称边权第i小的边为第i条边

1. 第1条边 权值为3,c,d不属于一个连通分量，加入

2. 第2条边 权值为5,b,c不属于一个连通分量，加入

3. 第3条边 权值为7,b,d属于一个连通分量，跳过

4. 第4条边 权值为8,d,e不属于一个连通分量，加入

5. 第5条边 权值为12,b,e属于一个连通分量，跳过

6. 第6条边 权值为14,a,e不属于一个连通分量，加入

7. 第7条边 权值为16,e,g不属于一个连通分量，加入

8. 第8条边 权值为18,a,g属于一个连通分量，跳过

9. 第9条边 权值为19,a,b属于一个连通分量，跳过

10. 第10条边 权值为21,d,f不属于一个连通分量，加入

11. 第11条边 权值为27,f,g属于一个连通分量，跳过

    最小生成树的权值和是67，边集是{<c,d,3>,<b,c,5>,<d,e,8>,<a,e,14>,<e,g,16>,<d,f,21>}

追问

最小生成树呢

？？？

Answer 2

扫码就行了。

追问

扫什么码