第五章 图

吉林财经大学管理科学与信息工程学院
7
5.1 基本概念和运算
1 2 3 4 连通图示例 5
若无向图中任意两点间都存在路径 无向图中任意两点间都存在路径 连通图。 —— 则称为连通图。 则称为连通图 否则，称为不连通图 非连通图） 不连通图（ 否则，称为不连通图（非连通图）。 非连通图包含若干连通分量 连通分量。 非连通图包含若干连通分量。
1 2 4 5 3
5阶无向完全图 1 2
3
4
4阶有向图示例 阶有向图示例
吉林财经大学管理科学与信息工程学院
9
5.1 基本概念和运算
1 2 3 4 5 7 树的示例 1 3 4 6 7 有向树示例 5 2
若无向图满足： 若无向图满足：连通并且无回路 ——则称为树。 则称为树 则称为 树的定义有如下几个等价的描述： 树的定义有如下几个等价的描述： 等价的描述 有最少边数的连通图。 有最少边数的连通图。 条边的连通图。 有n-1条边的连通图。 条边的连通图 连通的无环图。 连通的无环图。 如果在有向图中， 有向树 —— 如果在有向图中， 有一个顶点的入度为0，其余顶点的入度为1， 有一个顶点的入度为 ，其余顶点的入度为 ， 则称此图为有向树。 则称此图为有向树。 并称其中入度为0的顶点为有向根。 的顶点为有向根 并称其中入度为 的顶点为有向根。 右下图就是一个有向树，其中顶点1就是有向根 就是有向根。 右下图就是一个有向树，其中顶点 就是有向根。
6 dfs(6)
吉林财经大学管理科学与信息工程学院
17
5.3.1 深度优先搜索遍历
将dfs（1）执行过程中所搜索的边连接起来（有标注 （ ）执行过程中所搜索的边连接起来（ 的边）， 的边）， 得到一棵生成树----dfs生成树。 生成树。 得到一棵生成树 生成树
1 1
2 4 7
8 3
2 4 7
8
3
1 2
2 1 1 1
3 4 4 2 ^ ^
4
^
3
4
3 4
3
^
吉林财经大学管理科学与信息工程学院
13
5.2 图的存储
1 2 data firstadj
对应关系
1 2
4
2 4 4 1 ^ ^ ^
3
^
3
3 4
逆邻接链表
代表弧<4,1>
-----将“邻接自”的顶点连成链表data firstadj 将 邻接自” 1 2 3 4
吉林财经大学管理科学与信息工程学院
19
5.3.1 深度优先搜索遍历
1
2 3
有向图中的任意两点间可以 中的任意两点间可以互相到达 若有向图中的任意两点间可以互相到达 ——则称为强连通图。 则称为强连通图 则称为强连通图。
1 3 4 6 7 5 2 4 6
5 7
非连通图示例 ----三个连通分量
8
强连通图示例 吉林财经大学管理科学与信息工程学院
5.1 基本概念和运算
吉林财经大学管理科学与信息工程学院
16
5.3.1 深度优先搜索遍历
下面以下图为例来讨论dfs算法的执行过程：调用 下面以下图为例来讨论 算法的执行过程：调用dfs(1) 算法的执行过程
此箭头表示是从遍历运 算dfs(1)中调用dfs(2)， 即从顶点1直接转到2
此虚箭头表示是在dfs(3) 执行完毕后返回到遍历 运算dfs(2)中，即从顶点 3返回到2
5.1 基本概念和运算
由顶点集V和连接顶点的弧集 或边集） 所组成的结构 和连接顶点的弧集（ 所组成的结构， 图 —— 由顶点集 和连接顶点的弧集（或边集）E所组成的结构， 记作 G = ( V, E )。 。 其中弧的形式为<Vi,Vj>， 其中弧的形式为 ， 表示从顶点Vi到 之间有一条弧 图形表示为： 之间有一条弧， 表示从顶点 到Vj之间有一条弧，图形表示为： Vi —> Vj ----有向图 有向图 如右图中的G1就是一个有向图 就是一个有向图： 例：如右图中的 就是一个有向图：
若无向图中任意两点间都有一条边 无向图中任意两点间都有一条边 ——则称为无向完全图。 则称为无向完全图 则称为无向完全图。 共有n 条边） （共有 (n-1) / 2条边） 条边 若有向图中每个顶点到其余各点均有一条弧 有向图中每个顶点到其余各点均有一条弧 ——则称为有向完全图。 则称为有向完全图 则称为有向完全图。 共有n 条弧） （共有 (n-1) 条弧）
深度优先搜索遍历 图的两种遍历算法 广度优先搜索遍历
5.3.1 深度优先搜索遍历（Depth First Search) 深度优先搜索遍历（
这一问题求解包括几个部分。 这一问题求解包括几个部分。 1. 基本算法 从顶点v0出发深度优先搜索遍历图 出发深度优先搜索遍历图G的 描述如下： 从顶点 出发深度优先搜索遍历图 的dfs (v0)描述如下： 描述如下 (1) 访问 ； 访问v0； (2) 依次从 的未被访问过的邻接点出发深度遍历。 依次从v0的未被访问过的邻接点出发深度遍历 的未被访问过的邻接点出发深度遍历。
1 2
3
4
图G1 有向图示例
中间经过的顶点不重复的路径。 简单路径 —— 中间经过的顶点不重复的路径。 都是简单路径。 例:图G1中，( 1,2,4 ) ( 1,3,4 ) ( 1,3,4,1 ) 都是简单路径。 图 中 首尾顶点相同的路径。 回路 —— 首尾顶点相同的路径。 例如， 例如， ( 1,3,4,1 ) 简单回路 —— 回路中顶点不重复
6
吉林财经大学管理科学与信息工程学院
10
5.2 图的存储
图的存储----图结构在计算机中的存储形式 图的存储 图结构在计算机中的存储形式 1. 邻接矩阵
（1）不带权值 假设图中有n个顶点。则采用n×n的矩阵A来表示， 1 <i，j>∈E 其中 Aij＝ 0 否则 例：
1 2 0 0 0 1 1 0 0 0 1 0 0 0 0 1 1 0
1
2
3
4
其中： 其中： 顶点集合 V={1，2，3，4} ， ， ， 边集 E={ （1,2）,（1,3）,（1,4） ）（ ）（ ） （2,4）,（3,4） ）（ ） }
图G2 无向图示例
吉林财经大学管理科学与信息工程学院
4
⊆
5.1 基本概念和运算
中每条边（ 若G中每条边（弧）对应一个数值 中每条边 ——表示关系的程度，则称图 为 表示关系的程度， 表示关系的程度 则称图G为 网络。 网络。 例： 图G3 就是一个网络 对图G 对图 = ( V, E )，若存在 ，若存在G1=(V1， ， E1)， ， 满足V1 ， 满足 ⊆V，E1⊆ E。则G1是 。 是 G的子图。 的子图。 1 例如：右图G4 就是 就是G2 的子图。 的子图。 例如：右图
6
1
5 7 8 3
2
3
4
图G3 网络示例
2
1
2
3
4
3
4
图G2 无向图示例 图G4 子图示例 吉林财经大学管理科学与信息工程学院
5
5.1 基本概念和运算
顶点间关系： 顶点间关系： 如果 <Vi,Vj>∈E ∈ 则称—— Vi，Vj相邻接， 则称 ， 相邻接，
1 2
Vi邻接到 ，Vj邻接自 。 邻接到Vj， 邻接自 邻接自Vi。 邻接到 例如， 图中， 邻接到 邻接到V2， 邻接自 邻接自V3 例如，右 图中， V1邻接到 ，V4邻接自 则称Vi， 相邻接 若( Vi,Vj )∈E——则称 ，Vj相邻接 ∈ 则称 顶点的度 顶点的邻接点的数目。 顶点的度 —— 顶点的邻接点的数目。 有向图中：入度，出度。 有向图中：入度，出度。 入度＋出度。 度＝入度＋出度。
行的方向：发出的弧 列的方向 ：进入的弧
3
4
对应关系
吉林财经大学管理科学与信息工程学院
11
5.2 图的存储
1 2 0 1 1 1 1 0 0 1 1 0 0 1 1 1 1 0
无向图的邻接矩阵 对称
34ຫໍສະໝຸດ （2） 网络的表示方法 wij <i，j>∈E Aij＝ 0 或∞ 否则 4 例： 1 2
3 3 6 5 2
∞ 4 3 5 4∞∞ 2 3∞∞ 6 5 2 6∞
4 吉林财经大学管理科学与信息工程学院
12
5.2 图的存储
2. 邻接表表示法 ----将每个顶点的邻接点构成链表，并将各链表的表头指针合在一起。 将每个顶点的邻接点构成链表，并将各链表的表头指针合在一起。 将每个顶点的邻接点构成链表 对应关系 例： data firstadj 1 2
吉林财经大学管理科学与信息工程学院
4 1 1 2
^ ^ ^ 3 ^
14
5.2 图的存储
用邻接表存储网络 6 9 B 8
A 5
D 2 C
data firstadj
A B C D
B 5 C 8∧ D 2∧ B 9∧
D 6∧
吉林财经大学管理科学与信息工程学院
15
5.3 图的遍历
图的遍历——按某种次序访问图中所有顶点一次且仅 按某种次序访问图中所有顶点一次且仅 图的遍历 且一次。 且一次。
数 据 结 构
第五章 图
Data Structures
吉林财经大学管理科学与信息工程学院
1
第五章 图 (Graph)
第五章 图（Graph)
5.1 基本概念和运算 5.2 图的存储 5.3 图的遍历 5.4 最小生成树 5.5 5.6 有向无环图的应用 最短路径
吉林财经大学管理科学与信息工程学院
2
吉林财经大学管理科学与信息工程学院
3
4
图G1 有向图示例
6
5.1 基本概念和运算
路径 ——若 顶点序列 i1，Vi2，…，Vij， 若 顶点序列V ， 满足< 满足 Vik，Vi(k+1)>∈E或 ∈ 或 ）（k=1,2,…,j-1）， 者(Vik，Vi(k+1))∈E）（ ∈ ）（ ）， 则该顶点序列V 则该顶点序列 i1，Vi2，…，Vij ， 构成一条路径。 构成一条路径。 例: 图G1中，1,2,4,1,3,4是一条路径 中 是一条路径