无向图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开始的最小生成树,写出构造过程。
时间: 2023-10-08 07:13:19 浏览: 283
(1)无向图示意图如下:
```
10 7
a------b------f
| 8 / | \ |
| / | \ |
3|/ |6 \|5
c------f-----d
2
```
(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)普利姆算法构造最小生成树的过程如下:
1. 选定起点a,将a加入最小生成树中,同时将所有与a相邻的边加入候选集合中。
2. 在候选集合中选取权值最小的边,该边的另一端点如果未被加入最小生成树,则将该点加入最小生成树中,并将与该点相邻的边加入候选集合中。
3. 重复步骤2,直到最小生成树包含了所有的节点。
具体构造过程如下:
第一步:选定起点a,将a加入最小生成树中,同时将所有与a相邻的边加入候选集合中。此时最小生成树为{a},候选集合为{<a,b>10, <a,e>8, <a,c>3}。
```
10 7
a------b------f
| 8 / | \ |
| / | \ |
3|/ |6 \|5
c------f-----d
2
最小生成树:{a}
候选集合:{<a,b>10, <a,e>8, <a,c>3}
```
第二步:在候选集合中选取权值最小的边<a,c>3,将c加入最小生成树中,并将与c相邻的边加入候选集合中。此时最小生成树为{a, c},候选集合为{<a,b>10, <a,e>8, <c,f>6}。
```
10 7
a------b------f
| 8 / | \ |
| / | \ |
3|/ |6 \|5
c------f-----d
2
最小生成树:{a, c}
候选集合:{<a,b>10, <a,e>8, <c,f>6}
```
第三步:在候选集合中选取权值最小的边<a,e>8,将e加入最小生成树中,并将与e相邻的边加入候选集合中。此时最小生成树为{a, c, e},候选集合为{<a,b>10, <b,e>10, <c,f>6, <e,d>2}。
```
10 7
a------b------f
| / | \ |
| 10/ | \ |
3| / |6 \|5
c------f-----d
2
最小生成树:{a, c, e}
候选集合:{<a,b>10, <b,e>10, <c,f>6, <e,d>2}
```
第四步:在候选集合中选取权值最小的边<e,d>2,将d加入最小生成树中,并将与d相邻的边加入候选集合中。此时最小生成树为{a, c, e, d},候选集合为{<a,b>10, <b,e>10, <c,f>6}。
```
10 7
a------b------f
| / | \ |
| 10/ | \ |
3| / 2|6 \|5
c------f-----d
最小生成树:{a, c, e, d}
候选集合:{<a,b>10, <b,e>10, <c,f>6}
```
第五步:在候选集合中选取权值最小的边<c,f>6,将f加入最小生成树中,并将与f相邻的边加入候选集合中。此时最小生成树为{a, c, e, d, f},候选集合为{<a,b>10, <b,e>10}。
```
10 7
a------b------f
| / | /|
| 10/ | / |
3| / 2|/ 5|
c------f-----d
最小生成树:{a, c, e, d, f}
候选集合:{<a,b>10, <b,e>10}
```
第六步:在候选集合中选取权值最小的边<a,b>10,将b加入最小生成树中。此时最小生成树为{a, c, e, d, f, b},候选集合为空。
```
10 7
a------b------f
| / | /|
| 10/ | / |
3| / 2|/ 5|
c------f-----d
最小生成树:{a, c, e, d, f, b}
候选集合:{}
```
因此,由顶点a开始的最小生成树为{a, c, e, d, f, b}。
阅读全文