第2章 第6节 图论VIP免费

第 6 节 图 图 (Graph) 是一种复杂的非线性结构。在人工智能、工程、数学、物理、化学、生物和计算机科学等领域中，图结构有着广泛的应用。奥林匹克信息学竞赛的许多试题，亦需要用图来描述数据元素间的联系。 图 G 由两个集合 V 和 E 组成，记为：G=(V ， E) ，其中： V 是顶点的有穷非空集合， E 是 V 中顶点偶对 ( 称为边 ) 的有穷集。通常，也将图 G 的顶点集和边集分别记为 V(G) 和 E(G) 。 E(G) 可以是空集。若 E(G) 为空，则图 G 只有顶点而没有边。一、什么是图？ 很简单，点用边连起来就叫做图，严格意义上讲，图是一种数据结构，定义为： graph= （ V ， E ）。 V 是一个非空有限集合，代表顶点（结点）， E 代表边的集合。二、图的一些定义和概念1. (a) 有向图：图的边有方向，只能按箭头方向从一点到另一点。 (a) 就是一个有向图。2. (b) 无向图：图的边没有方向，可以双向。 (b) 就是一个无向图。3. 结点的度：无向图中与结点相连的边的数目，称为结点的度。4. 结点的入度：在有向图中，以这个结点为终点的有向边的数目。5. 结点的出度：在有向图中，以这个结点为起点的有向边的数目。6. 权值：边的“费用”，可以形象地理解为边的长度。7. 连通：如果图中结点 U ， V 之间存在一条从 U 通过若干条边、点到达 V 的通路，则称 U 、 V 是连通的8. 回路：起点和终点相同的路径，称为回路，或“环”。9. 完全图：一个 n 阶的完全无向图含有 n*(n-1)/2 条边；一个 n 阶的完全有向图含有 n*(n-1) 条边； 稠密图：一个边数接近完全图的图。 稀疏图：一个边数远远少于完全图的图。10. 强连通分量：有向图中任意两点都连通的最大子图。下图中 1-2-5 构成一个强连通分量。特殊地，单个点也算一个强连通分量，所以右图有三个强连通分量： 1-2-5 ， 4 ， 3 。 1 2 3 4 5 (a) 1 2 3 4 5 (b) 1 2 3 4 5 三、图的存储结构1. 二维数组邻接矩阵存储定义 int G[101][101];G[i][j] 的值，表示从点 i 到点 j 的边的权值，定义如下：上图中的 3 个图对应的邻接矩阵分别如下： 0 1 1 1 0 1 1 ∞ 5 8 ∞ 3G （ A ） = 1 0 1 1 G （ B ） = 0 0 1 5 ∞ 2 ∞ 6 1 1 0 0 0 1 0 G （ C ） = 8 2 ∞ 10 4 1 1 0 0 ∞ ∞ 10 ∞ 11 3 6 4 11 ∞四、深度优先与广度优...