西安电子科技大学出版社：《算法与数据结构》课程教学资源（练习题）第7章练习题

第7章图 要点: 1、图的逻辑结构和基本概念 2、图的存储表示 练习: 1、具有n个顶点的完全有向图的弧数为 2、对如右无向图: (1)画出图的邻接表存储结构 (2)给出邻接矩阵 (3)指出每个顶点的度; (4)该图是连通图吗? (5)写出从顶点A出发,按深 度优先遍历图时得到的顶 点序列。 叫>2囚 (6)写出从顶点A出发,按广 度优先遍历图时得到的顶‖v2 点序列。 N 3、对于一个具有n个顶点无向 乃32 图,回答下面问题: (1)所有顶点的度数之和与所3 有边之间存在什么关系? (2)该图要连通全部顶点至少 需要多少条边? (3)若该图为完全图,则包含多少条边? 4、若一个有向图的十字链表如上,试画出该有向图 参考解答: 1、n*(n-1) 2、(1)如右: 0[3A (2) =lOI 1匚 10010000 平2-[ bLa 0011100 01100000 00100 00101010 00000101 00001010 (3)A:2B:2C:4D:2E:3F:3G:2H:2 (4)是连通图 (5)ABDCEHGF (6) ABCDEFHG

第 7 章 图 要点： 1、图的逻辑结构和基本概念； 2、图的存储表示； 练习： 1、具有 n 个顶点的完全有向图的弧数为 。 2、对如右无向图： （1）画出图的邻接表存储结构； （2）给出邻接矩阵； （3）指出每个顶点的度； （4）该图是连通图吗？。 （5）写出从顶点 A 出发，按深 度优先遍历图时得到的顶 点序列。 （6）写出从顶点 A 出发，按广 度优先遍历图时得到的顶 点序列。 3、对于一个具有 n 个顶点无向 图，回答下面问题： （1）所有顶点的度数之和与所 有边之间存在什么关系？ （2）该图要连通全部顶点至少 需要多少条边？ （3）若该图为完全图，则包含多少条边？ 4、若一个有向图的十字链表如上，试画出该有向图。 参考解答： 1、n*(n-1) 2、（1）如右： （2） 0 0 0 0 1 0 1 0 0 0 0 0 0 1 0 1 0 0 1 0 1 0 1 0 0 0 1 0 0 1 0 1 0 1 1 0 0 0 0 0 1 0 0 1 1 1 0 0 1 0 0 1 0 0 0 0 0 1 1 0 0 0 0 0 （3）A：2 B：2 C：4 D：2 E：3 F：3 G：2 H：2 （4）是连通图 （5）ABDCEHGF （6） ABCDEFHG

3、(1)所有顶点的度数之和是所有边数的2倍 (3)n(n-1)/2

3、（1）所有顶点的度数之和是所有边数的 2 倍； （2）n-1 （3）n(n-1)/2 4