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 | 2
C | 2 | 1
D | 2 | 0
E | 1 | 1
F | 2 | 0

(2) 该图的邻接矩阵为：

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

(3) 该图的邻接表为：

A -> B -> C
B -> D -> E
C -> E
D ->
E -> C -> F
F ->

(4) 该图的逆邻接表为：

A <- 
B <- A
C <- A -> B -> E
D <- B
E <- B -> C
F <- E

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

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

相关问题

对于下图所示的有向图，试给出： (1)该图每个顶点的入度和出度； (2)该图的邻接矩阵； (3)该图的邻接表； (4)该图的逆邻接表。


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

顶点 1 的入度为 1，出度为 2

顶点 2 的入度为 1，出度为 1

顶点 3 的入度为 2，出度为 0

顶点 4 的入度为 1，出度为 1

顶点 5 的入度为 1，出度为 1

(2) 该图的邻接矩阵：

  1 2 3 4 5
1 0 1 0 0 1
2 0 0 1 0 0
3 0 0 0 0 0
4 0 1 0 0 0
5 0 0 1 0 0

(3) 该图的邻接表：

1 -> 2 -> 5
2 -> 3
3 ->
4 -> 2
5 -> 3

(4) 该图的逆邻接表：

1 -> 5
2 -> 1 -> 4
3 -> 2 -> 5
4 ->
5 -> 1

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