无向图G=(V, E),其中:V={a,b,c,d,e,f}, E={<a,b>10,<a,e>8,<a,c>3,<b,e>10,<b,f>7,<c,f>6,<f,d>5,<e,d>2},请回答以下问题: (1)画出该无向图的示意图;(2)画出图的邻接矩阵存储结构示意图;(3)用普利姆算法构造由顶点a开始的最小生成树,写出构造过程。
时间: 2024-03-03 07:52:54 浏览: 48
无向图G-图的基本概念
(1)该无向图的示意图如下:
```
10 8
b --------- e
/ | | \
10 | |7 | 2
/ | | | \
a | | | d
\ | |6 | /
3 \ | | | / 5
\ \|/ |/ /
c --------- f
6
```
(2)该无向图的邻接矩阵存储结构示意图如下:
```
a b c d e f
a 0 10 3 0 8 0
b 10 0 0 0 10 7
c 3 0 0 0 0 6
d 0 0 0 0 2 5
e 8 10 0 2 0 0
f 0 7 6 5 0 0
```
(3)用普利姆算法构造由顶点a开始的最小生成树,构造过程如下:
1. 选取a作为起始节点,将a加入生成树中。
2. 找出与a相连的边中权值最小的边<a, c>,将c加入生成树中。
3. 找出与已加入生成树的节点相连的边中权值最小的边,即<b, e>,将b和e加入生成树中。
4. 找出与已加入生成树的节点相连的边中权值最小的边,即<e, d>,将d加入生成树中。
5. 找出与已加入生成树的节点相连的边中权值最小的边,即<f, d>,将f加入生成树中。
6. 生成树中包含所有节点,算法结束。
构造过程中生成的最小生成树如下:
```
8
b --------- e
|
10 | 2
|
d
|
6 |
f --------- c
3
```
阅读全文