第五章 图

1、在图结构中，任意两个结点之间都可能相关，结点之间的邻接关系可以是任意的。

2、无向图：任意两点之间都有边的无向图称为无向完全图。一个具有n个顶点的无向完全图的边数为：n(n-1)/2。任何两点之间都有弧的有向图称为有向完全图。一个具有n个顶点的有向完全图的弧数为n(n-1)。

3、无向图中顶点V的度是与该顶点相关联的边的数目。有向图，以顶点V为终点的弧的数目称为V的入度，以顶点V为始点的弧的数目称为V的出度。有向图的度为入度和出度的和。

4、在无向图中，如果两个顶点之间有路径，则称为这两个顶点之间是连通的。如果图中的任意两个顶点都是连通的，则称为连通图。有向图中的任意两个顶点之间双向连通则称该图为强连通图。

5、图的存储结构：

邻接矩阵：

6、如果一个无向图有n个顶点，e条边，那么它的邻接表需要n个头结点和2e个表结点。在边稀疏的情况下，用邻接表表示比用邻接矩阵节省存储空间。

邻接表：

7、图的遍历：

8、采用Prim算法求最小生成树：

9、采用克鲁斯卡尔（Kruska）构造最小生成树：

10、拓扑排序

例题：求有向图顶点的拓扑序列，并画出它的邻接表：