已知一个带权图的顶点集V和边集G分别为: V={0,1,2,3,4,5}; E={(0,1)8,(0,2)5,(0,3)2,(1,5)6,(2,3)25,(2,4)13,(3,5)9,(4,5)10}, (1)画出该图并给出其邻接表表示。 (2)求出该图的最小生成树的权。
时间: 2024-06-14 20:03:27 浏览: 39
(1) 该图的邻接表表示如下:
| 顶点 | 邻接点及权值 |
| --- | --- |
| 0 | (1, 8), (2, 5), (3, 2) |
| 1 | (0, 8), (5, 6) |
| 2 | (0, 5), (3, 25), (4, 13) |
| 3 | (0, 2), (2, 25), (5, 9) |
| 4 | (2, 13), (5, 10) |
| 5 | (1, 6), (3, 9), (4, 10) |
(2) 该图的最小生成树的权为:35。
最小生成树的边依次为:(0, 3), (0, 2), (0, 1), (1, 5), (4, 5)。
相关问题
9. 已知一个图的顶点集V和边集E分别为: V={1,2,3,4,5,6,7}; E={〈2,1>,〈3,2>,〈3,6〉,〈4,3〉,<4,5>,<4,6>,〈5,1>,<5,7〉,〈6,1>,〈6,2〉,〈6,5〉}; 若存储它采用邻接表,并且每个顶点邻接表中的边结点都是按照终点序号从小到大的次序链接的,按主教材中介绍的拓朴排序算法进行排序,试给出得到的拓朴排序的序列。
根据给定的邻接表,我们可以得到各个顶点的入度:
| 顶点 | 入度 |
| --- | --- |
| 1 | 0 |
| 2 | 2 |
| 3 | 1 |
| 4 | 2 |
| 5 | 2 |
| 6 | 3 |
| 7 | 1 |
从入度为0的顶点开始,按照拓扑排序算法,每次选择一个入度为0的顶点并将其从图中删除,直到图为空或不存在入度为0的顶点为止。在这个过程中,选择的顶点序列即为图的拓扑排序。
根据上表,入度为0的顶点有1和4。我们可以从顶点1和4开始,分别将其从图中删除。此时,入度为0的顶点有2和7。我们可以选择其中任意一个顶点,比如选择2,将其从图中删除。然后入度为0的顶点有3和7,选择其中任意一个,比如选择3,将其从图中删除。然后入度为0的顶点有5和7,选择其中任意一个,比如选择5,将其从图中删除。此时入度为0的顶点只剩下7,将其删除后,图为空,得到的拓扑排序为:
1 -> 4 -> 2 -> 3 -> 5 -> 6 -> 7
上已知一个有向图的顶点集V和边集G分别为:V={0,1,2,3,4,5,6,7,8);E={《0,2),《1,3),(1,4),《2,4),《2,5),《3,6),《3,7),《4,7),《4,8),《5,7),《6,7),《7,8)},试求(1)若存储它采用邻接矩阵,画出邻接矩阵存储的示意图货 (2)若存储它采用邻接表,并且每个顶点邻接表中的边结点都是按照结点序号从小到
大的顺序存储,请写出每个顶点的邻接表。
(1)邻接矩阵存储的示意图如下:
```
0 1 2 3 4 5 6 7 8
0 0 0 1 0 0 0 0 0 0
1 0 0 0 1 1 0 0 0 0
2 0 0 0 0 1 1 0 0 0
3 0 0 0 0 0 0 1 1 0
4 0 0 0 0 0 0 0 1 1
5 0 0 0 0 0 0 0 1 0
6 0 0 0 0 0 0 0 1 0
7 0 0 0 0 0 0 0 0 1
8 0 0 0 0 0 0 0 0 0
```
(2)每个顶点的邻接表如下:
```
0: 2
1: 3 -> 4
2: 4 -> 5
3: 6 -> 7
4: 7 -> 8
5: 7
6: 7
7: 8
8:
```
相关推荐
![doc](https://img-home.csdnimg.cn/images/20210720083327.png)
![](https://img-home.csdnimg.cn/images/20210720083646.png)
![doc](https://img-home.csdnimg.cn/images/20210720083327.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)
![doc](https://img-home.csdnimg.cn/images/20210720083327.png)
![pdf](https://img-home.csdnimg.cn/images/20210720083512.png)
![pdf](https://img-home.csdnimg.cn/images/20210720083512.png)