? 3.6.1 图的基本概念
3.6.2 图的存储
3.6.3 图的遍历
3.6.4 图的应用
3.6 图
3.6.1 图的基本概念
BA C
D 6
3
2
1
5数据结构 B=（ D,R）
图,G=（ V,E）
顶 点,图中的数据元素
V：表示 顶 点的非空有限集合。
E,表示两个 顶 点之间关系的集合。
图的定义、术语图有向图无向图在有向图中,<V1,V3>表示从 V1到 V3的一条弧。
V1为弧尾或初始点,V3为弧头或终端点。
在无向图中,(V1,V3)表示 V1和 V3之间的一条边 。
V1 V3
V2 V4
V1 V3
V2 V4
图的定义、术语
V1 V3
V2 V4
V1 V3
V2 V4
顶点集合 V={V1,V2,V3,V4 }
弧的集合 G={<V1,V3>,<V3,V4>,
<V2,V4>,<V4,V1>}
顶点集合 V={V1,V2,V3,V4 }
边的集合 E={(V1,V3),(V1,V2),
(V1,V4),(V2,V4)}
G=( V,E )
顶点 (V1,V3)与 (V3,V1)表示同一条边图的定义、术语
BA C
D 6
3
2
1
5
权,与图的边或弧相关的数。
顶点的度,依附于该顶点的边数或弧数。
出度,（仅对有向图）以该顶点为尾的弧数。
入度,（仅对有向图）以该顶点为头的弧数。
路径,顶点 A与顶点 C之间存在一条路径。路径上边或弧的数目称为该路径的路径长度。
连通图,无向图任意两顶点都有路径（ 没有孤立顶点）
强连通图,有向图 任意两顶点都有路径网,带权的图称为网图的定义、术语图的存储 邻接矩阵
3.6.2 图的存储
1,邻接矩阵法
（ 1）给顶点编号
（ 2）建立邻接（关系）矩阵
2
1 4
3
1 2 3 4
1
2
3
4
0 0 0 0
1 0 1 1
1 0 0 1
0 1 1 0
a i j表示弧 < i,j >
1：表示有弧； 0:表示无弧任意顶点的出度是该行元素之和任意顶点的入度是该列元素之和图的存储 邻接矩阵
邻接矩阵的优点：
增减边的操作简单
邻接矩阵的缺点：
增减顶点的操作需要搬移大量的元素，
浪费存储空间
2
1 4
3
1 2 3 4
1
2
3
4
0 1 1 0
1 0 1 1
1 1 0 1
0 1 1 0 无向图的邻接矩阵是对称的图的存储 邻接矩阵的实现
图的邻接矩阵实现
typedef struct graph_m{
elemtype node[MAXNUM];
int arcs[MAXNUM][MAXNUM];
}graph_m;
顶点集合边的邻接矩阵二维数组图的存储 邻接表
2,邻接表法
一个邻接表由两种结构组成
存放各顶点元素的数组，头结点
各顶点各自的邻接链表，邻接结点
2
1 4
3
2 31 data
2 data
3 data
4 data
1 3 4
1 2 4
2 3
3 data顶点号元素域邻接链表头指针
2
邻接顶点号下一邻接结点图的存储（课堂练习）
请写出下面这副图的邻接表
1）给顶点编号
2）建立顶点数组
3）建立各顶点的邻接链表
注意，此图为有向图
2
1
3
4
51 data
2 data
3 data
4 data
5 data
2 3
1 3
5
1
4
图的存储 邻接表的实现
邻接表的定义
头结点的定义
邻接结点的定义顶点号 元素域 与头结点相邻的顶点
typedef struct headnode{
int node_index;
elemtype data;
struct adj_node * next_adj;
} headnode;
顶点号下一个与头结点相邻的顶点的邻接结点
typedef struct adj_node{
int node_index;
struct adj_node *next_adj;
}adj_node;
图的存储 邻接表
图邻接表的定义
typedef struct graph_l{
headnode node_list[MAXNUM];
int node_num;
}graph_l;
2 31 data
2 data
3 data
4 data
1 3 4
1 2 4
2 3
图的存储 邻接表
2
1 4
3
2 31 data
2 data
3 data
4 data
1 3 4
1 2 4
2 3
2
1 4
3
1 data
2 data
3 data
4 data
1 3 4
1
3
4
注意：有向图与无向图的区别图的存储
图的邻接表存储法的特点
优点
节省存储空间
边的插入和删除操作比较简便
缺点
结构复杂
具有两种不同的基本组成单元图的存储
3,边带权值的图的存储
1）在邻接矩阵中的实现
0 2 3 5
2 0 1 0
3 1 0 1
5 0 1 0
a[4][4] =
a[ i ][ j ]：记录边的权值；为 0表示无边
1
2 4
3
2
3
5
1 1
图的存储
3,边带权值的图的存储
2）在邻接表中的实现
在邻接结点结构中增加一个权值域
1 data
2 data
3 data
4 data
2 3 3 2
1 1 3 5 4 10
2 3
3 1
顶点号 边权值
1
2 4
3
3
2
5 1
1
10 3
图的遍历
3.6.3 图的遍历
问题：
1）对于连通图，从一个顶点出发沿着所有可能的路径，是否可以将所有的顶点遍历到。
2）图中有回路，遍历算法可能产生死循环。
有重复的路径称为 回路 2
1 4
3
图的遍历 深优
1,深度优先遍历
（ 1）从一个未访问过的顶点开始，访问它的一个未访问过的相邻顶点。
（ 2）如果顶点的所有相邻顶点都是已访问过的，
则需要回溯到之前的一个顶点，选取它的另一个未被访问的相邻顶点。
（ 3）对于前两个步骤是递归的图的遍历 深优
1,深度优先遍历
（ 1）从一个未访问过的顶点开始，访问它的一个未访问过的相邻顶点。
（ 2）如果顶点的所有相邻顶点都是已访问过的，
则需要回溯到之前的一个顶点，选取它的另一个未被访问的相邻顶点。
（ 3）对于前两个步骤是递归的
1
2
5
84
6
3
7
1 73 6 5 28 4
回到 8
1 73 6 528 4
1 3 6 8 4 2 5 7
或者按以下顺序遍历：
注意使用栈支持递归：
图的遍历 深优
深度优先遍历的特点
“深度”：总是访问顶点的 一个 相邻顶点，好像是沿着图中的一条路径走到“底”，然后后退一点，再选一条路。如此“进进退退”，直到所有顶点都被访问
对于连通图，如果第一个被访问的顶点的所有相邻顶点都被访问了，意味着图中所有顶点都被访问了。
即栈空时图的遍历 深优
用递归调用实现深度优先遍历算法
void dfs （ g,v） {
}
1访问顶点 v；visit（ v）； visited[ v ] = 1;
p = g[v]->next_adj
while(p != NULL){
w = p->node_index;
if(visited[w] == 0)
p = p->next_adj;
}
2取得顶点的一个未被访问过的顶点 w；
3 dfs（ g,w）；回到 2；
4重复 2,3直到该顶点所有的相邻顶点都被访问过；
dfs(g,w);
1
2
3
4
5
void dfs（ g,v） {
visited[ v ] = 1;
p = g[ v ]->next_adj
while(p != NULL){
w = p->node_index;
if(visited[ w ] == 0)
dfs( g,w );
p = p->next_adj;
}}
void dfs（ g,2） {
visited[ 2 ] = 1;
p = g[ 2 ]->next_adj
while(p != NULL){
w = p->node_index;
if(visited[ 3 ] == 0)
dfs( g,3 );
p = p->next_adj;
}
}
void dfs（ g,3） {
visited[ 3 ] = 1;
p = g[ 3 ]->next_adj
while(p != NULL){
w = p->node_index;
if(visited[ 4 ] == 0)
dfs( g,4 );
p = p->next_adj;
}
}
void dfs（ g,4） {
visited[ 4 ] = 1;
p = g[ 4 ]->next_adj
while(p != NULL){
w = p->node_index;
if(visited[ w ] == 0)
dfs( g,w );
p = p->next_adj;
}
}
void dfs（ g,5） {
visited[ 5 ] = 1;
p = g[ 5 ]->next_adj
while(p != NULL){
w = p->node_index;
if(visited[ w ] == 0)
dfs( g,w );
p = p->next_adj;
}}
（,1）
1
1
2 ] == 0)
2 );
}
}
5
(,5 );
图的遍历 广优
2,广度优先遍历
访问顶点 v后，接着依次访问 v的所有邻接顶点，
再依次访问这些邻接顶点的邻接顶点。直到所有的顶点都被访问过。
1
2
5
84
6
3
7
1 2 3 4 5 6 7 8
注意,8是作为哪个顶点的邻接顶点被访问的？
1 2 3 4 5 6 7 8
体会队列操作方式：
图的遍历 广优
广度优先遍历的特点
“广度”：总是在访问了一个顶点后，依次访问它的所有相邻顶点。然后再从它的第一个相邻顶点开始，访问其所有的相邻顶点。如此逐个顶点地逐步扩散，直到所有的顶点都被访问。
广度优先遍历操作具有队列操作的特点，当从队列中取出最后一个顶点，发现该顶点的所有相邻顶点都被访问过时，意味着图中所有的顶点都已被访问过生成树与图
3.6.4 图的应用
1,生成树定义
假设存在这样一颗树：
树结点的集合与图的顶点集合相等
树的分支全部由图的边组成。
称这颗树是这幅 图的生成树
生成树是图的,
子集 /子图
是一个不包含回路的子图
图的生成树是
2
1 4
3
2
1 4
3
2
1
4
3
不唯一的！
唯一的！取决于遍历方法和遍历的起始点生成树的示例
A D
B E
C
( a ) D F S 生成树
A D
B E
C
( b ) B F S 生成树生成树与图对于一个有 n个顶点 的连通图 G，
其生成树包含了 条边。
深度优先搜索得到的生成树 广度优先搜索得到的生成树
n－ 1
权值生成树与图
2,最小费用生成树（ 通信网络、交通网络）
在图所有生成树中，边的权值总和最小的生成树
1
2 4
5 6
3
6
5
3 6
6
4 2
4
1
6
1
2 4
5 6
3
边
1－ 3 1
4－ 6 2
2－ 5 3
1－ 4 4
3－ 6 4
2－ 3 5
1－ 2 6
3－ 5 6
5－ 6 6将边按权值大小排列生成树与图
算法分析
关键技术：
为什么在（ 1,4）边选中后不能选（ 3,6）边
在选择（ 3,6）边和（ 2,3）边时有什么不同，怎样设置条件以区别？
当时 3和 6位于同一图中,2,5和 3位于不同的图中
1
2 4
5 6
3
6
5
3 6
6
4 2
4
1
6
1
2 4
5 6
31－ 4 4
3－ 6 4
2－ 3 5
－－ 回路生成树与图
1
2 4
5 6
3
……
1）开始时所有的节点都位于不同的图中
2）选择一条连接两个不同子图的最短边
3）连接以后两个子图的所有顶点都要改为在一个子图中
4）当所有的顶点都位于一个子图中，
算法结束。
权值边
1－ 3 1
4－ 6 2
2－ 5 3
1－ 4 4
3－ 6 4
2－ 3 5
1－ 2 6 思考既然是颗树，如果选择边数为 n－
1个时可不可以结束算法呢？
算法的优化图的最短路径
3,最短路径
图中两个顶点之间有 条路径
最短路径：
是路径中边（弧）的权值总和最小的路径
计算机网络中常使用最短路径算法计算最佳路径
交通网络中使用最短路径算法计算最短旅途多
Dijkstra Algorithm
Floyd Algorithm
A1
A2
A4
A3
A5
2 6
5
1
2
1
5
1）初始化时，设 A1到其它不直连顶点距离为 ∞
寻找 A1到所有节点的最短路径
A2
A3
A4
A5
顶点 距离 路径
2）选择距离最短的路径
3）观察通过新选择的路径是否能更短地到达其它顶点
4）选择出的最短路径将不参加下一轮比较
5）反复 2 - 4步，直到不剩有顶点
2
6
5
∞
A2
A3
A4
A1 A2 A3－－ 3 更新A1 A2 A33
A1 A2 A4－－ ∞
A1 A2 A5－－ 4
3 A4－－ 4 更新A1 A2 A3 A44
3 A5－－ 8A1 A2 A54 4 A5－－ ∞更新
Dijkstra Algorithm
拓 扑 排 序按一定顺序进行的活动,可以使用顶点表示活动,顶点之间的有向边表示活动间的先后关系的有向图来表示,这种有向图称为顶点表示活动网络 (Activity On Vertex network,简称
AOV网 )。
AOV网中的有向边表示了活动之间的制约关系 。
4,拓 扑 排 序将 AOV网中的所有顶点排列成一个线性序列 vi1,vi2,…,vin,并且这个序列同时满足关系：若在 AOV网中从顶点 vi到顶点 vj存在一条路径,则在线性序列中 vi必在 vj之前,我们就称这个线性序列为 拓扑序列 。 把对 AOV网构造拓扑序列的操作称为 拓扑排序 。
在实际的意义上,AOV网中存在的有向环就意味着某些活动是以自己为先决条件,这显然是荒谬的 。 例如对于程序的数据流图而言,AOV网中存在环就意味着程序存在一个死循环 。
任何一个无环的 AOV网中的所有顶点都可排列在一个拓扑序列里,
拓扑排序的基本操作如下：
(1) 从网中选择一个入度为 0的顶点并且输出它 。
(2) 从网中删除此顶点及所有由它发出的边 。
(3) 重复上述两步，直到网中再没有入度为 0的顶点为止。
C
1
C
4
C
2
C
3
C
5
C
7
C
8
C
10
C
12
C
9
C
11
C
6
以上的操作会产生两种结果：
一 种是网中的全部顶点都被输出,整个拓扑排序完成；
另一种是网中顶点未被全部输出,剩余的顶点的入度均不为 0,则说明网中存在有向环 。
用以上操得到了一种拓扑序列：
C1,C2,C3,C4,C5,C7,C9,C10,C12,C11,C6,C8。
拓扑序列可以是 种多
AOV网拓扑排序过程
C
4
C
3
C
5
C
7
C
8
C
10
C
12
C
9
C
11
C
6
( a ) 输出 C
1
后
C
2
C
4
C
3
C
5
C
7
C
8
C
10
C
12
C
9
C
11
C
6
( b ) 输出 C
2
后
C
8
C
10
C
12
C
9
C
11
C
6
( c ) 输出 C
3
,C
4
,C
5
,C
7
后
C
8
C
6
( d ) 输出 C
9
,C
1 0
,C
1 2
,C
1 1
后 ( e ) 输出 C
6
,C
8
后在邻接表存储结构中实现拓扑排序算法的步骤为：
(1) 扫描顶点表,将入度为 0的顶点入栈 。
(2) 当栈非空时执行以下操作：
{ 将栈顶顶点 vi的序号弹出,并输出之；
检查 vi的出边表,将每条出边表邻接点域所对应的顶点的入度域值减 1,若该顶点入度为 0,则将其入栈；
}
(3) 若输出的顶点数小于 n,则输出,有回路,,否则拓扑排序正常结束 。
关 键 路 径
5,关键路径
AOE网络 (Activity On Edge network)：
有向边：表示一个子工程 （ 活动 ）
边上的权值：表示一个活动持续的时间顶点：表示事件,它表示了一种状态,即它的入边所表示的活动均已完成,它的出边所表示的活动可以开始 。
这种带权的有向网络称为 AOE网络 (Activity On Edge network),即边表示活动网络 。
一个 AOE网络的示例
v
2
v
3
v
5
v
6
v
4
v
7
v
1
a
1
＝ 3
a
2
＝ 2
a
4
＝ 4
a
5
＝ 3
a
6
＝ 7
a
3
＝ 8
a
7
＝ 4
a
8
＝ 2
a
9
＝ 9
a
1 0
＝ 6
关键路径：
从源点到汇点的具有最大路径长度的路径 。
关键活动：
关键路径上的各个活动 。
明确了哪些活动是关键活动就可以设法提高关键活动的功效,
以便缩短整个工期 。
nj2,Ev,v )}ji,d u r (( i )m a x { v( j )v
0( 1 ) v
1jiee
e
其中 E1是网络中以 vj为终点的入边集合,dur(<i,j>)是有向边 <vi,vj>上的权值 。
vl(j)的计算可从汇点开始,向源点逆推计算：
(13.2)
其中 E2是网络中以 vj为起点的出边集合 。
1-nj2Ev,v )}k j,d u r (-( k )m i n { v( j )v
n)(vn)(v
2kjll
el
(1)
(2)
ve(j)的计算可 从 源点 开始 利用以下的递推公式求得
ve(1)=0
ve(2)=max{ve(1)+dur(<1,2>)}=max{0+3}=3
ve(3)=max{ve(1)+dur(<1,3>)}=max{0+2}=2
ve(4)=maw{ve(2)+dur(<2,4>),ve(3)+dur(<3,4>)}=max{3+4,2+3}=7
ve(5)=max{ve(4)+dur(<4,5>),ve(2)+dur(<2,5>)}=max{7+4,3+8}=11
ve(6)=max{ve(3)+dur(<3,6>),ve(4)+dur(<4,6>)}=max{2+7,7+2}=9
ve(7)=max{ve(5)+dur(<5,7>),ve(6)+dur(<6,7>)}=max{11+9,9+6}=20
vl(7)=ve(7)=20
按 (1)式和 (2)式，可计算出图该 AOE网各个事件的最早发生时间和最迟发生时间：
vl(6)=min{vl(7)－ dur(<6,7>)}=min{20－ 6}=14
vl(5)=min{vl(7)－ dur(<5,7>)}=min{20－ 9}=11
vl(4)=min{vl(5)－ dur(<4,5>),vl(6)－ dur(<4,6>)}=min{11－ 4,11－ 2}=7
vl(3)=min{vl(4)－ dur(<3,4>),vl(6)－ dur(<3,6>)}=min{7－ 3,14－ 7}=4
vl(2)=min{vl(4)－ dur(<2,4>),vl(5)－ dur(<2,5>)}=min{7－ 4,11－ 8}=3
vl(1)=min{vl(2)－ dur(<1,2>),vl(3)－ dur(<1,3>)}=min{3－ 3,4－ 2}=0
利用 ve(i)=e(i) 和 l(i)=vl(k)－ dur(<j,k>)
v
2
v
5
v
4
v
7
v
1
a
1
＝ 3
a
4
＝ 4
a
3
＝ 8
a
7
＝ 4
a
9
＝ 9
网络的关键路径关键活动算法主要由以下步骤组成：
(1) 对 AOE网进行拓扑排序，同时按拓扑排序顺序求出各顶点事件的最早发生时间 ve，若网中有回路，则算法终止，否则执行 (2)。
(2) 按拓扑序列的逆序求出各顶点事件的最迟发生时间 vl。
(3) 根据 ve和 vl的值求出 ai的最早开始时间 e(i)和最迟开始时间 l(i)。 若 l(i)=e(i),则 ai为关键活动 。
因为计算各顶点的 ve值是在拓扑排序的过程中进行的，所以可通过对拓扑排序算法进行一些修正来实现求关键路径的算法。
作业
v
2
v
3
v
5
v
6
v
4
v
7
v
1
a
1
＝ 3
a
2
＝ 2
a
4
＝ 4
a
5
＝ 3
a
6
＝ 7
a
3
＝ 8
a
7
＝ 4
a
8
＝ 2
a
9
＝ 9
a
1 0
＝ 6
一个网络及其邻接矩阵
∞ 10 ∞ ∞ 19 21
10 ∞ 5 6 ∞ 11
∞ 5 ∞ 6 ∞ ∞
∞ 6 6 ∞ 18 14
19 ∞ ∞ 18 ∞ 33
21 11 ∞ 14 33 ∞
0
10
1
34
25
18
19
11
21
33
14
6
5
6
Kruskal算法构造最小生成树的过程
0 1
34
25
( a ) 初始状态
0 1
34
25
5
( b ) 找到最短边 ( 1,2 )
0 1
34
2
5
6
( c ) 找到最短边 ( 2,3 )
0
10
1
34
25
18
11
5
6
( f ) 找到最短边 ( 3,4 )
0
10
1
34
25
11
5
6
( e ) 找到最短边 ( 1,5 )
0
10
1
34
25
5
6
( d ) 找到最短边 ( 0,1 )
5
3.6.2 图的存储
3.6.3 图的遍历
3.6.4 图的应用
3.6 图
3.6.1 图的基本概念
BA C
D 6
3
2
1
5数据结构 B=（ D,R）
图,G=（ V,E）
顶 点,图中的数据元素
V：表示 顶 点的非空有限集合。
E,表示两个 顶 点之间关系的集合。
图的定义、术语图有向图无向图在有向图中,<V1,V3>表示从 V1到 V3的一条弧。
V1为弧尾或初始点,V3为弧头或终端点。
在无向图中,(V1,V3)表示 V1和 V3之间的一条边 。
V1 V3
V2 V4
V1 V3
V2 V4
图的定义、术语
V1 V3
V2 V4
V1 V3
V2 V4
顶点集合 V={V1,V2,V3,V4 }
弧的集合 G={<V1,V3>,<V3,V4>,
<V2,V4>,<V4,V1>}
顶点集合 V={V1,V2,V3,V4 }
边的集合 E={(V1,V3),(V1,V2),
(V1,V4),(V2,V4)}
G=( V,E )
顶点 (V1,V3)与 (V3,V1)表示同一条边图的定义、术语
BA C
D 6
3
2
1
5
权,与图的边或弧相关的数。
顶点的度,依附于该顶点的边数或弧数。
出度,（仅对有向图）以该顶点为尾的弧数。
入度,（仅对有向图）以该顶点为头的弧数。
路径,顶点 A与顶点 C之间存在一条路径。路径上边或弧的数目称为该路径的路径长度。
连通图,无向图任意两顶点都有路径（ 没有孤立顶点）
强连通图,有向图 任意两顶点都有路径网,带权的图称为网图的定义、术语图的存储 邻接矩阵
3.6.2 图的存储
1,邻接矩阵法
（ 1）给顶点编号
（ 2）建立邻接（关系）矩阵
2
1 4
3
1 2 3 4
1
2
3
4
0 0 0 0
1 0 1 1
1 0 0 1
0 1 1 0
a i j表示弧 < i,j >
1：表示有弧； 0:表示无弧任意顶点的出度是该行元素之和任意顶点的入度是该列元素之和图的存储 邻接矩阵
邻接矩阵的优点：
增减边的操作简单
邻接矩阵的缺点：
增减顶点的操作需要搬移大量的元素，
浪费存储空间
2
1 4
3
1 2 3 4
1
2
3
4
0 1 1 0
1 0 1 1
1 1 0 1
0 1 1 0 无向图的邻接矩阵是对称的图的存储 邻接矩阵的实现
图的邻接矩阵实现
typedef struct graph_m{
elemtype node[MAXNUM];
int arcs[MAXNUM][MAXNUM];
}graph_m;
顶点集合边的邻接矩阵二维数组图的存储 邻接表
2,邻接表法
一个邻接表由两种结构组成
存放各顶点元素的数组，头结点
各顶点各自的邻接链表，邻接结点
2
1 4
3
2 31 data
2 data
3 data
4 data
1 3 4
1 2 4
2 3
3 data顶点号元素域邻接链表头指针
2
邻接顶点号下一邻接结点图的存储（课堂练习）
请写出下面这副图的邻接表
1）给顶点编号
2）建立顶点数组
3）建立各顶点的邻接链表
注意，此图为有向图
2
1
3
4
51 data
2 data
3 data
4 data
5 data
2 3
1 3
5
1
4
图的存储 邻接表的实现
邻接表的定义
头结点的定义
邻接结点的定义顶点号 元素域 与头结点相邻的顶点
typedef struct headnode{
int node_index;
elemtype data;
struct adj_node * next_adj;
} headnode;
顶点号下一个与头结点相邻的顶点的邻接结点
typedef struct adj_node{
int node_index;
struct adj_node *next_adj;
}adj_node;
图的存储 邻接表
图邻接表的定义
typedef struct graph_l{
headnode node_list[MAXNUM];
int node_num;
}graph_l;
2 31 data
2 data
3 data
4 data
1 3 4
1 2 4
2 3
图的存储 邻接表
2
1 4
3
2 31 data
2 data
3 data
4 data
1 3 4
1 2 4
2 3
2
1 4
3
1 data
2 data
3 data
4 data
1 3 4
1
3
4
注意：有向图与无向图的区别图的存储
图的邻接表存储法的特点
优点
节省存储空间
边的插入和删除操作比较简便
缺点
结构复杂
具有两种不同的基本组成单元图的存储
3,边带权值的图的存储
1）在邻接矩阵中的实现
0 2 3 5
2 0 1 0
3 1 0 1
5 0 1 0
a[4][4] =
a[ i ][ j ]：记录边的权值；为 0表示无边
1
2 4
3
2
3
5
1 1
图的存储
3,边带权值的图的存储
2）在邻接表中的实现
在邻接结点结构中增加一个权值域
1 data
2 data
3 data
4 data
2 3 3 2
1 1 3 5 4 10
2 3
3 1
顶点号 边权值
1
2 4
3
3
2
5 1
1
10 3
图的遍历
3.6.3 图的遍历
问题：
1）对于连通图，从一个顶点出发沿着所有可能的路径，是否可以将所有的顶点遍历到。
2）图中有回路，遍历算法可能产生死循环。
有重复的路径称为 回路 2
1 4
3
图的遍历 深优
1,深度优先遍历
（ 1）从一个未访问过的顶点开始，访问它的一个未访问过的相邻顶点。
（ 2）如果顶点的所有相邻顶点都是已访问过的，
则需要回溯到之前的一个顶点，选取它的另一个未被访问的相邻顶点。
（ 3）对于前两个步骤是递归的图的遍历 深优
1,深度优先遍历
（ 1）从一个未访问过的顶点开始，访问它的一个未访问过的相邻顶点。
（ 2）如果顶点的所有相邻顶点都是已访问过的，
则需要回溯到之前的一个顶点，选取它的另一个未被访问的相邻顶点。
（ 3）对于前两个步骤是递归的
1
2
5
84
6
3
7
1 73 6 5 28 4
回到 8
1 73 6 528 4
1 3 6 8 4 2 5 7
或者按以下顺序遍历：
注意使用栈支持递归：
图的遍历 深优
深度优先遍历的特点
“深度”：总是访问顶点的 一个 相邻顶点，好像是沿着图中的一条路径走到“底”，然后后退一点，再选一条路。如此“进进退退”，直到所有顶点都被访问
对于连通图，如果第一个被访问的顶点的所有相邻顶点都被访问了，意味着图中所有顶点都被访问了。
即栈空时图的遍历 深优
用递归调用实现深度优先遍历算法
void dfs （ g,v） {
}
1访问顶点 v；visit（ v）； visited[ v ] = 1;
p = g[v]->next_adj
while(p != NULL){
w = p->node_index;
if(visited[w] == 0)
p = p->next_adj;
}
2取得顶点的一个未被访问过的顶点 w；
3 dfs（ g,w）；回到 2；
4重复 2,3直到该顶点所有的相邻顶点都被访问过；
dfs(g,w);
1
2
3
4
5
void dfs（ g,v） {
visited[ v ] = 1;
p = g[ v ]->next_adj
while(p != NULL){
w = p->node_index;
if(visited[ w ] == 0)
dfs( g,w );
p = p->next_adj;
}}
void dfs（ g,2） {
visited[ 2 ] = 1;
p = g[ 2 ]->next_adj
while(p != NULL){
w = p->node_index;
if(visited[ 3 ] == 0)
dfs( g,3 );
p = p->next_adj;
}
}
void dfs（ g,3） {
visited[ 3 ] = 1;
p = g[ 3 ]->next_adj
while(p != NULL){
w = p->node_index;
if(visited[ 4 ] == 0)
dfs( g,4 );
p = p->next_adj;
}
}
void dfs（ g,4） {
visited[ 4 ] = 1;
p = g[ 4 ]->next_adj
while(p != NULL){
w = p->node_index;
if(visited[ w ] == 0)
dfs( g,w );
p = p->next_adj;
}
}
void dfs（ g,5） {
visited[ 5 ] = 1;
p = g[ 5 ]->next_adj
while(p != NULL){
w = p->node_index;
if(visited[ w ] == 0)
dfs( g,w );
p = p->next_adj;
}}
（,1）
1
1
2 ] == 0)
2 );
}
}
5
(,5 );
图的遍历 广优
2,广度优先遍历
访问顶点 v后，接着依次访问 v的所有邻接顶点，
再依次访问这些邻接顶点的邻接顶点。直到所有的顶点都被访问过。
1
2
5
84
6
3
7
1 2 3 4 5 6 7 8
注意,8是作为哪个顶点的邻接顶点被访问的？
1 2 3 4 5 6 7 8
体会队列操作方式：
图的遍历 广优
广度优先遍历的特点
“广度”：总是在访问了一个顶点后，依次访问它的所有相邻顶点。然后再从它的第一个相邻顶点开始，访问其所有的相邻顶点。如此逐个顶点地逐步扩散，直到所有的顶点都被访问。
广度优先遍历操作具有队列操作的特点，当从队列中取出最后一个顶点，发现该顶点的所有相邻顶点都被访问过时，意味着图中所有的顶点都已被访问过生成树与图
3.6.4 图的应用
1,生成树定义
假设存在这样一颗树：
树结点的集合与图的顶点集合相等
树的分支全部由图的边组成。
称这颗树是这幅 图的生成树
生成树是图的,
子集 /子图
是一个不包含回路的子图
图的生成树是
2
1 4
3
2
1 4
3
2
1
4
3
不唯一的！
唯一的！取决于遍历方法和遍历的起始点生成树的示例
A D
B E
C
( a ) D F S 生成树
A D
B E
C
( b ) B F S 生成树生成树与图对于一个有 n个顶点 的连通图 G，
其生成树包含了 条边。
深度优先搜索得到的生成树 广度优先搜索得到的生成树
n－ 1
权值生成树与图
2,最小费用生成树（ 通信网络、交通网络）
在图所有生成树中，边的权值总和最小的生成树
1
2 4
5 6
3
6
5
3 6
6
4 2
4
1
6
1
2 4
5 6
3
边
1－ 3 1
4－ 6 2
2－ 5 3
1－ 4 4
3－ 6 4
2－ 3 5
1－ 2 6
3－ 5 6
5－ 6 6将边按权值大小排列生成树与图
算法分析
关键技术：
为什么在（ 1,4）边选中后不能选（ 3,6）边
在选择（ 3,6）边和（ 2,3）边时有什么不同，怎样设置条件以区别？
当时 3和 6位于同一图中,2,5和 3位于不同的图中
1
2 4
5 6
3
6
5
3 6
6
4 2
4
1
6
1
2 4
5 6
31－ 4 4
3－ 6 4
2－ 3 5
－－ 回路生成树与图
1
2 4
5 6
3
……
1）开始时所有的节点都位于不同的图中
2）选择一条连接两个不同子图的最短边
3）连接以后两个子图的所有顶点都要改为在一个子图中
4）当所有的顶点都位于一个子图中，
算法结束。
权值边
1－ 3 1
4－ 6 2
2－ 5 3
1－ 4 4
3－ 6 4
2－ 3 5
1－ 2 6 思考既然是颗树，如果选择边数为 n－
1个时可不可以结束算法呢？
算法的优化图的最短路径
3,最短路径
图中两个顶点之间有 条路径
最短路径：
是路径中边（弧）的权值总和最小的路径
计算机网络中常使用最短路径算法计算最佳路径
交通网络中使用最短路径算法计算最短旅途多
Dijkstra Algorithm
Floyd Algorithm
A1
A2
A4
A3
A5
2 6
5
1
2
1
5
1）初始化时，设 A1到其它不直连顶点距离为 ∞
寻找 A1到所有节点的最短路径
A2
A3
A4
A5
顶点 距离 路径
2）选择距离最短的路径
3）观察通过新选择的路径是否能更短地到达其它顶点
4）选择出的最短路径将不参加下一轮比较
5）反复 2 - 4步，直到不剩有顶点
2
6
5
∞
A2
A3
A4
A1 A2 A3－－ 3 更新A1 A2 A33
A1 A2 A4－－ ∞
A1 A2 A5－－ 4
3 A4－－ 4 更新A1 A2 A3 A44
3 A5－－ 8A1 A2 A54 4 A5－－ ∞更新
Dijkstra Algorithm
拓 扑 排 序按一定顺序进行的活动,可以使用顶点表示活动,顶点之间的有向边表示活动间的先后关系的有向图来表示,这种有向图称为顶点表示活动网络 (Activity On Vertex network,简称
AOV网 )。
AOV网中的有向边表示了活动之间的制约关系 。
4,拓 扑 排 序将 AOV网中的所有顶点排列成一个线性序列 vi1,vi2,…,vin,并且这个序列同时满足关系：若在 AOV网中从顶点 vi到顶点 vj存在一条路径,则在线性序列中 vi必在 vj之前,我们就称这个线性序列为 拓扑序列 。 把对 AOV网构造拓扑序列的操作称为 拓扑排序 。
在实际的意义上,AOV网中存在的有向环就意味着某些活动是以自己为先决条件,这显然是荒谬的 。 例如对于程序的数据流图而言,AOV网中存在环就意味着程序存在一个死循环 。
任何一个无环的 AOV网中的所有顶点都可排列在一个拓扑序列里,
拓扑排序的基本操作如下：
(1) 从网中选择一个入度为 0的顶点并且输出它 。
(2) 从网中删除此顶点及所有由它发出的边 。
(3) 重复上述两步，直到网中再没有入度为 0的顶点为止。
C
1
C
4
C
2
C
3
C
5
C
7
C
8
C
10
C
12
C
9
C
11
C
6
以上的操作会产生两种结果：
一 种是网中的全部顶点都被输出,整个拓扑排序完成；
另一种是网中顶点未被全部输出,剩余的顶点的入度均不为 0,则说明网中存在有向环 。
用以上操得到了一种拓扑序列：
C1,C2,C3,C4,C5,C7,C9,C10,C12,C11,C6,C8。
拓扑序列可以是 种多
AOV网拓扑排序过程
C
4
C
3
C
5
C
7
C
8
C
10
C
12
C
9
C
11
C
6
( a ) 输出 C
1
后
C
2
C
4
C
3
C
5
C
7
C
8
C
10
C
12
C
9
C
11
C
6
( b ) 输出 C
2
后
C
8
C
10
C
12
C
9
C
11
C
6
( c ) 输出 C
3
,C
4
,C
5
,C
7
后
C
8
C
6
( d ) 输出 C
9
,C
1 0
,C
1 2
,C
1 1
后 ( e ) 输出 C
6
,C
8
后在邻接表存储结构中实现拓扑排序算法的步骤为：
(1) 扫描顶点表,将入度为 0的顶点入栈 。
(2) 当栈非空时执行以下操作：
{ 将栈顶顶点 vi的序号弹出,并输出之；
检查 vi的出边表,将每条出边表邻接点域所对应的顶点的入度域值减 1,若该顶点入度为 0,则将其入栈；
}
(3) 若输出的顶点数小于 n,则输出,有回路,,否则拓扑排序正常结束 。
关 键 路 径
5,关键路径
AOE网络 (Activity On Edge network)：
有向边：表示一个子工程 （ 活动 ）
边上的权值：表示一个活动持续的时间顶点：表示事件,它表示了一种状态,即它的入边所表示的活动均已完成,它的出边所表示的活动可以开始 。
这种带权的有向网络称为 AOE网络 (Activity On Edge network),即边表示活动网络 。
一个 AOE网络的示例
v
2
v
3
v
5
v
6
v
4
v
7
v
1
a
1
＝ 3
a
2
＝ 2
a
4
＝ 4
a
5
＝ 3
a
6
＝ 7
a
3
＝ 8
a
7
＝ 4
a
8
＝ 2
a
9
＝ 9
a
1 0
＝ 6
关键路径：
从源点到汇点的具有最大路径长度的路径 。
关键活动：
关键路径上的各个活动 。
明确了哪些活动是关键活动就可以设法提高关键活动的功效,
以便缩短整个工期 。
nj2,Ev,v )}ji,d u r (( i )m a x { v( j )v
0( 1 ) v
1jiee
e
其中 E1是网络中以 vj为终点的入边集合,dur(<i,j>)是有向边 <vi,vj>上的权值 。
vl(j)的计算可从汇点开始,向源点逆推计算：
(13.2)
其中 E2是网络中以 vj为起点的出边集合 。
1-nj2Ev,v )}k j,d u r (-( k )m i n { v( j )v
n)(vn)(v
2kjll
el
(1)
(2)
ve(j)的计算可 从 源点 开始 利用以下的递推公式求得
ve(1)=0
ve(2)=max{ve(1)+dur(<1,2>)}=max{0+3}=3
ve(3)=max{ve(1)+dur(<1,3>)}=max{0+2}=2
ve(4)=maw{ve(2)+dur(<2,4>),ve(3)+dur(<3,4>)}=max{3+4,2+3}=7
ve(5)=max{ve(4)+dur(<4,5>),ve(2)+dur(<2,5>)}=max{7+4,3+8}=11
ve(6)=max{ve(3)+dur(<3,6>),ve(4)+dur(<4,6>)}=max{2+7,7+2}=9
ve(7)=max{ve(5)+dur(<5,7>),ve(6)+dur(<6,7>)}=max{11+9,9+6}=20
vl(7)=ve(7)=20
按 (1)式和 (2)式，可计算出图该 AOE网各个事件的最早发生时间和最迟发生时间：
vl(6)=min{vl(7)－ dur(<6,7>)}=min{20－ 6}=14
vl(5)=min{vl(7)－ dur(<5,7>)}=min{20－ 9}=11
vl(4)=min{vl(5)－ dur(<4,5>),vl(6)－ dur(<4,6>)}=min{11－ 4,11－ 2}=7
vl(3)=min{vl(4)－ dur(<3,4>),vl(6)－ dur(<3,6>)}=min{7－ 3,14－ 7}=4
vl(2)=min{vl(4)－ dur(<2,4>),vl(5)－ dur(<2,5>)}=min{7－ 4,11－ 8}=3
vl(1)=min{vl(2)－ dur(<1,2>),vl(3)－ dur(<1,3>)}=min{3－ 3,4－ 2}=0
利用 ve(i)=e(i) 和 l(i)=vl(k)－ dur(<j,k>)
v
2
v
5
v
4
v
7
v
1
a
1
＝ 3
a
4
＝ 4
a
3
＝ 8
a
7
＝ 4
a
9
＝ 9
网络的关键路径关键活动算法主要由以下步骤组成：
(1) 对 AOE网进行拓扑排序，同时按拓扑排序顺序求出各顶点事件的最早发生时间 ve，若网中有回路，则算法终止，否则执行 (2)。
(2) 按拓扑序列的逆序求出各顶点事件的最迟发生时间 vl。
(3) 根据 ve和 vl的值求出 ai的最早开始时间 e(i)和最迟开始时间 l(i)。 若 l(i)=e(i),则 ai为关键活动 。
因为计算各顶点的 ve值是在拓扑排序的过程中进行的，所以可通过对拓扑排序算法进行一些修正来实现求关键路径的算法。
作业
v
2
v
3
v
5
v
6
v
4
v
7
v
1
a
1
＝ 3
a
2
＝ 2
a
4
＝ 4
a
5
＝ 3
a
6
＝ 7
a
3
＝ 8
a
7
＝ 4
a
8
＝ 2
a
9
＝ 9
a
1 0
＝ 6
一个网络及其邻接矩阵
∞ 10 ∞ ∞ 19 21
10 ∞ 5 6 ∞ 11
∞ 5 ∞ 6 ∞ ∞
∞ 6 6 ∞ 18 14
19 ∞ ∞ 18 ∞ 33
21 11 ∞ 14 33 ∞
0
10
1
34
25
18
19
11
21
33
14
6
5
6
Kruskal算法构造最小生成树的过程
0 1
34
25
( a ) 初始状态
0 1
34
25
5
( b ) 找到最短边 ( 1,2 )
0 1
34
2
5
6
( c ) 找到最短边 ( 2,3 )
0
10
1
34
25
18
11
5
6
( f ) 找到最短边 ( 3,4 )
0
10
1
34
25
11
5
6
( e ) 找到最短边 ( 1,5 )
0
10
1
34
25
5
6
( d ) 找到最短边 ( 0,1 )
5
