第五章 图@H_502_1@
1、在图结构中，任意两个结点之间都可能相关，结点之间的邻接关系可以是任意的。@H_502_1@
2、无向图：任意两点之间都有边的无向图称为无向完全图。一个具有n个顶点的无向完全图的边数为：n(n-1)/2。任何两点之间都有弧的有向图称为有向完全图。一个具有n个顶点的有向完全图的弧数为n(n-1)。@H_502_1@
3、无向图中顶点V的度是与该顶点相关联的边的数目。有向图，以顶点V为终点的弧的数目称为V的入度，以顶点V为始点的弧的数目称为V的出度。有向图的度为入度和出度的和。@H_502_1@
4、在无向图中，如果两个顶点之间有路径，则称为这两个顶点之间是连通的。如果图中的任意两个顶点都是连通的，则称为连通图。有向图中的任意两个顶点之间双向连通则称该图为强连通图。@H_502_1@
5、图的存储结构：@H_502_1@
邻接矩阵：@H_502_1@
@H_502_1@
6、如果一个无向图有n个顶点，e条边，那么它的邻接表需要n个头结点和2e个表结点。在边稀疏的情况下，用邻接表表示比用邻接矩阵节省存储空间。@H_502_1@
邻接表：@H_502_1@
@H_502_1@
7、图的遍历：@H_502_1@
@H_502_1@
@H_502_1@
9、采用克鲁斯卡尔（Kruska）构造最小生成树：@H_502_1@
@H_502_1@
10、拓扑排序@H_502_1@
例题：求有向图顶点的拓扑序列，并画出它的邻接表：@H_502_1@
@H_502_1@