20023
数据结构作业 2002 年 第七章 图
71已知如右图所示的有向图请给出 (1)各顶点的入/出度; (2)邻接矩阵; (3)邻接表; (4)逆邻接表; (5)强连通分量。 解答:(1) 顶点入度出度顶点入度出度 B ACE 2 D 233
7.1 已知如右图所示的有向图，请给出 （1）各顶点的入/出度； （2）邻接矩阵； （3）邻接表； （4）逆邻接表； （5）强连通分量。 B D A E F C 解答：（1） 顶点 入度 出度 顶点 入度 出度 A 3 0 B 2 2 C 1 2 D 1 3 E 2 1 F 2 3
(2)邻接矩阵; A C DE F A(000000 V[1..6] B100100 C010001 AB CDEF D001011 123456 E100000 顶点数组 F(110010 邻接矩阵
（2）邻接矩阵； A B C D E F A 0 0 0 0 0 0 B 1 0 0 1 0 0 C 0 1 0 0 0 1 D 0 0 1 0 1 1 E 1 0 0 0 0 0 F 1 1 0 0 1 0 M= 邻接矩阵 A B C D E F 1 2 3 4 5 6 顶点数组 V[1..6]
(3)邻接表; 序号头结点数组表结点单链表 123456 ABCDEF 1[4 3→D[6人 →区[5 图邻接表
（3）邻接表； A ∧ B C D E F 1 2 3 4 5 6 1 ∧ 图邻接表 序号 头结点数组 表结点单链表 1 4 ∧ 3 5 6 ∧ 2 6 ∧ 1 2 5 ∧
4)逆邻接表; 序号头结点数组表结点单链表 ⑤→[6 123456 ABCDEF 4 图逆邻接表
（4）逆邻接表； A B C D E F 1 2 3 4 5 6 图逆邻接表 序号 头结点数组 表结点单链表 3 6 ∧ 2 5 6 ∧ 4 ∧ 2 ∧ 4 6 ∧ 3 6 ∧