计算机 数据结构 题

Question

（1）各顶点的入度和出度
（2）什么是强连通分量，画出此图的强连通分量
（3）画出图的邻接矩阵
（4）画出图的邻接链表

最好能有详细过程，谢谢了！~

Answer 1

（1）入度：指向该点的箭头数量；出度：该点指向其他点的箭头数量 (入度=出度)
顶点 入度 出度
A 2 3
B 1 1
C 1 1
D 1 2
E 2 2
F 2 0
（2）在有向图G中，如果两个顶点间至少存在一条路径，称两个顶点强连通(strongly connected)。如果有向图G的每两个顶点都强连通，称G是一个强连通图。非强连通图有向图的极大强连通子图，称为强连通分量(strongly connected components)。

｛A、B、C、D、E｝为一个强连通分量，因为顶点ABCDE两两可达，{F}也是一个强连通分量
（3）0表示不指向，1表示指向改点，第一行第二列的1表示：A指向B。
0 1 0 1 1 0
0 0 1 0 0 0
1 0 0 0 0 0
0 0 0 0 1 1
1 0 0 0 0 1
0 0 0 0 0 0
（4）因为不能截图，所以比较简陋，你应该看的懂的吧~~~邻接链表主要在后面接的是出度的顶点
0 A ---> 1---> 3--> 4 |^
1 B ---> 2|^
2 C ---> 0 |^
3 D ---> 4 ---> 5 |^
4 E ---> 0---> 5 |^
5 F |^