第 8章 图图的基本概念图的存储结构图的遍历生成树最短路径拓扑排序关键路径图的基本概念图,是一种数据结构，它的形式化定义为 Graph=（ V，
E）,其中 V是图中结点（ Vertices）的非空有限集,E
是图中边（ Edges）的有限集。
无向图,图上的每条边都没有方向，即两个顶点对
（ V1,V2）和（ V2,V1）代表同一边。
有向图,图上的每条边都是有方向的，即两个顶点对
（ V1,V2）和（ V2,V1）代表两条边。
有向完全图,对于有向图，有 n(n-1)条弧的有向图。
无向完全图,对于无向图，有 n(n-1)/2条边的无向图。
权,与图的边或弧相关的数叫做权 (weight)，权反应了这条边或弧的某种特征的数据。
网,带权的图。
实例：
子图,有两个图 G=(V,E)和 G′=(V′,E′),如果
V′?V且 E′?E，则称 G′ 为 G的子图。
实例：
弧头和弧尾,有向图中存在 <vi,vj>，称弧的始点 vi为弧尾，弧的终点 vj为弧头。
出边和入边,有向图中存在 <vi,vj>，称该弧为始点 vi
的出边，终点 vj的入边。
度,无向图 G=(V,E)，边 (v,v′)?E，称顶点 v和 v′
互为邻接点 (adjacent);边 (v,v′) 依附 (incident)于顶点 v和 v′,或说边 (v,v′) 和顶点 v与 v′ 相关联 ;顶点 v
的度 (degree)是和顶点 v相关联的边的数目，记为
TD(V)。
入度,以顶点 v为头的弧的数目，称为 v的入度，记为
ID（ v）。
出度,以顶点 v为尾的弧的数目，称为 v的出度，记为
OD（ v）。
顶点的度,顶点的度 TD（ v） =ID（ v） +OD（ v）。
路径,无向图 G = (V,E)中从顶点 v到顶点 v?的路径 (path)
是一个顶点序列 (v,vi,0,vi,1,vi,2vi,m,v?)，其中 (vi,j-
1,vi,j)?E,1?j?m；如果 G是有向图，则路径也是有向的顶点序列，应满足?vi,j-1,vi,jE,1?j?m。
路径的长度,路径上的边或弧的数目。
回路或环,第一个顶点和最后一个顶点相同的路径。
简单路径,序列中顶点不重复出现的路径。
简单回路,一条简单路径，其长度?2，且路径的起始点和终止点是同一顶点的路径。
连通图,在无向图中，从顶点 v到顶点 v?有路径，则称 v和
v?是连通的；如果图中任意两个顶点 vi,vj?V,vi和 vj都是连通的，则称 G是连通图。
连通分量,无向图中极大连通子图。
强连通图,有向图 G中，如果对于每一对 vi,vj?V，
vi?vj,从 vi到 vj和从 vj到 vi都存在路径，则称 G是强连通图。
强连通分量,有向图中的极大连通子图称为有向图的强连通分量。
实例：
(a) 无向图 G5 (b)G5的三个连通分量生成树,为一个极小连通子图，含有图中的全部顶点，
只有足以构成一棵树的 n-1条边。
实例：
有向树,一个有向图恰好有一个顶点入度为 0，其余顶点入度为 1，则为有向树。
生成森林,有向图的生成森林由若干棵有向树组成，含有图中全部顶点，只含有足以构成若干棵不相交的有向树的弧 。
图的存储结构邻接矩阵邻接表邻接矩阵表示法概念,用二维数组存储图中顶点的信息，用矩阵表示图中各个顶点（数据元素）之间的关系（边或弧）的信息；
设 G=（ V,E）是具有 n个顶点的图，则 G的邻接矩阵是具有如下性质的 n阶方阵,
网的邻接矩阵,网 G=(V,E)含有 n(?1)个顶点 V=
（ v1,v2,vn），则元素为：
图及其邻接矩阵实例：
网及其邻接矩阵实例：
返回概念,图的一种顺序存储结构和链式存储结构相结合的存储方法；用一维数组表示顶点结点
Vertex域存放与顶点有关的信息； FirstArc为指针域，存放与该结点相邻接的所有顶点组成的单链表的头指针 ；
邻接单链表中每个结点表示依附于该顶点的一条边，称作边结点，边结点的结构为：
Adjvertex：存放依附于该边的另一个顶点在一维数组中的序号； Weight域存放边和该边有关的信息 ； Nextarc域为指向依附于该顶点的下一个边结点的指针 。
邻接表
Vertex FirstArc
Adjvertex Weight Nextarc
实例：
返回图的遍历图的遍历,从图中任一顶点出发访遍图中所有顶点，
且使每一个顶点仅被访问一次的过程。
深度优先搜索：
遍历过程,首先访问指定的起始顶点 v0，从 v0出发在访问了任意一个和 v0邻接的顶点 w1之后，再从
w1出发，访问和 w1邻接且未被访问过的任意顶点
w2，然后从 w2出发，重复上述过程，直到图中所有和 v0有路径相通的顶点都被访问过；如若仍有未被访问过的顶点，则另选图中一个未曾被访问过的顶点作起始点，重复上述过程，直至图中所有顶点都被访问到为止。
实例：
图 a,V1?V2?V4?V8?V5?V6?V3?V7
图 b,V5?V7?V6?V2?V4?V3?V1
广度优先搜索：
遍历过程,首先访问指定的起始顶点 v0，从 v0出发，访问 v0的所有未被访问过的邻接顶点 w1,w2,…,然后再依次从 w1,w2,… 出发，访问他们的所有未被访问过的邻接顶点如此下去，直到图中所有被访问过的顶点的邻接顶点都被访问过；若此时图中还有未被访问过的顶点，则从一个未被访问过的顶点出发，重复上述过程，
直到图中所有的顶点都被访问过为止。
实例：
遍历结果,V5?V6?V7?V2?V4?V1?V3
生成树生成树,图中的顶点加上遍历时经过的所有边所构成的子图。
生成森林,对于一个非连通图和不是强连通的有向图，
从任一点出发，不能访问到图中所有顶点，只能得到连通分量的生成树，所有连通分量的生成树成生成森林。
实例：
最小代价生成树,选择一棵生成树，使总的费用（一 棵生成树的代价就是树上各边的代价之和 ）最小。
MST的性质,假设 N=（ V,E）是一个连通网,U是顶点集 V的一个非空子集。若（ u,v）是一条具有最小权值
（代价）的边，其中 u?U,v?V-U，则必存在一棵包含边（ u,v）的最小生成树 。
构造最小生成树的算法：
普里姆（ Prim）算法克鲁斯卡尔（ Kruskal）算法普里姆（ Prim）算法算法描述：
U={u1},T={}
While (U!=V) do
(u,v)=min{Wuv; u?U,v?V-U}
T=T+{(u,v)}
U=U+{v}
结束。
实例：
a
实例分析：
克鲁斯卡尔（ Kruskal）算法遍历过程,T是无向连通网 N=（ V,E）的最小生成树，
E（ T）是其边集，则构造最小生成树的步骤如下：
T的边集 E（ T）有初态为空集； T中只有 n个顶点，每个顶点都自成一个分量。
当 E中边数小于 n-1时，重复执行。
在无向连通网 N的边集 E中选择权值最小的边 <vi,vj>，并从 E中删除它。
如果 vi,vj落在 T中不同的连通分量上，
则将此边加入到 T中去，否则丢掉该边，
继续在 E中选择一条权值最小的边。
实例：
最短路径概念：
源点,路径开始的顶点。
终点,最后的顶点。
最短路径有两类：
第一类是从一个顶点到其它各个顶点的最短路径。
第二类是求每一对顶点间的最短路径。
单源最短路径概念,从一个确定的顶点 v到其余顶点的最短路径问题实例：
从 V1到 V6有四条不同路径：
<V1,V3,V4,V5,V6>，长度,21（最短路径）
<V1,V5,V6>长度,32
<V1,V7,V6>长度,49
<V1,V2,V6>2长度,22
迪杰斯特拉（ Dijkstra）算法描述：
用带权的邻接矩阵 cost来表示带权的有向图，
cost[i][j]为弧 <vi,vj>上的权值（ <vi,vj>存在）
或为?（弧 <vi,vj>不存在，即 vi和 vj之间没有弧 dist[i]=cost[v][vi] vi?V。
选择 vj，使得 dist[j]=min{dist[i]?vi?V-S}令
S=S?{ vj } 。
修改从 v出发到集合 V-S上任一顶点 vk可达的最短路径长度，如果 dist[j]+cost[j][k]<dist[k]，
则 dist[k]= dist[j]+cost[j][k]。
重复执行（ 2）、（ 3）直到再也没有可加入到 S中的顶点为止 。
拓扑排序概念,设 S是一个集合,R是 S上的一个关系,a和 b是 S
中的任意元素：
若 (a,b)?R，则称 a是 b关于 R的前趋元素,b是 a关于
R的后继元素。
若 a,b,c是 S中的任意元素，若 (a,b)?R,(b,c)
R，则必有（ a,c）?R，则 R是 S上的传递关系。
若对于 S中任一元素 a，不存在（ a,a）?R，则称 R
是 S上的一个非自反关系。
若 S上的一个关系 R是传递关系且是非自反的，则称 R
是 S上的偏序关系。
若 R是集合 S上的一个偏序关系,A =（ ai,aj） A是 S
中元素的一个序列，且当（ ai,aj）?R时，有 i < j，
则称 A是相对于 R的一个拓扑序列。
AOV-网络,在一个有向图 G中，若用顶点表示活动或任务，用边表示活动（或任务）之间的关系。
AOV-网拓扑排序算法的基本步骤：
在网络中选取一个没有前趋的顶点，且把它输出。
从网络中删除该顶点和以它为尾的所有出边。
重复执行上述两个步骤，直到所有顶点都被输出，
或者直到遗留在网络上的顶点都有前趋顶点为止。
实例：
拓扑有序序列：
V1?V3?V7?V4?V9?V2?V5?V8?V6
其邻接表：
关键路径概念：
AOE-网,在带权的有向图中，用顶点表示事件，用弧表示活动，权表示活动持续的时间，这样组成的网称为以边表示活动的网。
起始点,入度为 0的顶点。
结束点,出度为 0的顶点。
关键路径,从源点到汇点具有最大长度的路径。
关键活动,关键路径上的活动。
事件 vi可能的最早发生时间 VE(i),是从源点 v1到顶点 vi
的最长路径长度。
事件 vk的最迟发生时间 VL(k),汇点 vn的最早发生时间
VE(n)减去 vk 到 vn的最长路径长度。
活动 ai的最早开始时间 E(i),事件 vi最早发生时间，即
VE(i)=E(i) 。
活动 ai的最迟开始时间 L(i),ai的最迟完成时间减去 ai的持续时间，即 L(i)=VL(k) - <vj,vk>的权。
实例：
E）,其中 V是图中结点（ Vertices）的非空有限集,E
是图中边（ Edges）的有限集。
无向图,图上的每条边都没有方向，即两个顶点对
（ V1,V2）和（ V2,V1）代表同一边。
有向图,图上的每条边都是有方向的，即两个顶点对
（ V1,V2）和（ V2,V1）代表两条边。
有向完全图,对于有向图，有 n(n-1)条弧的有向图。
无向完全图,对于无向图，有 n(n-1)/2条边的无向图。
权,与图的边或弧相关的数叫做权 (weight)，权反应了这条边或弧的某种特征的数据。
网,带权的图。
实例：
子图,有两个图 G=(V,E)和 G′=(V′,E′),如果
V′?V且 E′?E，则称 G′ 为 G的子图。
实例：
弧头和弧尾,有向图中存在 <vi,vj>，称弧的始点 vi为弧尾，弧的终点 vj为弧头。
出边和入边,有向图中存在 <vi,vj>，称该弧为始点 vi
的出边，终点 vj的入边。
度,无向图 G=(V,E)，边 (v,v′)?E，称顶点 v和 v′
互为邻接点 (adjacent);边 (v,v′) 依附 (incident)于顶点 v和 v′,或说边 (v,v′) 和顶点 v与 v′ 相关联 ;顶点 v
的度 (degree)是和顶点 v相关联的边的数目，记为
TD(V)。
入度,以顶点 v为头的弧的数目，称为 v的入度，记为
ID（ v）。
出度,以顶点 v为尾的弧的数目，称为 v的出度，记为
OD（ v）。
顶点的度,顶点的度 TD（ v） =ID（ v） +OD（ v）。
路径,无向图 G = (V,E)中从顶点 v到顶点 v?的路径 (path)
是一个顶点序列 (v,vi,0,vi,1,vi,2vi,m,v?)，其中 (vi,j-
1,vi,j)?E,1?j?m；如果 G是有向图，则路径也是有向的顶点序列，应满足?vi,j-1,vi,jE,1?j?m。
路径的长度,路径上的边或弧的数目。
回路或环,第一个顶点和最后一个顶点相同的路径。
简单路径,序列中顶点不重复出现的路径。
简单回路,一条简单路径，其长度?2，且路径的起始点和终止点是同一顶点的路径。
连通图,在无向图中，从顶点 v到顶点 v?有路径，则称 v和
v?是连通的；如果图中任意两个顶点 vi,vj?V,vi和 vj都是连通的，则称 G是连通图。
连通分量,无向图中极大连通子图。
强连通图,有向图 G中，如果对于每一对 vi,vj?V，
vi?vj,从 vi到 vj和从 vj到 vi都存在路径，则称 G是强连通图。
强连通分量,有向图中的极大连通子图称为有向图的强连通分量。
实例：
(a) 无向图 G5 (b)G5的三个连通分量生成树,为一个极小连通子图，含有图中的全部顶点，
只有足以构成一棵树的 n-1条边。
实例：
有向树,一个有向图恰好有一个顶点入度为 0，其余顶点入度为 1，则为有向树。
生成森林,有向图的生成森林由若干棵有向树组成，含有图中全部顶点，只含有足以构成若干棵不相交的有向树的弧 。
图的存储结构邻接矩阵邻接表邻接矩阵表示法概念,用二维数组存储图中顶点的信息，用矩阵表示图中各个顶点（数据元素）之间的关系（边或弧）的信息；
设 G=（ V,E）是具有 n个顶点的图，则 G的邻接矩阵是具有如下性质的 n阶方阵,
网的邻接矩阵,网 G=(V,E)含有 n(?1)个顶点 V=
（ v1,v2,vn），则元素为：
图及其邻接矩阵实例：
网及其邻接矩阵实例：
返回概念,图的一种顺序存储结构和链式存储结构相结合的存储方法；用一维数组表示顶点结点
Vertex域存放与顶点有关的信息； FirstArc为指针域，存放与该结点相邻接的所有顶点组成的单链表的头指针 ；
邻接单链表中每个结点表示依附于该顶点的一条边，称作边结点，边结点的结构为：
Adjvertex：存放依附于该边的另一个顶点在一维数组中的序号； Weight域存放边和该边有关的信息 ； Nextarc域为指向依附于该顶点的下一个边结点的指针 。
邻接表
Vertex FirstArc
Adjvertex Weight Nextarc
实例：
返回图的遍历图的遍历,从图中任一顶点出发访遍图中所有顶点，
且使每一个顶点仅被访问一次的过程。
深度优先搜索：
遍历过程,首先访问指定的起始顶点 v0，从 v0出发在访问了任意一个和 v0邻接的顶点 w1之后，再从
w1出发，访问和 w1邻接且未被访问过的任意顶点
w2，然后从 w2出发，重复上述过程，直到图中所有和 v0有路径相通的顶点都被访问过；如若仍有未被访问过的顶点，则另选图中一个未曾被访问过的顶点作起始点，重复上述过程，直至图中所有顶点都被访问到为止。
实例：
图 a,V1?V2?V4?V8?V5?V6?V3?V7
图 b,V5?V7?V6?V2?V4?V3?V1
广度优先搜索：
遍历过程,首先访问指定的起始顶点 v0，从 v0出发，访问 v0的所有未被访问过的邻接顶点 w1,w2,…,然后再依次从 w1,w2,… 出发，访问他们的所有未被访问过的邻接顶点如此下去，直到图中所有被访问过的顶点的邻接顶点都被访问过；若此时图中还有未被访问过的顶点，则从一个未被访问过的顶点出发，重复上述过程，
直到图中所有的顶点都被访问过为止。
实例：
遍历结果,V5?V6?V7?V2?V4?V1?V3
生成树生成树,图中的顶点加上遍历时经过的所有边所构成的子图。
生成森林,对于一个非连通图和不是强连通的有向图，
从任一点出发，不能访问到图中所有顶点，只能得到连通分量的生成树，所有连通分量的生成树成生成森林。
实例：
最小代价生成树,选择一棵生成树，使总的费用（一 棵生成树的代价就是树上各边的代价之和 ）最小。
MST的性质,假设 N=（ V,E）是一个连通网,U是顶点集 V的一个非空子集。若（ u,v）是一条具有最小权值
（代价）的边，其中 u?U,v?V-U，则必存在一棵包含边（ u,v）的最小生成树 。
构造最小生成树的算法：
普里姆（ Prim）算法克鲁斯卡尔（ Kruskal）算法普里姆（ Prim）算法算法描述：
U={u1},T={}
While (U!=V) do
(u,v)=min{Wuv; u?U,v?V-U}
T=T+{(u,v)}
U=U+{v}
结束。
实例：
a
实例分析：
克鲁斯卡尔（ Kruskal）算法遍历过程,T是无向连通网 N=（ V,E）的最小生成树，
E（ T）是其边集，则构造最小生成树的步骤如下：
T的边集 E（ T）有初态为空集； T中只有 n个顶点，每个顶点都自成一个分量。
当 E中边数小于 n-1时，重复执行。
在无向连通网 N的边集 E中选择权值最小的边 <vi,vj>，并从 E中删除它。
如果 vi,vj落在 T中不同的连通分量上，
则将此边加入到 T中去，否则丢掉该边，
继续在 E中选择一条权值最小的边。
实例：
最短路径概念：
源点,路径开始的顶点。
终点,最后的顶点。
最短路径有两类：
第一类是从一个顶点到其它各个顶点的最短路径。
第二类是求每一对顶点间的最短路径。
单源最短路径概念,从一个确定的顶点 v到其余顶点的最短路径问题实例：
从 V1到 V6有四条不同路径：
<V1,V3,V4,V5,V6>，长度,21（最短路径）
<V1,V5,V6>长度,32
<V1,V7,V6>长度,49
<V1,V2,V6>2长度,22
迪杰斯特拉（ Dijkstra）算法描述：
用带权的邻接矩阵 cost来表示带权的有向图，
cost[i][j]为弧 <vi,vj>上的权值（ <vi,vj>存在）
或为?（弧 <vi,vj>不存在，即 vi和 vj之间没有弧 dist[i]=cost[v][vi] vi?V。
选择 vj，使得 dist[j]=min{dist[i]?vi?V-S}令
S=S?{ vj } 。
修改从 v出发到集合 V-S上任一顶点 vk可达的最短路径长度，如果 dist[j]+cost[j][k]<dist[k]，
则 dist[k]= dist[j]+cost[j][k]。
重复执行（ 2）、（ 3）直到再也没有可加入到 S中的顶点为止 。
拓扑排序概念,设 S是一个集合,R是 S上的一个关系,a和 b是 S
中的任意元素：
若 (a,b)?R，则称 a是 b关于 R的前趋元素,b是 a关于
R的后继元素。
若 a,b,c是 S中的任意元素，若 (a,b)?R,(b,c)
R，则必有（ a,c）?R，则 R是 S上的传递关系。
若对于 S中任一元素 a，不存在（ a,a）?R，则称 R
是 S上的一个非自反关系。
若 S上的一个关系 R是传递关系且是非自反的，则称 R
是 S上的偏序关系。
若 R是集合 S上的一个偏序关系,A =（ ai,aj） A是 S
中元素的一个序列，且当（ ai,aj）?R时，有 i < j，
则称 A是相对于 R的一个拓扑序列。
AOV-网络,在一个有向图 G中，若用顶点表示活动或任务，用边表示活动（或任务）之间的关系。
AOV-网拓扑排序算法的基本步骤：
在网络中选取一个没有前趋的顶点，且把它输出。
从网络中删除该顶点和以它为尾的所有出边。
重复执行上述两个步骤，直到所有顶点都被输出，
或者直到遗留在网络上的顶点都有前趋顶点为止。
实例：
拓扑有序序列：
V1?V3?V7?V4?V9?V2?V5?V8?V6
其邻接表：
关键路径概念：
AOE-网,在带权的有向图中，用顶点表示事件，用弧表示活动，权表示活动持续的时间，这样组成的网称为以边表示活动的网。
起始点,入度为 0的顶点。
结束点,出度为 0的顶点。
关键路径,从源点到汇点具有最大长度的路径。
关键活动,关键路径上的活动。
事件 vi可能的最早发生时间 VE(i),是从源点 v1到顶点 vi
的最长路径长度。
事件 vk的最迟发生时间 VL(k),汇点 vn的最早发生时间
VE(n)减去 vk 到 vn的最长路径长度。
活动 ai的最早开始时间 E(i),事件 vi最早发生时间，即
VE(i)=E(i) 。
活动 ai的最迟开始时间 L(i),ai的最迟完成时间减去 ai的持续时间，即 L(i)=VL(k) - <vj,vk>的权。
实例：
