对于题图所示的有向网， ‍ （1）给出该图对应的邻接矩阵、邻接表和逆邻接表； ‍ （2）判断该图是否为强连通图，并给出其强连通分量； ‍ （3）给出每个顶点的度、入度和出度； ‍ （4）给出从顶点V1开始的深度优先搜索遍历序列和广度优先搜索遍历序列。 ‍ ‌ ‍ ‌

(1) 邻接矩阵：

| | V1 | V2 | V3 | V4 | V5 |
|---|----|----|----|----|----|
| V1| 0 | 1 | 0 | 0 | 1 |
| V2| 0 | 0 | 1 | 1 | 0 |
| V3| 0 | 0 | 0 | 1 | 0 |
| V4| 0 | 0 | 0 | 0 | 1 |
| V5| 0 | 0 | 0 | 0 | 0 |

邻接表：

V1: V2 -> V5 \
V2: V3 -> V4 \
V3: V4 \
V4: V5 \
V5:

逆邻接表：

V1: \
V2: V1 \
V3: V2 \
V4: V2 -> V3 \
V5: V1 -> V4 \

(2) 该图不是强连通图。它的强连通分量为：

{V1, V2, V3}, {V4}, {V5}

(3) 每个顶点的度、入度和出度如下：

| | 度 | 入度 | 出度 |
|---|----|------|------|
| V1| 2 | 0 | 2 |
| V2| 2 | 1 | 1 |
| V3| 1 | 2 | 0 |
| V4| 2 | 2 | 0 |
| V5| 1 | 2 | 0 |

(4) 从顶点 V1 开始的深度优先搜索遍历序列为：V1 -> V2 -> V3 -> V4 -> V5

从顶点 V1 开始的广度优先搜索遍历序列为：V1 -> V2 -> V5 -> V3 -> V4

相关问题

对于题图所示的有向网， ‎ （1）给出该图对应的邻接矩阵、邻接表和逆邻接表； ‎ （2）判断该图是否为强连通图，并给出其强连通分量； ‎ （3）给出每个顶点的度、入度和出度； ‎ （4）给出从顶点V1开始的深度优先搜索遍历序列和广度优先搜索遍历序列。 ‎ ‍

1. 该图对应的邻接矩阵为：

| | V1 | V2 | V3 | V4 | V5 | V6 |
|---|----|----|----|----|----|----|
|V1 | 0 | 1 | 0 | 0 | 0 | 1 |
|V2 | 0 | 0 | 1 | 0 | 0 | 0 |
|V3 | 0 | 1 | 0 | 1 | 0 | 1 |
|V4 | 0 | 0 | 0 | 0 | 1 | 0 |
|V5 | 0 | 0 | 0 | 1 | 0 | 0 |
|V6 | 0 | 0 | 0 | 0 | 1 | 0 |

该图对应的邻接表为：

V1 -> V2, V6
V2 -> V3
V3 -> V2, V4, V6
V4 -> V5
V5 -> V4
V6 -> V5

该图对应的逆邻接表为：

V1 -> V6
V2 -> V1, V3
V3 -> V2
V4 -> V3
V5 -> V4, V6
V6 -> V1, V3

2. 该图不是强连通图，其强连通分量为：

{V1, V2, V6}, {V3}, {V4}, {V5}

3. 每个顶点的度、入度和出度如下：

| | 度 | 入度 | 出度 |
|---|----|------|------|
|V1 | 2 | 0 | 2 |
|V2 | 1 | 1 | 0 |
|V3 | 3 | 2 | 1 |
|V4 | 1 | 1 | 0 |
|V5 | 2 | 2 | 0 |
|V6 | 2 | 1 | 1 |

4. 从顶点V1开始的深度优先搜索遍历序列为：V1 -> V2 -> V3 -> V4 -> V5 -> V6

从顶点V1开始的广度优先搜索遍历序列为：V1 -> V2 -> V6 -> V3 -> V5 -> V4

1.(20分)对于下图所示的有向图，请给出： (1)该图每个顶点的入度和出度；(2)该图的邻接矩阵； (3)该图的邻接表； (4)该图的逆邻接表； (5)写出一种从A点开始按深度优先遍历该图的序列； (6)写出一种从A点开始按广度优先遍历该图的序列。↵ A A 5 7 C D B F 6 5 5 3 B E C E 4 2 D F 笛1 题图 第2题图

(1) 该图每个顶点的入度和出度：

顶点  入度  出度
A     0     2
B     1     1
C     2     1
D     1     1
E     2     0
F     2     0

(2) 该图的邻接矩阵：

  A B C D E F
A 0 0 1 0 0 1
B 1 0 0 0 1 0
C 0 1 0 0 1 0
D 0 0 1 0 0 1
E 0 0 1 1 0 0
F 0 0 0 1 1 0

(3) 该图的邻接表：

A: C F
B: A E
C: B E
D: C F
E: C D
F: D E

(4) 该图的逆邻接表：

A: B
B: C
C: A D E
D: F
E: B C
F: A D

(5) 从A点开始按深度优先遍历该图的序列为：A -> C -> B -> E -> D -> F

(6) 从A点开始按广度优先遍历该图的序列为：A -> C -> F -> B -> E -> D