第8章图 (2)邻接表 (出边表 5∧ 3D (入边表) 1 B -3B (3)邻接多重表(十字链表) data fin fout ij ilink jlink 0A∧ 0 03∧∧ 4121(((((B.C) 2|5A 31 54A∧cE 8-4用邻接矩阵表示图时,若图中有1000个顶点,1000条边,则形成的邻接矩阵有多少矩阵元素?有 多少非零元素?是否稀疏矩阵? 【解答】 个图中有1000个顶点,其邻接矩阵中的矩阵元素有10002=1000000个。它有1000个非零元素(对 于有向图)或2000个非零元素(对于无向图),因此是稀疏矩阵。 8-5用邻接矩阵表示图时,矩阵元素的个数与顶点个数是否相关?与边的条数是否相关? 【解答】 用邻接矩阵表示图,矩阵元素的个数是顶点个数的平方,与边的条数无关。矩阵中非零元素的个数 与边的条数有关 8-6有n个顶点的无向连通图至少有多少条边?有n个顶点的有向强连通图至少有多少条边?试举例说 【解答】第 8 章 图 97 (2) 邻接表 (3) 邻接多重表（十字链表） 8-4 用邻接矩阵表示图时，若图中有 1000 个顶点，1000 条边，则形成的邻接矩阵有多少矩阵元素？有 多少非零元素？是否稀疏矩阵？ 【解答】 一个图中有 1000 个顶点，其邻接矩阵中的矩阵元素有 10002 = 1000000 个。它有 1000 个非零元素（对 于有向图）或 2000 个非零元素（对于无向图），因此是稀疏矩阵。 8-5 用邻接矩阵表示图时，矩阵元素的个数与顶点个数是否相关？与边的条数是否相关？ 【解答】 用邻接矩阵表示图，矩阵元素的个数是顶点个数的平方，与边的条数无关。矩阵中非零元素的个数 与边的条数有关。 8-6 有 n 个顶点的无向连通图至少有多少条边？有 n 个顶点的有向强连通图至少有多少条边？试举例说 明。 【解答】 0 A 1 B 2 C 3 D 4 E 5 F 1 0 A 1 B 2 C 3 D 4 E 5 F 3 2 4 5 1 4 4 0 3 1 0 1 3 5 2 ∧ ∧ ∧ ∧ ∧ ∧ ∧ ∧ ∧ ∧ ∧ ∧ （出边表） （入边表） 0 A 1 B 2 C 3 D 4 E 5 F data fin fout i j ilink jlink 0 1 (A, B) 0 3 (A, D) 1 2 (B, C) 1 4 (B, E) 2 5 (C, F) 3 1 (D, B) 3 4 (D, E) 5 4 (F, E) ∧ ∧ ∧ ∧ ∧ ∧ ∧ ∧ ∧ ∧