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