路径长度——沿路径边的数目或沿路径各边权值之和
回路——第一个顶点和最后一个顶点相同的路径叫~
简单路径——序列中顶点不重复出现的路径叫~
简单回路——除了第一个顶点和最后一个顶点外，其余顶点不重复出现的回路叫~
连通——从顶点V到顶点W有一条路径，则说V和W是连通的
连通图——图中任意两个顶点都是连通的叫~
连通分量——非连通图的每一个连通部分叫~
强连通图——有向图中，如果对每一对Vi,VjÎV,Vi¹Vj,从Vi到Vj和从Vj到Vi都存在路径，则称G是~
路径：
1，2，3，5，6，3
路径长度：
5
简单路径：
1，2，3，5
回路：
1，2，3，5，6，3，1
简单回路：
3，5，6，3
路径：
1，2，5，7，6，5，2，3
路径长度：
7
简单路径：
1，2，5，7，6
回路：
1，2，5，7，6，5，2，1
简单回路：
1，2，3，1
连通图
强连通图
非连通图
连通分量
6.2图的存储结构
多重链表
邻接矩阵——表示顶点间相联关系的矩阵
定义：
设G=（V,E）是有n³1个顶点的图，G的邻接矩阵A是具有以下性质的n阶方阵
特点：
无向图的邻接矩阵对称，可压缩存储；有n个顶点的无向图需存储空间为n（n+1）/2
有向图邻接矩阵不一定对称；有n个顶点的有向图需存储空间为n²
无向图中顶点Vi的度TD（Vi）是邻接矩阵A中第i行元素之和
有向图中，
顶点Vi的出度是A中第i行元素之和
顶点Vi的入度是A中第i列元素之和
网络的邻接矩阵可定义为：
关联矩阵——表示顶点与边的关联关系的矩阵
定义：
设G=（V,E）是有n³1个顶点，e³0条边的图，G的关联矩阵A是具有以下性质的n´e阶矩阵
特点
关联矩阵每列只有两个非零元素，是稀疏矩阵；n越大，零元素比率越大
无向图中顶点Vi的度TD（Vi）是关联矩阵A中第i行元素之和
有向图中，
顶点Vi的出度是A中第i行中“1”的个数
顶点Vi的入度是A中第i行中“-1”的个数
邻接表
实现：
为图中每个顶点建立一个单链表，第i个单链表中的结点表示依附于顶点Vi的边（有向图中指以Vi为尾的弧）
特点
无向图中顶点Vi的度为第i个单链表中的结点数
有向图中
顶点Vi的出度为第i个单链表中的结点个数
顶点Vi的入度为整个单链表中邻接点域值是i的结点个数
逆邻接表：
有向图中对每个结点建立以Vi为头的弧的单链表
有向图的十字链表表示法
^
^
^
^
^
^
^
^
无向图的邻接多重表表示法
^
^
^
^
^
6.3图的遍历
深度优先遍历（DFS）
方法：
从图的某一顶点V0出发，访问此顶点；然后依次从V0的未被访问的邻接点出发，深度优先遍历图，直至图中所有和V0相通的顶点都被访问到；若此时图中尚有顶点未被访问，则另选图中一个未被访问的顶点作起点，重复上述过程，直至图中所有顶点都被访问为止
深度遍历：
V1ÞV2ÞV4ÞV8ÞV5ÞV3ÞV6ÞV7
深度遍历：
V1ÞV2ÞV4ÞV8ÞV5ÞV6ÞV3ÞV7
深度遍历：
V1ÞV2ÞV4ÞV8ÞV5ÞV6ÞV3ÞV7
深度遍历：
V1ÞV2ÞV4ÞV8ÞV3ÞV6ÞV7ÞV5
深度优先遍历算法
递归算法
Ch6_1.c
深度遍历：
V1Þ
V3Þ
V7Þ
V6Þ
V2Þ
V5Þ
V8Þ
V4
深度遍历：
V1Þ
V3Þ
V7Þ
V6Þ
V2Þ
V4Þ
V8Þ
V5
广度优先遍历（BFS）
方法：
从图的某一顶点V0出发，访问此顶点后，依次访问V0的各个未曾访问过的邻接点；然后分别从这些邻接点出发，广度优先遍历图，直至图中所有已被访问的顶点的邻接点都被访问到；若此时图中尚有顶点未被访问，则另选图中一个未被访问的顶点作起点，重复上述过程，直至图中所有顶点都被访问为止
广度遍历：
V1ÞV2ÞV3ÞV4ÞV5ÞV6ÞV7ÞV8
广度遍历：
V1ÞV2ÞV3ÞV4ÞV5ÞV6ÞV7ÞV8
广度遍历：
V1ÞV2ÞV3ÞV4ÞV5ÞV6ÞV7ÞV8
广度遍历：
V1ÞV2ÞV3ÞV4ÞV6ÞV7ÞV8ÞV5
广度优先遍历算法
Ch6_2.c
6.4生成树
生成树
定义：
所有顶点均由边连接在一起，但不存在回路的图叫~
深度优先生成树与广度优先生成树
生成森林：
非连通图每个连通分量的生成树一起组成非连通图的~
说明
一个图可以有许多棵不同的生成树
所有生成树具有以下共同特点：
生成树的顶点个数与图的顶点个数相同
生成树是图的极小连通子图
一个有n个顶点的连通图的生成树有n-1条边
生成树中任意两个顶点间的路径是唯一的
在生成树中再加一条边必然形成回路
含n个顶点n-1条边的图不一定是生成树
深度遍历：
V1ÞV2ÞV4ÞV8ÞV5ÞV3ÞV6ÞV7
广度遍历：
V1ÞV2ÞV3ÞV4ÞV5ÞV6ÞV7ÞV8
最小生成树
问题提出
要在n个城市间建立通信联络网，
顶点——表示城市
权——城市间建立通信线路所需花费代价
希望找到一棵生成树，它的每条边上的权值之和（即建立
该通信网所需花费的总代价）最小———最小代价生成树
问题分析
n个城市间，最多可设置n（n-1）/2条线路
n个城市间建立通信网，只需n-1条线路
问题转化为：
如何在可能的线路中选择n-1条，能把
所有城市（顶点）均连起来，且总耗费
（各边权值之和）最小
构造最小生成树方法
方法一：
普里姆（Prim）算法
算法思想：
设N=（V,{E}）是连通网，TE是N上最小生成树中边的集合
初始令U={u0},（u0ÎV）,TE=F
在所有uÎU,vÎV-U的边（u,v）ÎE中，找一条代价最小的边（u0,v0）
将（u0,v0）并入集合TE，同时v0并入U
重复上述操作直至U=V为止，则T=（V,{TE}）为N的最小生成树
算法实现：
图用邻接矩阵表示
算法描述
算法评价：
T（n）=O（n²）
Ch6_3.c
对角线元素全为0。
构造最小生成树的过程中，若顶点已包含在生成树里，就把其对应的对角线元素置为“1”；若边（vi,vj）已包含进生成树里，就把A[i,j]或A[j,i]位于下三角的一个置为负值
1
1
1
-2
1
-4
1
-1
1
-5
1
-3
方法二：
克鲁斯卡尔（Kruskal）算法
算法思想：
设连通网N=（V,{E}），令最小生成树
初始状态为只有n个顶点而无边的非连通图T=（V,{F}），每个顶点自成一个连通分量
在E中选取代价最小的边，若该边依附的顶点落在T中不同的连通分量上，则将此边加入到T中；否则，舍去此边，选取下一条代价最小的边
依此类推，直至T中所有顶点都在同一连通分量上为止
（0）用顶点数组和边数组存放顶点和边信息
（1）初始时，令每个顶点的jihe互不相同；每个边的flag为0
（2）选出权值最小且flag为0的边
（3）若该边依附的两个顶点的jihe值不同，即非连通，则令
该边的flag=1,选中该边；再令该边依附的两顶点的jihe
以及两集合中所有顶点的jihe相同
若该边依附的两个顶点的jihe值相同，即连通，则令该
边的flag=2,即舍去该边
（4）重复上述步骤，直到选出n-1条边为止
顶点结点：
typedefstruct
{intdata;//顶点信息
intjihe;
}VEX;
边结点：
typedefstruct
{intvexh,vext;//边依附的两顶点
intweight;//边的权值
intflag;//标志域
}EDGE;
算法实现：
Ch6_30.c
算法描述：
1
1
1
1
1
4
2
1
1
1
2
2
2
2
2
6.5拓扑排序
问题提出：
学生选修课程问题
顶点——表示课程
有向弧——表示先决条件，若课程i是课程j的先决条件，则图中有弧
学生应按怎样的顺序学习这些课程，才能无矛盾、顺利地完成学业——拓扑排序
定义
AOV网——用顶点表示活动，用弧表示活动间优先关系的有向图称为顶点表示活动的网（ActivityOnVertexnetwork），简称AOV网
若是图中有向边，则vi是vj的直接前驱；vj是vi的直接后继
AOV网中不允许有回路，这意味着某项活动以自己为先决条件
拓扑排序——把AOV网络中各顶点按照它们相互之间的优先关系排列成一个线性序列的过程叫~
检测AOV网中是否存在环方法：
对有向图构造其顶点的拓扑有序序列，若网中所有顶点都在它的拓扑有序序列中，则该AOV网必定不存在环
拓扑排序的方法
在有向图中选一个没有前驱的顶点且输出之
从图中删除该顶点和所有以它为尾的弧
重复上述两步，直至全部顶点均已输出；或者当图中不存在无前驱的顶点为止
拓扑序列：
C1--C2--C3--C4--C5--C7--C9--C10--C11--C6--C12--C8
或：
C9--C10--C11--C6--C1--C12--C4--C2--C3--C5--C7--C8
一个AOV网的拓扑序列不是唯一的
算法实现
以邻接表作存储结构
把邻接表中所有入度为0的顶点进栈
栈非空时，输出栈顶元素Vj并退栈；在邻接表中查找Vj的直接后继Vk，把Vk的入度减1；若Vk的入度为0则进栈
重复上述操作直至栈空为止。
若栈空时输出的顶点个数不是n，则有向图有环；否则，拓扑排序完毕
邻接表结点：
typedefstructnode
{intvex;//顶点域
structnode*next;//链域
}JD;
表头结点：
typedefstructtnode
{intin;//入度域
structnode*link;//链域
}TD;
TDg[M];//g[0]不用
算法描述
Ch6_40.c
1
6
输出序列：
6
输出序列：
6
输出序列：
6
输出序列：
6
输出序列：
6
输出序列：
6
输出序列：
61
输出序列：
61
输出序列：
61
4
输出序列：
61
4
输出序列：
61
4
输出序列：
61
4
3
输出序列：
61
4
3
输出序列：
61
4
3
输出序列：
61
4
3
输出序列：
61
4
3
输出序列：
613
4
3
输出序列：
613
4
输出序列：
613
4
输出序列：
613
4
输出序列：
613
4
2
输出序列：
613
4
2
输出序列：
613
4
2
输出序列：
6132
4
2
输出序列：
6132
4
输出序列：
61324
4
输出序列：
61324
输出序列：
61324
5
输出序列：
61324
5
输出序列：
613245
5
输出序列：
613245
算法分析
建邻接表：
T（n）=O（e）
搜索入度为0的顶点的时间：
T（n）=O（n）
拓扑排序：
T（n）=O（n+e）
Ch6_4.c
6.6关键路径
问题提出
把工程计划表示为有向图，用顶点表示事件，弧表示活动；
每个事件表示在它之前的活动已完成，在它之后的活动可以开始
例设一个工程有11项活动，9个事件
事件V1——表示整个工程开始
事件V9——表示整个工程结束
问题：
（1）完成整项工程至少需要多少时间？
（2）哪些活动是影响工程进度的关键？
定义
AOE网（ActivityOnEdge）——也叫边表示活动的网。
AOE网是一个带权的有向无环图，其中顶点表示事件，弧表示活动，权表示活动持续时间
路径长度——路径上各活动持续时间之和
关键路径——路径长度最长的路径叫~
Ve（j）——表示事件Vj的最早发生时间
Vl（j）——表示事件Vj的最迟发生时间
e（i）——表示活动ai的最早开始时间
l（i）——表示活动ai的最迟开始时间
l（i）-e（i）——表示完成活动ai的时间余量
关键活动——关键路径上的活动叫~，即l（i）=e（i）的活动
问题分析
如何找e（i）=l（i）的关键活动？
设活动ai用弧表示，其持续时间记为：
dut（）
则有：
（1）e（i）=Ve（j）
（2）l（i）=Vl（k）-dut（）
如何求Ve（j）和Vl（j）？
求关键路径步骤
求Ve（i）
求Vl（j）
求e（i）
求l（i）
计算l（i）-e（i）
V1
V2
V3
V4
V5
V6
V7
V8
V9
0
6
4
5
7
7
16
14
18
0
6
6
8
7
10
16
14
18
a1
a2
a3
a4
a5
a6
a7
a8
a9
a10
a11
ü
ü
ü
ü
ü
ü
算法实现
以邻接表作存储结构
从源点V1出发，令Ve[1]=0,按拓扑序列求各顶点的Ve[i]
从汇点Vn出发，令Vl[n]=Ve[n],按逆拓扑序列求其余各顶点的Vl[i]
根据各顶点的Ve和Vl值，计算每条弧的e[i]和l[i],找出e[i]=l[i]的关键活动
邻接表结点：
typedefstructnode
{intvex;//顶点域
intlength;
structnode*next;//链域
}JD;
表头结点：
typedefstructtnode
{intvexdata;
intin;//入度域
structnode*link;//链域
}TD;
TDg[M];//g[0]不用
算法描述
输入顶点和弧信息，建立其邻接表
计算每个顶点的入度
对其进行拓扑排序
排序过程中求顶点的Ve[i]
将得到的拓扑序列进栈
按逆拓扑序列求顶点的Vl[i]
计算每条弧的e[i]和l[i],找出e[i]=l[i]的关键活动
Ch6_20.c
6.7最短路径
问题提出
用带权的有向图表示一个交通运输网，图中：
顶点——表示城市
边——表示城市间的交通联系
权——表示此线路的长度或沿此线路运输所花的时间或费用等
问题：
从某顶点出发，沿图的边到达另一顶点所经过的路径中，
各边上权值之和最小的一条路径——最短路径
从某个源点到其余各顶点的最短路径
13
8
13
19
21
20
迪杰斯特拉（Dijkstra）算法思想
按路径长度递增次序产生最短路径算法：
把V分成两组：
（1）S：
已求出最短路径的顶点的集合
（2）V-S=T：
尚未确定最短路径的顶点集合
将T中顶点按最短路径递增的次序加入到S中，
保证：
（1）从源点V0到S中各顶点的最短路径长度都不大于
从V0到T中任何顶点的最短路径长度
（2）每个顶点对应一个距离值
S中顶点：
从V0到此顶点的最短路径长度
T中顶点：
从V0到此顶点的只包括S中顶点作中间
顶点的最短路径长度
依据：
可以证明V0到T中顶点Vk的最短路径，或是从V0到Vk的
直接路径的权值；或是从V0经S中顶点到Vk的路径权值之和
（反证法可证）
求最短路径步骤
初使时令S={V0},T={其余顶点}，T中顶点对应的距离值
若存在，为弧上的权值
若不存在，为µ
从T中选取一个其距离值为最小的顶点W，加入S
对T中顶点的距离值进行修改：
若加进W作中间顶点，从V0到Vi的距离值比不加W的路径要短，则修改此距离值
重复上述步骤，直到S中包含所有顶点，即S=V为止
13
8
µ
30
µ
32
V2:
8
13
-------
13
30
µ
32
V1:
13
-------
-------
13
30
22
20
V3:
13
-------
-------
-------
19
22
20
V4:
19
--------
--------
--------
--------
21
20
V6:
20
算法实现
图用带权邻接矩阵存储ad[][]
数组dist[]存放当前找到的从源点V0到每个终点的最短路径长度，其初态为图中直接路径权值
数组pre[]表示从V0到各终点的最短路径上，此顶点的前一顶点的序号；若从V0到某终点无路径，则用0作为其前一顶点的序号
算法描述
Ch6_5.c
1
13
3
1
22
20
2
2
19
4
1
21
5
1
1
1
13
8
13
19
21
20
算法分析：
T（n）=O（n²）
每一对顶点之间的最短路径
方法一：
每次以一个顶点为源点，重复执行Dijkstra算法n次——T（n）=O（n³）
方法二：
弗洛伊德（Floyd）算法
算法思想：
逐个顶点试探法
求最短路径步骤
初始时设置一个n阶方阵，令其对角线元素为0，若存在弧，则对应元素为权值；否则为µ
逐步试着在原直接路径中增加中间顶点，若加入中间点后路径变短，则修改之；否则，维持原值
所有顶点试探完毕，算法结束
算法实现
图用邻接矩阵存储
length[][]存放最短路径长度
path[i][j]是从Vi到Vj的最短路径上Vj前一顶点序号
算法描述
Ch6_6.c
算法分析：
T（n）=O（n³）
升级会员 