建立如图8.41所示的有向图g的邻接矩阵,并输出;(2)由有向图g的邻接矩阵产生邻接表,
时间: 2023-09-09 10:01:09 浏览: 59
(1) 按照图8.41所示,我们可以建立有向图g的邻接矩阵。邻接矩阵是一个二维矩阵,其中行和列分别代表图中的顶点。邻接矩阵中的元素表示从一个顶点到另一个顶点是否存在一条有向边。
首先,我们需要确定有向图g中有多少个顶点。根据图8.41,我们可以看到有顶点A、B、C、D、E、F、G、H共8个顶点。
然后,我们可以用一个8x8的矩阵来表示邻接矩阵。其中的行和列分别代表图中的顶点。
创建一个8x8的矩阵如下:
```
A B C D E F G H
A |0 1 0 0 0 0 0 0|
B |0 0 1 1 0 0 0 0|
C |0 1 0 0 0 0 0 0|
D |0 0 0 0 1 1 1 0|
E |0 0 0 0 0 0 1 1|
F |0 0 0 0 0 0 1 1|
G |0 0 0 0 0 0 0 0|
H |0 0 0 0 0 0 1 0|
```
上述矩阵的每个元素代表对应位置的行顶点到列顶点之间是否存在一条有向边。其中1表示存在有向边,0表示不存在。
(2) 邻接矩阵产生邻接表的过程,需要扫描每一个顶点所对应的邻接矩阵的行。对于每个顶点,如果邻接矩阵中的元素为1,则将对应的列顶点加入到该顶点的邻接表中。
按照上述邻接矩阵,我们可以得到相应的邻接表如下:
```
A -> B
B -> C, D
C -> B
D -> E, F, G
E -> G, H
F -> G, H
G -> None
H -> G
```
上述邻接表表示了每个顶点与其邻接顶点之间的关系,其中“->”表示有向边的关系。例如,A -> B表示从顶点A到顶点B存在一条有向边。对于没有邻接顶点的顶点(如G),邻接表中的对应项为None。
总结:建立有向图g的邻接矩阵和邻接表可以帮助我们更好地理解和分析图中顶点之间的关系和结构。