已知一个图的顶点集V和边集E分别为:V- {1,2,3,4,5,6,7}; E={(1,2)3,(1,3)5,(1,4)8,(2,5)10,(2,3)6,(3,4)15,(3,5)12,(3,6)9,(4,6)4,(4,7)20,(5,6)18,(6,7)25};用克鲁斯卡尔算法得到最小生成树,试写出在最小生成树中
时间: 2023-08-19 20:41:24 浏览: 169
包含的边以及它们的权值。
首先,将边按照权值从小到大排序,得到如下排序后的边集:
{(4,6)4, (1,2)3, (1,3)5, (2,3)6, (3,6)9, (2,5)10, (3,5)12, (5,6)18, (4,7)20}
从权值最小的边(4,6)4开始,逐一加入边,如果加入一条边会形成回路,则不加入,直到加入n-1条边为止,其中n为顶点数。
首先加入(4,6)4,得到生成树T={(4,6)4},其中顶点集为{4,6}。
接下来加入(1,2)3,这条边与T不形成回路,加入后得到T={(4,6)4, (1,2)3},其中顶点集为{1,2,4,6}。
继续加入(1,3)5,这条边与T不形成回路,加入后得到T={(4,6)4, (1,2)3, (1,3)5},其中顶点集为{1,2,3,4,6}。
接着加入(2,3)6,这条边与T不形成回路,加入后得到T={(4,6)4, (1,2)3, (1,3)5, (2,3)6},其中顶点集为{1,2,3,4,6}。
加入(3,6)9,这条边与T不形成回路,加入后得到T={(4,6)4, (1,2)3, (1,3)5, (2,3)6, (3,6)9},其中顶点集为{1,2,3,4,6}。
加入(2,5)10,这条边与T不形成回路,加入后得到T={(4,6)4, (1,2)3, (1,3)5, (2,3)6, (3,6)9, (2,5)10},其中顶点集为{1,2,3,4,5,6}。
加入(3,5)12,这条边与T不形成回路,加入后得到T={(4,6)4, (1,2)3, (1,3)5, (2,3)6, (3,6)9, (2,5)10, (3,5)12},其中顶点集为{1,2,3,4,5,6}。
加入(5,6)18,这条边与T不形成回路,加入后得到T={(4,6)4, (1,2)3, (1,3)5, (2,3)6, (3,6)9, (2,5)10, (3,5)12, (5,6)18},其中顶点集为{1,2,3,4,5,6}。
最后加入(4,7)20,这条边与T不形成回路,加入后得到T={(4,6)4, (1,2)3, (1,3)5, (2,3)6, (3,6)9, (2,5)10, (3,5)12, (5,6)18, (4,7)20},其中顶点集为{1,2,3,4,5,6,7}。
因此,最小生成树包含的边以及它们的权值为:
(4,6)4, (1,2)3, (1,3)5, (2,3)6, (3,6)9, (2,5)10, (3,5)12, (5,6)18, (4,7)20
相关推荐
![pdf](https://img-home.csdnimg.cn/images/20210720083512.png)
![doc](https://img-home.csdnimg.cn/images/20210720083327.png)
![ppt](https://img-home.csdnimg.cn/images/20210720083527.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![pdf](https://img-home.csdnimg.cn/images/20210720083512.png)
![doc](https://img-home.csdnimg.cn/images/20210720083327.png)
![](https://img-home.csdnimg.cn/images/20210720083646.png)
![](https://img-home.csdnimg.cn/images/20210720083646.png)