[知识框架]
主要掌握深度优先搜索和广度优先搜索，图的基本概念及基本性质、图的存储结构（邻接矩阵、邻接表、邻接多重表和十字链表）及其特性、存储结构之间的转化、基于存储结构上的遍历操作和各种应用（拓扑排序、最小生成树、最短路径和关键路径）等。通常要求掌握基本思想和实现步骤（手动模拟）。
图 G G G 由顶点集 V V V 和边集 E E E 组成，记为 G = ( V , E ) G=(V, E) G=(V,E) 。
其中 V ( G ) V(G) V(G) 表示图 G G G 中顶点的有限非空集;
E ( G ) E(G) E(G) 表示图 G G G 中顶点之间的关系（边）集合。
若 V = { v 1 , v 2 , ⋯ , v n } V=\left\{v_{1}, v_{2}, \cdots, v_{n}\right\} V={v1,v2,⋯,vn}, 则用 表 ∣ V ∣ |V| ∣V∣ 示图 G G G 中顶点的个 数，也称图 G G G 的阶，
E = { ( u , v ) ∣ u ∈ V , v ∈ V } E=\{(u, v) \mid u \in V, v \in V\} E={(u,v)∣u∈V,v∈V}, 用 ∣ E ∣ |E| ∣E∣ 表示图 G G G 中边的条数。
注意：线性表可以是空表，树可以是空树，但图不能是空图。图中不能一个顶点也没有，图的顶点集V一定非空，但边集E可以为空，此时图中只有顶点没有边。
若 E E E 是有向边（也称弧）的有限集合时，则图 G G G 为有向图。
弧是顶点的有序对，记为
<
v
,
w
>
<v, w>
<v,w>, 其中
v
,
w
v, w
v,w 是顶点,
v
v
v 称为弧尾,
w
w
w 称为弧头,
<
v
,
w
>
<v, w>
<v,w> 称为从顶点
v
v
v 到顶点
w
w
w 的弧，也称
v
v
v 邻接到
w
w
w,或
w
w
w 邻接自
v
v
v。
图
(
a
)
(\mathrm{a})
(a) 所示的有向图
G
1
G_{1}
G1 可表示为
G
1
=
(
V
1
,
E
1
)
V
1
=
{
1
,
2
,
3
}
E
1
=
{
<
1
,
2
>
,
<
2
,
1
>
,
<
2
,
3
>
}
\begin{array}{c} G_{1}=\left(V_{1}, E_{1}\right) \\ V_{1}=\{1,2,3\} \\ E_{1}=\{<1,2>,<2,1>,<2,3>\} \end{array}
G1=(V1,E1)V1={1,2,3}E1={<1,2>,<2,1>,<2,3>}
若 E E E 是无向边（简称边）的有限集合时，则图 G G G 为无向图。
边是顶点的无序对，记为 ( v , w ) (v, w) (v,w) 或 ( w , v ) (w, v) (w,v), 因为 ( v , w ) = ( w , v ) (v, w)=(w, v) (v,w)=(w,v), 其中 v , w v, w v,w 是顶点。
可以说顶点 w w w 和顶点 v v v 互为邻接点。边 ( v , w ) (v, w) (v,w) 依附于顶点 w w w 和 v v v ，或者说边 ( v , w ) (v, w) (v,w) 和顶点 v , w v, w v,w 相关联。
图
(
b
)
(\mathrm{~b})
( b) 所示的无向图
G
2
G_{2}
G2 可表示为
G
2
=
(
V
2
,
E
2
)
V
2
=
{
1
,
2
,
3
,
4
}
E
2
=
{
(
1
,
2
)
,
(
1
,
3
)
,
(
1
,
4
)
,
(
2
,
3
)
,
(
2
,
4
)
,
(
3
,
4
)
}
\begin{array}{c} G_{2}=\left(V_{2}, E_{2}\right) \\ V_{2}=\{1,2,3,4\} \\ E_{2}=\{(1,2),(1,3),(1,4),(2,3),(2,4),(3,4)\} \end{array}
G2=(V2,E2)V2={1,2,3,4}E2={(1,2),(1,3),(1,4),(2,3),(2,4),(3,4)}
有向边用<>表示，无向边用（）表示。
一个图 G G G 若满足:
(1) 不存在重复边;
(2) 不存在顶点到自身的边，则称图 G G G 为简单图。
图中 G 1 G_{1} G1 和 G 2 G_{2} G2 均为简单图。数据结构中仅讨论简单图。
若图 G G G 中某两个结点之间的边数多于一条，又允许顶点通过同一条边和自己关联，则 G G G 为多重图。多重图的定义和简单图是相对的。
对于无向图， ∣ E ∣ |E| ∣E∣ 的取值范围是 0 到 n ( n − 1 ) / 2 n(n-1) / 2 n(n−1)/2, 有 n ( n − 1 ) / 2 n(n-1) / 2 n(n−1)/2 条边的无向图称为完全图，在完全图中任意两个顶点之间都存在边。
对于有向图， ∣ E ∣ |E| ∣E∣ 的取值范围是 0 到 n ( n − 1 ) n(n-1) n(n−1), 有 n ( n − 1 ) n(n-1) n(n−1) 条弧 的有向图称为有向完全图，在有向完全图中任意两个顶点之间都存在方向相反的两条弧。图中 G 2 为无向完全图，而 G 3 G2{\text {为无向完全图，而 }} G{3} G2为无向完全图，而 G3 为有向完全图。
设有两个图 G = ( V , E ) G=(V, E) G=(V,E) 和 G ′ = ( V ′ , E ′ ) G^{\prime}=\left(V^{\prime}, E^{\prime}\right) G′=(V′,E′), 若 V ′ V^{\prime} V′ 是 V V V 的子集，且 E ′ E^{\prime} E′ 是 E E E 的子集，则称 G ′ G^{\prime} G′ 是 G G G 的子图。
若有满足 V ( G ′ ) = V ( G ) V\left(G^{\prime}\right)=V(G) V(G′)=V(G) 的子图 G ′ G^{\prime} G′, 则称其为 G G G 的生成子图。图中 G 3 G_{3} G3 为 G 1 G_{1} G1 的子图。
注意: 并非 V V V 和 E E E 的任何子集都能构成 G G G 的子图， 因为这样的子集可能不是图，即 E E E 的子集中的某些边关联的顶点可能不在这个 V V V 的子集中。
在无向图中，若从顶点 v v v 到顶点 w w w 有路径存在，则称 v v v 和 w w w 是连通的。
若图 G G G 中任意两个顶点都是连通的，则称图 G G G 为连通图，否则称为非连通图。
无向图中的极大连通子图称为连通分量。
若一个图有 n n n 个顶点，并且边数小于 n − 1 n-1 n−1, 则此图必是非连通图。如图 (a)所示，图 G 4 G_{4} G4 有 3 个连通分量，如图 (b)所示。
连通分量强调：
注意: 极大连通子图是无向图的连通分量，极大即要求该连通子图包含其所有的边;
极小连通子图是既要保持图连通又要使得边数最少的子图。
在有向图中，若从顶点 v v v 到顶点 w w w 和从顶点 w w w 到顶点 v v v 之间都有路径，则称这两个顶点是强连通的。
若图中任何一对顶点都是强连通的，则称此图为强连通图。
有向图中的极大强连通子图称为有向图的强连通分量，图 G 1 G_{1} G1 的强连通分量如图所示。
注意：强连通图、强连通分量只是针对有向图而言的。一般在无向图中讨论连通性，在有向图中考虑强连通性。
**连通图的生成树是包含图中全部顶点的一个极小连通子图。**若图中顶点数为 n n n, 则它的生成树含有 n − 1 n-1 n−1 条边。
对生成树而言，若砍去它的一条边，则会变成非连通图，若加上一条边则会形成一个回路。
在非连通图中, 连通分量的生成树构成了非连通图的生成森林。图 G 2 G_{2} G2 的一个生成树：
注意：包含无向图中全部顶点的极小连通子图，只有生成树满足条件，因为砍去生成树的任一条边，图将不再连通。
图中每个顶点的度定义为以该顶点为一个端点的边的数目。
对于无向图，顶点 v v v 的度是指依附于该顶点的边的条数，记为 T D ( v ) \mathrm{TD}(v) TD(v) 。 在
具有 n n n 个顶点、 e e e 条边的无向图中， ∑ i = 1 n T D ( v i ) = 2 e \sum_{i=1}^{n} \mathrm{TD}\left(v_{i}\right)=2 e ∑i=1nTD(vi)=2e,
即无向图的全部顶点的度的和等于边数的 2 倍，因为每条边和两个顶点相关联。
对于有向图, 顶点 v v v 的度分为入度和出度,
入度是以顶点 v v v 为终点的有向边的数目,记为 I D ( v ) ; \mathrm{ID}(v) ; ID(v);
而出度是以顶点 v v v 为起点的有向边的数目，记为 O D ( v ) \mathrm{OD}(v) OD(v) 。
顶点 v v v 的度等于其入度和出度之和，即 T D ( v ) = I D ( v ) + O D ( v ) \mathrm{TD}(v)=\mathrm{ID}(v)+\mathrm{OD}(v) TD(v)=ID(v)+OD(v)
在具有 n n n 个顶点、 e e e 条边的有向图中， ∑ i = 1 n I D ( v i ) = ∑ i = 1 n O D ( v i ) = e \sum_{i=1}^{n} \mathrm{ID}\left(v_{i}\right)=\sum_{i=1}^{n} \mathrm{OD}\left(v_{i}\right)=e ∑i=1nID(vi)=∑i=1nOD(vi)=e,
即有向图的全部顶点的入度之和与出度之和相等，并且等于边数。这是因为每条有向边都有一个起点和终点。
在一个图中，每条边都可以标上具有某种含义的数值，该数值成为该边的权值。这种边上带有权值的图称为带权图，也称网。
**边数很少的图称为稀疏图，反之称为稠密图。**稀疏和稠密本身是模糊的概念，稀疏图和稠密图常常是相对而言的。
一般当图 G G G 满足 ∣ E ∣ < ∣ V ∣ log ∣ |E|<|V| \log \mid ∣E∣<∣V∣log∣ V｜时，可以将 G G G 视为稀疏图。
顶点 v p v_{p} vp 到顶点 v q v_{q} vq 之间的一条路径是指顶点序列 v p , v i 1 , v i 2 , ⋯ , v i m , v q v_{p}, v_{i_{1}}, v_{i_{2}}, \cdots, v_{i_{m}}, v_{q} vp,vi1,vi2,⋯,vim,vq, 关联的边也可以理解为路径的构成要素。
路径上边的数目称为路径长度。
第一个顶点和最后一个顶点相同的路径称为回路或环。若一个图有 n n n 个顶点，并且有大于 n − 1 n-1 n−1 条边，则此图一定有环。
在路径序列中，顶点不重复出现的路径称为简单路径。
除第一个顶点和最后一个顶点外，其余顶点不重复出现的回路称为简单回路。
从顶点 u u u 出发到顶点 v v v 的最短路径若存在，则此路径的长度称为从 u u u 到 v v v 的距离。
若从 u u u 到 v v v 根本不存在路径，则记该距离为无穷 ( ∞ ) (\infty) (∞) 。
一个顶点的入度为 0 、其余顶点的入度均为 1 的有向图，称为有向树。
邻接矩阵存储，是指用一个一维数组存储图中顶点的信息，用一个二维数组存储图中边 的信息（即各顶点之间的邻接关系 )，存储顶点之间邻接关系的二维数组称为邻接矩阵。
结点数为
n
n
n 的图
G
=
(
V
,
E
)
G=(V, E)
G=(V,E) 的邻接矩阵
A
A
A 是
n
×
n
n \times n
n×n 的。将
G
G
G 的顶点编号为
v
1
,
v
2
,
⋯
,
v
n
v_{1}, v_{2}, \cdots, v_{n }
v1,v2,⋯,vn。若
(
v
i
,
v
j
)
∈
E
\left(v_{i}, v_{j}\right) \in E
(vi,vj)∈E, 则
A
[
i
]
[
j
]
=
1
A[i][j]=1
A[i][j]=1, 否则
A
[
i
]
[
j
]
=
0
A[i][j]=0
A[i][j]=0 。
A
[
i
]
[
j
]
=
{
1
,
若
(
v
i
,
v
j
)
或
<
v
i
,
v
j
>
是
E
(
G
)
中
的
边
0
,
若
(
v
i
,
v
j
)
或
<
v
i
,
v
j
>
不是
E
(
G
)
中的边
A[i][j]=\left\{\begin{array}{ll} 1, & \text { 若 }\left(v_{i}, v_{j}\right) \text 或<v_{i }, v_{j}>\text { 是 } E(G) 中 的 边 \\ 0, & \text { 若 }\left(v_{i}, v_{j}\right) \text 或<v_{i },v_{j}>\text { 不是 } E(G) \text { 中的边 } \end{array}\right.
A[i][j]={1,0, 若 (vi,vj)或<vi,vj> 是 E(G)中的边 若 (vi,vj)或<vi,vj> 不是 E(G) 中的边
对于带权图而言, 若顶点
v
i
v_{i}
vi 和
v
j
v_{j}
vj 之间有边相连, 则邻接矩阵中对应项存放着该边对应的权值，
若顶点
V
i
V_{i}
Vi 和
V
j
V_{j}
Vj 不相连，则用0或
(
∞
)
(\infty)
(∞) 来代表这两个顶点之间不存在边:
A
[
i
]
[
j
]
=
{
w
i
j
,
若
(
v
i
,
v
j
)
或
<
v
i
,
v
j
>
是
E
(
G
)
中
的
边
0
或
∞
,
若
(
v
i
,
v
j
)
或
<
v
i
,
v
j
>
不
是
E
(
G
)
中
的
边
A[i][j]=\left\{\begin{array}{ll} w_{i j}, & \text { 若 }\left(v_{i}, v_{j}\right) \text { 或 }< v_{i}, v_{j}>\text { 是 } E(G) 中 的 边 \\ 0 \text 或\infty , & \text { 若 }\left(v_{i}, v_{j}\right) \text 或 <v_{i}, v_{j}> { 不是 } E(G) \text 中的边 \end{array}\right.
A[i][j]={wij,0或∞, 若 (vi,vj) 或 <vi,vj> 是 E(G)中的边 若 (vi,vj)或<vi,vj>不是E(G)中的边
有向图、无向图和网对应的邻接矩阵示例如图所示。
图的邻接矩阵存储结构定义如下：
# define MaxVertexNum 100typedef char VertexType; //顶点数目的最大值typedef int EdgeType; //顶点的数据类型typpedef struct{ //带权图中边上权值的数据类型 VerTexType vex[MaxVertexNum]; //顶点表 EdgeType Edge[MaxVertexNum][MaxVertexNum]; //邻接矩阵，边表 int vexnum,arcnum; //图的当前顶点数和弧数}MGraph;
注意
图的邻接矩阵存储表示法具有以下特点：
所谓邻接表（Adjacency List）, 是指对图 G G G 中的每个顶点 v i v_{i} vi 建立一个单链表, 第 i i i 个单链表中的结点表示依附于顶点 v i v_{i} vi 的边（对于有向图则是以顶点 v i v_{i} vi 为尾的弧)，这个单链表就称为顶点 v i v_{i} vi 的边表（对于有向图则称为出边表)。
边表的头指针和顶点的数据信息采用顺序存储（称为顶点表 )，所以在邻接表中存在两种结点: 顶点表结点和边表结点。
顶点表结点由顶点域（data）和指向第一条邻接边的指针（firstarc）构成；
边表（邻接表）结点由邻接点域（adjvex）和指向下一条邻接边的指针域（nextarc）构成。
邻接表处理办法：
图的邻接表存储结构定义：
#define MaxVertexNum 100 //图中顶点数目的最大值typedef struct ArcNode{ //边表结点 int adjvex; //该弧指向的顶点的位置 struct ArcNode *next; //指向下一条弧的指针 //InfoType info; //网的边权值}ArcNode;typedef struct VNode{ //顶点表结点 VertexType data; //顶点信息 ArcNode *first; //指向第一条依附该顶点的弧的指针}VNode,AdjList[MaxVertexNum];typedef struct{ AdjList vertices; //邻接表 int vexnum,arcnum; //图的顶点数和弧数}ALGraph; //ALGraph是以邻接表存储的图类型
图的邻接表存储方法具有以下特点:
(1) 若 G G G 为无向图, 则所需的存储空间为 O ( ∣ V ∣ + 2 ∣ E ∣ ) O(|V|+2|E|) O(∣V∣+2∣E∣);
若 G G G 为有向图, 则所需的存储空间为 O ( ∣ V ∣ + ∣ E ∣ ) O(|V|+|E|) O(∣V∣+∣E∣) 。前者的倍数 2 是由于无向图中，每条边在邻接表中出现了两次。
(2) 对于稀疏图，采用邻接表表示将极大地节省存储空间。
(3) 在邻接表中，给定一顶点，能很容易地找出它的所有邻边，因为只需要读取它的邻接表。
在邻接矩阵中，相同的操作则需要扫描一行，花费的时间为 O ( n ) O(n) O(n) 。但是，若要确定给定 的两个顶点间是否存在边，则在邻接矩阵中可以立刻查到，而在邻接表中则需要在相应 结点对应的边表中查找另一结点，效率较低。
(4) 在有向图的邻接表表示中，求一个给定顶点的出度只需计算其邻接表中的结点个数; 但求其顶点的入度则需要遍历全部的邻接表。因此，也有人采用逆邻接表的存储方式来加速求解给定顶点的入度。当然，这实际上与邻接表存储方式是类似的。
(5) 图的邻接表表示并不唯一，因为在每个顶点对应的单链表中，各边结点的链接次序可以是任意的，它取决于建立邻接表的算法及边的输入次序。
十字链表是有向图的一种链式存储结构，在十字链表中，对应于有向图中的每条弧有一个节点，对应于每个顶点也有一个节点。
顶点表结点结构如下：
其中 firstin 表示入边表头指针，指向该顶点的入边表中第一个结点, firstout 表示 出边表头指针，指向该顶点的出边表中的第一个结点。
弧结点（边表结点）结构如下：
其中 tailvex 是指弧起点在顶点表的下标，
headvex 是指弧终点在顶点表中的下 标,
headlink 是指入边表指针域, 指向终点相同的下一条边,
taillink 是指边表指针域, 指向起点相同的下一条边。
如果是网，还可以再增加一个 weight 域来存储权值。
比如图中顶点依然是存入一个一维数组 { v 0 , v 1 , v 2 , v 3 } \left\{\mathrm{v}_{0}, \mathrm{v}_{1}, \mathrm{v}_{2}, \mathrm{v}_{3}\right\} {v0,v1,v2,v3}, 就以顶点 v 0 \mathrm{v}_{0} v0 来说, firstout 指向的是出边表中的第一 个结点 v 3 \mathrm{v}_{3} v3 。
所以 v 0 \mathrm{v}_{0} v0 边表结点的 headvex = 3 =3 =3, 而 tailvex 其实就是当前顶点 v 0 \mathrm{v}_{0} v0 的下标0 , 由于 v 0 \mathrm{v}_{0} v0 只有一个出边顶点, 所以 headlink 和 taillink 都是空。
虚线箭头的含义，它其实就是此图的逆邻接表的表示。
对于 v 0 \mathrm{v}_{0} v0 来说，它有两个顶点 v 1 \mathrm{v}_{1} v1 和 v 2 \mathrm{v}_{2} v2 的入边。因此 v 0 \mathrm{v}_{0} v0 的 firstin 指向顶点 v 1 \mathrm{v}_{1} v1 的边表结点中headvex 为 0 的结点, 如图(1)。
接着由入边结点的 headlink 指向下一个入边顶点 v 2 \mathrm{v}_{2} v2 ，如图中的(2)。
对于顶点 v 1 \mathrm{v}_{1} v1, 它有一个入边顶点 v 2 \mathrm{v}_{2} v2, 所以它的 firstin指向顶点 v 2 \mathrm{v}_{2} v2 的边表结点中 headvex 为 1 的结点, 如图中的(3)。
顶点 v 2 \mathrm{v}_{2} v2 和 v 3 \mathrm{v}_{3} v3 也是同样有一个入边顶点, 如图中(4)和(5)。
十字链表的好处就是因为把邻接表和逆邻接表整合在了一起，这样既容易找到以 v i \mathrm{v}_{\mathbf{i}} vi 为尾的弧，也容易找到以 v i \mathrm{v}_{\mathrm{i}} vi 为头的弧, 因而容易求得顶点的出度和入度。
而且它除了结构复杂一点外，其实创建图算法的时间复杂度是和邻接表相同的, 因此, 在有向图的应用中，十字链表是非常好的数据结构模型。
如果边的操作，比如对已访问过的边做标记，删除某一条边等操作, 那就意味着，需要找到这条边的两个边表结点进行操作，这其实还是比较麻烦的。比如下图，若要删除左图的 ( v 0 , v 2 ) \left(\mathrm{v}_{0}, \mathrm{v}_{2}\right) (v0,v2) 这条边，需要对邻接表结构中右边表的阴影两个结点进行删除操作，显然这是比较繁琐的。
重新定义的边表结构
其中 ivex 和 jvex 是与某条边依附的两个顶点在顶点表中下标。
ilink 指向依附顶点 ivex 的下一条边, jlink 指向依附顶点 jvex 的下一条边。这就是邻接多重表结构。
如图所示, 左图有 4 个顶点和 5 条边, 显然，应该先将 4 个顶点和 5 条边的边表结点画出来。由于是无向图, 所以 ivex 是 0、 jvex 是 1 还是反过来都是无所谓的，不过为了绘图方便，都将 ivex 值设置得与一旁的顶点下标相同。
开始连线，如图，首先连线的(1)(2)(3)(4)就是将顶点的 firstedge 指向一 条边, 顶点下标要与 ivex 的值相同，这很好理解。
接着, 由于顶点 v 0 \mathrm{v}_{0} v0 的（ v 0 , v 1 \mathrm{v}_{0}, \mathrm{v}_{1} v0,v1 ）边的邻边有 ( v 0 , v 3 ) \left(\mathrm{v}_{0}, \mathrm{v}_{3}\right) (v0,v3) 和 ( v 0 , v 2 ) \left(\mathrm{v}_{0}, \mathrm{v}_{2}\right) (v0,v2) 。 因此(5)(6)的连线就是满足指向下一条依附于顶点 v 0 \mathrm{v}_{0} v0 的边的目标, 注意 ilink 指向的结点的 jvex 一定要和它本身的 ivex 的值相同。
同样的道理, 连线(7)就是指（ ( v 1 , v 0 ) \left(\mathrm{v}_{1}, \mathrm{v}_{0}\right) (v1,v0) 这条边, 它是相当于顶点 v 1 \mathrm{v}_{1} v1 指向 ( v 1 , v 2 ) \left(\mathrm{v}_{1}, \mathrm{v}_{2}\right) (v1,v2) 边后的下一条。
v 2 \mathrm{v}_{2} v2 有三条边依附, 所以在 ( 3 ) (3) (3) 之后就有了 ( 8 ) ( 9 ) (8)(9) (8)(9) 。连线 (10)的就是顶点 v 3 \mathrm{v}_{3} v3 在连线(4)之后的下一条边。左图一共有 5 条边, 所以右图有 10 条连线，完全符合预期。
邻接多重表与邻接表的差别，仅仅是在于同一条边 在邻接表中用两个结点表示，而在邻接多重表中只有一个结点。这样对边的操作就方便多了, 若要删除左图的 ( v 0 , v 2 ) \left(\mathrm{v}_{0}, \mathrm{v}_{2}\right) (v0,v2) 这条边, 只需要将右图的(6)(9)的链接指向改为 ∧ \wedge ∧ 即可。
| 基本操作 | 注释 |
|---|---|
| Adjacent(G,x,y) | 判断图G是否存在边<x,y>或(x,y) |
| Neighbors(G,x) | 列出图G中与结点x邻接的边 |
| InsertVertex(G,x) | 在图G中插入顶点x |
| DeleteVertex(G,x) | 从图G中删除顶点x |
| AddEdge(G,x,y) | 若无向边(x,y)或有向边<x,y>不存在，则向图G中添加该边 |
| RemoveEdge(G,x,y) | 若无向边(x,y)或有向边<x,y>存在，则向图G中删除该边 |
| FirstNeighbor(G,x) | 求图中顶点x的第一个邻接点，若有则返回顶点号。若x没有邻接点或图中不存在x，则返回-1 |
| NextNeighbor(G,x) | 假设图G中顶点y是顶点x的一个邻接点，返回除y外顶点x的下一个邻接点的顶点号，若y是x的最后一个邻接点，则返回-1 |
| Get_edge_value(G,x,y) | 获取图G中边(x,y)或<x,y>的权值 |
| Set_edge_value(G,x,y,v) | 设置图G中边(x,y)或<x,y>对应权值为v |
**图的遍历（Traversing Graph）**是指从图中的某一顶点出发，按照某种搜索方法沿着图中的边对图中的所有定带你访问一次且仅访问一次。
树也是一种特殊的图，树的遍历实际上也可视为特殊的图的遍历。
为了避免在图的遍历过程中同一顶点被访问多次，在遍历图的过程中，必须记下每个已经访问过的顶点，为此可以设一个辅助数组visited[ ]来标记顶点是否被访问过。
图的遍历算法主要有两种：广度优先搜索和深度优先搜索。
为了防止存在沿着某条路径搜索之后，又回到原顶点，还有些顶点没有遍历到的情况，需要在便利过程中把访问过的顶点打上标记，具体方法是设置一个访问数组visited[n]，n是图中顶点的个数，初值为0，访问过后设置为1。
深度优先遍历（Depth_First_Search,DFS），又称为深度优先搜索。
深度优先遍历其实就是一个递归的过程。
转化为右图之后，就像一棵树的前序遍历，从图中某个顶点v出发，访问此顶点，然后从v的未被访问的邻接点出发深度优先遍历图，直至图中所有和v有路径相通的顶点都被访问到。
对于非连通图，只需要对它的连通分量分别进行深度优先遍历，即在先前一个顶点进行深度优先遍历之后，若图中有顶点尚未被访问，则另选图中一个未曾被访问的顶点作为起始点，重复上述过程，直至图中所有顶点都被访问。
邻接矩阵深度优先递归算法
typedef int Boolean;Bolean visited[MAX];//邻接矩阵深度优先遍历操作void DFSTraverse(Graph G){ int i=0; for(i=0;i<G.numVertexes;i++) visited[v]=FALSE; for(v=0;v<G.numVertexes;i++) if(!visited[i]) DFS(G,i);}//邻接矩阵深度优点递归算法void DFS(Graph G,int v){ int j; visited[v]=True; for(j=0;j<G.numVertexes;j++) if(G.arc[i][j]==1&&!visited[j]){ DFS(G,j); } }
邻接表深度优先递归算法
//邻接表深度遍历操作void DFSTraverse(GraphAdjList GL){ int v; for(v=0;v<GL.numVertexes;v++) visited[v]=FALSE; //初始所有顶点都是未访问过状态 for(v=0;v<GL.numVertexes;v++) if(!visited[v]) //对未访问过的顶点调用DFS，若是连通图，则只会执行一次 DFS(GL,v);}//邻接表深度优点递归算法void DFS(GraphAdjList GL,int v){ EdgeNode *p; visit(v); visited[v]=True; p=Gl->agjList[v].firstedge; while(p){ if(!=visited[p->adjvex]) DFS(GL,p->adjvex); p=p->next; }
图的邻接矩阵是唯一的，对邻接表来说，边的输入次序不同，生成的邻接表也不同。因此，对于同样一个图，基于邻接矩阵遍历的到的DFS序列和BFS序列是唯一的，基于邻接表的遍历所得到的DFS序列和BFS序列是不唯一的。
DFS 算法是一个递归算法, 需要借助一个递归工作栈, 故其空间复杂度为 O ( ∣ V ] ) O(\mid V]) O(∣V]) 。
遍历图的过程实质上是对每个顶点查找其邻接点的过程, 其耗费的时间取决于所用的存储结构 。
以邻接矩阵表示时, 查找每个顶点的邻接点所需的时间为 O ( ∣ V ∣ ) O(|V|) O(∣V∣), 故总的时间复杂度为 O ( ∣ V 2 ) O\left(\mid V^{2}\right) O(∣V2) 。
以邻接表表示时, 查找所有顶点的邻接点所需的时间为 O ( ∣ E ∣ ) O(|E|) O(∣E∣), 访问顶点所需的时间为 O ( ∣ V ∣ ) O(|V|) O(∣V∣), 此 时，总的时间复杂度为 O ( ∣ V ∣ + ∣ E ∣ ) O(|V|+|E|) O(∣V∣+∣E∣) 。
深度优先的生成树和生成森林
与广度优先搜索一样，深度优先搜索也会产生一棵深度优先生成树。当然，是有条件 的, 即对连通图调用 D F S \mathrm{DFS} DFS 才能产生深度优先生成树, 否则产生的将是深度优先生成森林，如图所示。
与 BFS 类似, 基于邻接表存储的深度优先生成树是不唯一的。
广度优先搜索（Bread_First_Search,BFS）类似于二叉树的层序便利算法。
将下图的第一幅图稍微变形，变形原则是顶点 A \mathrm{A} A 放置在最上 第一层, 让与它有边的顶点 B 、 F \mathrm{B} 、 \mathrm{~F} B、 F 为第二层，再让与 B \mathrm{B} B 和 F \mathrm{F} F 有边的顶点 C 、 I 、 G 、 E \mathrm{C} 、 \mathrm{I} 、 \mathrm{G} 、 \mathrm{E} C、I、G、E 为第三层，再将这四个顶点有边的 D、H 放在第四层, 如下图的第二幅图所示。
此时在视觉上感觉图的形状发生了变化，其实顶点和边的关系还是完全相同的。
简而言之，广度优先搜索遍历图的过程是以起始访问顶点v为起点，由近至远一次访问和v有路径相通且路径长度为1，2……的顶点。
邻接矩阵的广度遍历算法
void BFSTraverse(MGraph G){ int i,j; Queue Q; for(i=0;i<G.numVertexes;i++) visited[i]=False; InitQueue(&Q); for(i=0;i<G.numVertexes;i++){ if(!visited[i]){ visited[i]=True; printf("%c",G.vexs[i]); EnQueue(&Q,i); while(!QueueEmpty(Q)){ DeQueue(&Q,&i); for(j=0;j<G.numVertexes;j++){ if(G.arc[i][j]==1&&!visited[j]){ visited[j]=True; printf("&c",G.vexs[j]); EnQueue(&Q,j); } } } } }}
邻接表的广度优先遍历算法
void BFSTraverse(GraphAdjList GL){ int i; EndgeNode *p; Queue Q; for(i=0;i<G.numVertexes;i++) visited[i]=False; InitQueue(&Q); for(i=0;i<G.numVertexes;i++){ if(!visited[i]){ visited[i]=True; printf("%c",GL->adjList[i].data); EnQueue(&Q,i); while(!QueueEmpty(Q)){ DeQueue(&Q,&i); p=GL->adjList[i].firstedge; while(p){ if(!visited[p->adjvex]){ visited[p->adjvex]=True; printf("&c",GL->adjList[p->adjvex].data); EnQueue(&Q,j); } p=p->next; } } } }}
无论是邻接表还是邻接矩阵的存储方式，BFS算法都需要借助一个辅助队列Q，n个顶点均需入队一次，在最坏情况下，空间复杂度为O(|V|)。
采用邻接表存储方式时，每个顶点均需搜索一次（或入队一次），故时间复杂度为O(|V|)，
在搜索任一顶点的邻接点时，每条边至少访问一次，故时间复杂度为O(|E|)，
算法总时间复杂度为O(|V|+｜E｜)。
采用邻接矩阵存储方式时，查找每个顶点的邻接点所需时间为O(|V|)，故算法总时间复杂度为O(|V2|)。
BFS算法求解单源最短路径问题
若图
G
=
(
V
,
E
)
G=(V, E)
G=(V,E) 为非带权图, 定义从顶点
u
u
u 到顶点
v
v
v 的最短路径
d
(
u
,
v
)
d(u, v)
d(u,v) 为从
u
u
u 到
v
v
v 的任何路径中最少的边数; 若从
u
u
u 到
v
v
v 没有通路, 则
d
(
u
,
v
)
=
∞
d(u, v)=\infty
d(u,v)=∞ 。
使用 BFS，可以求解一个满足上述定义的非带权图的单源最短路径问题, 这是由广度优 先搜索总是按照距离由近到远来遍历图中每个顶点的性质决定的。
算法如下：
void BFS_MIN_Distance(Graph G,int u){ for(i=0;i<G.vexnum;++i) d[i]=∞; visited[u]=True; d[u]=0; EnQueue(Q,u); while(!isEmpty(Q)){ DeQueue(Q,u); for(w=FirstNeighbor(G,u);w>=0;w=NextNeighbor(G,u,w)) if(!visited[w]){ //w为u的尚未访问的邻接点 viisited[w]=True; d[w]=d[u]+1; //路径长度+1 EnQueue(Q,w); } }}
广度优先生成树
在广度遍历的过程中, 可以得 到一棵遍历树，称为广度优先生成树, 需要注意的是，一给定图的邻接矩阵存储表示是唯一的, 故其广度优先生成树也是唯一的，但由于邻接表存储表示不唯一，故其广度优先生 成树也是不唯一的。
图的遍历算法可以用来判断图的连通性。
对于无向图来说，若无向图是连通的, 则从任一结点出发, 仅需一次遍历就能够访问图中的所有顶点;
若无向图是非连通的, 则从某一个顶点出发, 一次遍历只能访问到该顶点所在连通分量的 所有顶点, 而对于图中其他连通分量的顶点，则无法通过这次遍历访问。
**对于有向图来说，**若从初始点到图中的每个顶点都有路径, 则能够访问到图中的所有顶点, 否则不能访问到所有顶点。
故在 BFSTraverse () 或 DFSTraverse () 中添加了第二个 for 循环, 再选取初始点, 继续进 行遍历, 以防止一次无法遍历图的所有顶点。
对于无向图, 上述两个函数调用 B F S ( G , i ) \mathrm{BFS}(\mathrm{G}, \mathrm{i}) BFS(G,i) 或 D F S ( G , i ) \mathrm{DFS}(\mathrm{G}, \mathrm{i}) DFS(G,i) 的次数等于该图的连通分量数;
而对于有向图则不是这样，因为一个连通的有向图分为强连通的和非强连通的，它的连通子图也分为强连通分量和非强连通分量, 非强连通分量一次调用 B F S ( G , i ) \mathrm{BFS}(\mathrm{G}, \mathrm{i}) BFS(G,i) 或 DFS (G, i) 无法访 问到该连通分量的所有顶点，如图所示。
对于一个带权连通无向图 G = ( V , E ) G=(V, E) G=(V,E), 生成树不同，每棵树的权（即树中所有边上的权值之和）也可能不同。
设 ℜ \Re ℜ 为 G G G 的所有生成树的集合，若 T T T 为 ℜ \Re ℜ 中边的权值之和最小的那棵生成树,则 T T T 称为 G G G 的最小生成树（Minimum-Spanning-Tree, M S T \mathrm{MST} MST )。
最小生成树具有如下性质:
1）最小生成树不是唯一的，即最小生成树的树形不唯一， ℜ \Re ℜ中可能有多个最小生成树。当图 G G G 中的各边权值互不相等时， G G G 的最小生成树是唯一的; 若无向连通图 G G G 的边数比顶点数少 1 , 即 G G G 本身是一棵树时，则 G G G 的最小生成树就是它本身。
2）最小生成树的边的权值之和总是唯一的，虽然最小生成树不唯一，但其对应的边的权值之和总是唯一的, 而且是最小的。
3）最小生成树的边数为顶点数减 1。
构造最小生成树有多种算法, 但大多数算法都利用了最小生成树的下列性质:
假设 G = ( V , E ) G=(V, E) G=(V,E) 是一个带权连通无向图, U U U 是顶点集 V V V 的一个非空子集。若 ( u , v ) (u, v) (u,v) 是一条具有最小权值的边, 其中 u ∈ U , v ∈ V − U u \in U, v \in V-U u∈U,v∈V−U, 则必存在一棵包含边 ( u , v ) (u, v) (u,v) 的最小生成树。
基于该性质的最小生成树算法主要有 Prim 算法和 Kruskal 算法,它们都基于贪心算法的策略。
构造如下邻接矩阵，又一个存储结构为MGraph的G，G有9个顶带你，arc二维数组如右图所示，数组中用65535代替∞。
Prim算法：
void MiniSpanTree_Prim(MGraph G){ int min,i,j,k; int adjvex[MAXVEX]; //保存相关顶点下标 int lowcost[MAXVEX]; //保存相关顶点边的权值 lowcost[0]=0; //初始化第一个权值为0.即v0加入生成树，lowcost的值为0，在这里就是此下标的顶点已经加入生成树 adjvex[0]=0; //初始化第一个顶点下标为0 for(i=1;i<G.nemVertexes;i++){ //循环除下标为0外的全部顶点 lowcost[i]=G.arc[0][i]; //将v0顶点与之有边的权值存入数组 adjvex[i]=0; //初始化都为v0的下标 } for(i=1;i<G.numVertexes;i++){ min=INFINITY; //初始化最小权值为∞ j=1;k=0; while(j<numVertexes){ //循环全部顶点 if(lowcost[j]!=0&&lowcost[j]<min){ //如果权值不为0或小于min min=lowcost[j]; //让当前权值为最小值 k=j; //让当前最小值的下标存入k } j++; } printf("(%d,%d)",adjvex[k],k); //打印当前顶点边中权值最小边 lowcost[k]=0; //将当前顶点的权值设置为0，表示此顶点已经完成任务 for(j=1;j<G.numVertexes;j++){ //循环所有顶点 if(lowcost[j]!=0 && G.arc[k][j]<lowcost[j]){ //若下标为k顶点各边权值小于此前这些顶点未被加入生成树权值 lowcost[j]=G.arc[k][j]; //将较小权值加入lowcost adjvex[j]=k; //将下标为k的顶点存入adjvex } } }}
假设 N = ( P , { E } ) \mathrm{N}=(\mathrm{P},\{\mathrm{E}\}) N=(P,{E}) 是连通网， T E \mathrm{TE} TE 是 N \mathrm{N} N 上最小生成树中边的集合。
算法从
U
=
{
u
0
}
\mathrm{U}=\left\{\mathrm{u}_{0}\right\}
U={u0}
(
u
0
∈
V
)
,
T
E
=
{
}
\left(\mathrm{u}_{0} \in \mathrm{V}\right), \mathrm{TE}=\{\}
(u0∈V),TE={} 开始。重复执行下述操作：在所有
u
∈
U
,
v
∈
V
−
U
\mathrm{u} \in \mathrm{U}, \mathrm{v} \in \mathrm{V}-\mathrm{U}
u∈U,v∈V−U 的边
(
u
,
v
)
∈
E
(\mathrm{u}, \mathrm{v}) \in \mathrm{E}
(u,v)∈E 中 找一条代价最小的边
(
u
0
,
v
0
)
\left(\mathrm{u}_{0}, \mathrm{v}_{0}\right)
(u0,v0) 并入集合
T
E
\mathrm{TE}
TE ，同时
v
0
\mathrm{v}_{0}
v0 并入
U
\mathrm{U}
U, 直至
U
=
V
\mathrm{U}=\mathrm{V}
U=V 为止。此时
T
E
\mathrm{TE}
TE 中必有
n
−
1
\mathrm{n}-1
n−1 条边, 则
T
=
(
V
,
{
T
E
}
)
\mathrm{T}=(\mathrm{V},\{\mathrm{TE}\})
T=(V,{TE}) 为
N
\mathrm{N}
N 的最小生成树。
由算法代码中的循环嵌套可得知此算法的时间复杂度为
O
(
n
2
)
\mathrm{O}\left(\mathrm{n}^{2}\right)
O(n2) 。
与 Prim 算法从顶点开始扩展最小生成树不同，Kruskal （克鲁斯卡尔）算法是一种按权值的递增次序选择合适的边来构造最小生成树的方法。
简单来说，就是以某顶点为起点，逐步找个顶点上最小权值的边来构建最小生成树的。
可以直接就以边为目标去构建，因为权值是在边上, 直接去找最小权值的边来构建生成树也是很自然的想法，只不过构建时要考虑是否会形成环路而已。
此时就用到了图的存储结构中的边集数组结构。以下是 edge 边集数组结构的定义代码:
typedef struct{ int begin; int end; int weight;}Edge;
转化为边集数组：
调用MiniSpanTree_Kruskal函数，输入下述邻接矩阵，生成最小生成树算法：
void MiniSpantree_Kruskal(MGraph G){ int i,n,m; Edge edge[MAXEDGE]; //定义边集数组 int parent[MAXVEX]; //定义一组数组用来判断边与边之间是否形成回路 /*省略邻接矩阵G转化为边集数组edges并按权值由小到大排序的代码*/ for(i=0;i<G.numVertexes;i++) parent[i]=0; //初始化数组值为0 for(i=0;i<G.numEdges;i++){ //循环每一条边 n=Find(parent,edges[i].begin); m=Find(parent,edges[i],end); if(n!=m){ //假如n与m不等，说明此边没有与现成生成树形成环路 parent[n]=m; //将此边的结尾顶点放入下标为起点的parent中，表示此顶点已经在生成树集合中 printf("(%d,%d) %d",edges[i].begin,edges[i].end,edges[i].weight); } }}int Find(int *parent,int f){ //查找连线顶点的尾部下标 while(parent[f]>0) f=parent[f]; return f;}
假设 N = ( V , { E } ) \mathrm{N}=(\mathrm{V},\{\mathrm{E}\}) N=(V,{E}) 是连通网, 则令最小生成树的初始状态为只有 n \mathrm{n} n 个顶点而无边的 非连通图 T = { V , { } } \mathrm{T}=\{\mathrm{V},\{\}\} T={V,{}}, 图中每个顶点自成一个连通分量。
在 E \mathrm{E} E 中选择代价最小的边，若 该边依附的顶点落在 T \mathrm{T} T 中不同的连通分量上, 则将此边加入到 T \mathrm{T} T 中, 否则舍去此边而 选择下一条代价最小的边。
依次类推, 直至 T \mathrm{T} T 中所有顶点都在同一连通分量上为止。 此算法的 Find 函数由边数 e 决定, 时间复杂度为 O ( l o g e ) \mathrm{O}(\mathrm{log} e) O(loge), 而外面有一个 for 循环 e \mathrm{e} e 次。所以克鲁斯卡尔算法的时间复杂度为 O ( e l o g e ) \mathrm{O}(\mathrm{elog} e) O(eloge) 。
对比两个算法，Kruskal算法主要是针对边来展开，边数少时效率会非常高, 所以对于稀疏图有很大的优势; 而Prim算法对于稠密图, 即边数非常多的情况会更 好一些。
当图是带权图时，把从一个顶点v0到图中任一个顶点vi的一条路径（可能不止一条）所经过边上的权值之和，定义为该路径的带权路径长度，把带权路径长度最短的那条路径称为最短路径。
求解最短路径的算法通常都依赖于一种性质，即两点之间的最短路径也包含了路径上其他顶 点间的最短路径。
带权有向图 G G G 的最短路径问题一般可分为两类: 一是单源最短路径, 即求图中某一顶点到其他各顶点的最短路径，可通过经典的 Dijkstra（迪杰斯特拉）算法求解；二是求每对顶点间的最短路径，可通过Floyd（弗洛伊德）算法来求解。
Dijkstra 算法设置一个集合 S S S 记录已求得的最短路径的顶点，初始时把源点 v 0 v_{0} v0 放入 S S S, 集 合 S S S 每并入一个新顶点 v i v_{i} vi, 都要修改源点 v 0 v_{0} v0 到集合 V − S V-S V−S 中顶点当前的最短路径长度值。
在构造的过程中还设置了两个辅助数组:
dist [ ] : 记录从源点 v 0 v_{0} v0 到其他各顶点当前的最短路径长度, 它的初态为: 若从 v 0 v_{0} v0 到 v i v_{i} vi 有弧, 则 dist [i] 为弧上的权值; 否则置 dist [ i ] [\mathrm{i}] [i] 为∞ 。 _{\text {。 }} 。
path [] : path [i] 表示从源点到顶点
i
i
i 之间的最短路径的前驱结点。在算法结束时, 可根据 其值追溯得到源点
v
0
v_{0}
v0 到顶点
v
i
v_{i}
vi 的最短路径。
假设从顶点 0 出发, 即
v
0
=
0
v_{0}=0
v0=0, 集合
S
S
S 最初只包含顶点 0 , 邻接矩阵
arcs
\operatorname{arcs}
arcs 表示带权有向图,
arcs
[
i
]
[
j
]
\operatorname{arcs}[i][j]
arcs[i][j] 表示有向边<i,
j
>
j>
j> 的权值, 若不存在有向边<i, j>, 则
arcs
[
\operatorname{arcs}[
arcs[ i]
[
j
]
[j]
[j] 为∞。
Dijkstra 算法的步骤如下（不考虑对 path []的操作):
1）初始化: 集合 S S S 初始为 { 0 } \{0\} {0}, dist [ ] 的初始值 dist [i] =arcs [0] [i], i = 1 , 2 , ⋯ , n − 1 i=1,2, \cdots, n-1 i=1,2,⋯,n−1 。
2） 从顶点集合 V − S V-S V−S 中选出 v j v_{j} vj, 满足 dist [ j ] = min { [j]=\min \left\{\right. [j]=min{ dist [ [ [ i ] ∣ v i ∈ V − S } , v j \left.] \mid v_{i} \in \mathrm{V}-S\right\}, v_{j} ]∣vi∈V−S},vj 就是当前求得的 一条从 v 0 v_{0} v0 出发的最短路径的终点, 令 S = S ∪ { j } S=S \cup\{j\} S=S∪{j} 。
3）修改从 v 0 v_{0} v0 出发到集合 V − S V-S V−S 上任一顶点 v k v_{k} vk 可达的最短路径长度: 若 dist [ j ] + arcs [ j ] [ k ] < \operatorname{dist}[j]+\operatorname{arcs}[j][k]< dist[j]+arcs[j][k]< dist [ k ] \operatorname{dist}[k] dist[k], 则更新 dist [ k ] = dist [ j ] + arcs [ j ] [ k ] \operatorname{dist}[k]=\operatorname{dist}[j]+\operatorname{arcs}[j][k] dist[k]=dist[j]+arcs[j][k]
4）重复 2 ） 3 ）操作共 n − 1 n-1 n−1 次，直到所有的顶点都包含在 S S S 中。
步骤 3 ) 每当一个顶点加入 S S S 后, 可能需要修改源点 v 0 v_{0} v0 到集合 V − S V-S V−S 中可达顶点当前的最短路径长度,下面举一简单例子证明。如下图所示, 源点为 v 0 v_{0} v0, 初始时 S = { v 0 } S=\left\{v_{0}\right\} S={v0}, dist [ 1 ] = 3 , dist [ 2 ] = 7 \operatorname{dist}[1]=3, \operatorname{dist}[2]=7 dist[1]=3,dist[2]=7, 当将 v 1 v_{1} v1 并入集合 S S S 后, dist [ 2 ] \operatorname{dist}[2] dist[2] 需要更新为 4 。
算法过程如下：
初始化: 集合 S S S 初始为 { v 1 } , v 1 \left\{v_{1}\right\}, v_{1} {v1},v1 可达 v 2 v_{2} v2 和 v 5 , v 1 v_{5}, v_{1} v5,v1 不可达 v 3 v_{3} v3 和 v 4 v_{4} v4, 因此 dist [ ] \operatorname{dist}[] dist[] 数组各元素的初 值依次设置为 dist [ 2 ] = 10 , dist [ 3 ] = ∞ , dist [ 4 ] = ∞ , dist [ 5 ] = 5 \operatorname{dist}[2]=10, \operatorname{dist}[3]=\infty, \operatorname{dist}[4]=\infty, \operatorname{dist}[5]=5 dist[2]=10,dist[3]=∞,dist[4]=∞,dist[5]=5 。
第一轮: 选出最小值 dist [ 5 ] \operatorname{dist}[5] dist[5], 将顶点 v 5 v_{5} v5 并入集合 S S S, 即此时已找到 v 1 v_{1} v1 到 v 5 v_{5} v5 的最短路径。 当 v 5 v_{5} v5 加入 S S S 后, 从 v 1 v_{1} v1 到集合 V − S V-S V−S 中可达顶点的最短路径长度可能会产生变化. 因此需要更新 dist [ ] 数组. v 5 v_{5} v5 可达 v 2 v_{2} v2, 因 v 1 → v 5 → v 2 v_{1} \rightarrow v_{5} \rightarrow v_{2} v1→v5→v2 的距离 8 比 dist [ 2 ] = 10 \operatorname{dist}[2]=10 dist[2]=10 小, 更新 dist [ 2 ] = 8 ; v 5 ]=8 ; v_{5} ]=8;v5 可达 v 3 , v 1 → v 5 → v 3 v_{3}, v_{1} \rightarrow v_{5} \rightarrow v_{3} v3,v1→v5→v3 的距离 14, 更新 dist [ 3 ] = 14 ; v 5 \operatorname{dist}[3]=14 ; v_{5} dist[3]=14;v5 可达 v 4 , v 1 → v 5 → v 4 v_{4}, v_{1} \rightarrow v_{5} \rightarrow v_{4} v4,v1→v5→v4 的距离 7 , 更新 dist [ 4 ] = 7 \operatorname{dist}[4]=7 dist[4]=7 。
第二轮: 选出最小值 dist [ 4 ] \operatorname{dist}[4] dist[4], 将顶点 v 4 v_{4} v4 并入集合 S ∘ S_{\circ} S∘ 继续更新 dist []数组。 v 4 v_{4} v4 不可达 v 2 v_{2} v2, dist [2] 不变; v 4 v_{4} v4 可达 v 3 , v 1 → v 5 → v 4 → v 3 v_{3}, v_{1} \rightarrow v_{5} \rightarrow v_{4} \rightarrow v_{3} v3,v1→v5→v4→v3 的距离 13 比 dist [3] 小, 故更新 dist [3] = 13 =13 =13 。 第三轮：选出最小值 dist [ 2 ] \operatorname{dist}[2] dist[2], 将顶点 v 2 v_{2} v2 并入集合 S ∘ S_{\circ} S∘ 继续更新 dist [] 数组。 v 2 v_{2} v2 可达 v 3 v_{3} v3, v 1 → v 5 → v 2 → v 3 v_{1} \rightarrow v_{5} \rightarrow v_{2} \rightarrow v_{3} v1→v5→v2→v3 的距离 9 比 dist [3] 小, 更新 dist [ 3 ] = 9 \operatorname{dist}[3]=9 dist[3]=9 。
第四轮：选出唯一最小值 dist [ 3 ] \operatorname{dist}[3] dist[3], 将顶点 v 3 v_{3} v3 并入集合 S S S, 此时全部顶点都已包含在 S S S 中。 显然，Dijkstra 算法也是基于贪心策略的。
使用邻接矩阵表示时, 时间复杂度为
O
(
∣
V
∣
2
)
O\left(|V|^{2}\right)
O(∣V∣2) 。使用带权的邻接表表示时，虽然修改
dist
[
]
\operatorname{dist}[]
dist[] 的 时间可以减少, 但由于在
dist
[
]
\operatorname{dist}[]
dist[] 中选择最小分量的时间不变, 时间复杂度仍为
O
(
∣
V
∣
2
)
O\left(|V|^{2}\right)
O(∣V∣2) 。
也有可能只希望找到从源点到某个特定顶点的最短路径, 但这个问题和求解源点到其他所有 顶点的最短路径一样复杂，时间复杂度也为
O
(
∣
V
∣
2
)
O\left(|V|^{2}\right)
O(∣V∣2) 。
边上带有负权值时, Dijkstra 算法并不适用。若允许边上带有负权值, 则在与 S S S （已求得最短路径的顶点集，归入 S S S 内的结点的最短路径不再变更）内某点 （记为 a a a ）以负边相连的点（记为 b b b ) 确定其最短路径时, 其最短路径长度加上这条负边的权值结果可能小于a原先确定的最短路径长度，而此时a在Dijkstra算法下时无法更新的。如下图例子：
Dijkstra算法代码实现
（求有向网G到v0顶点到其余顶点v最短路径p【v】及带权长度D【v】，p[v]为前驱顶点下标，D[v]表示 v 0 v_{0} v0到v的最短路径长度）：
#define MAXVEX 9#define INFINITY 65535typedef int Pathmatirx[MAXVEX];typedef int ShortPathTable[MAXVEX];void ShortestPath_Dijkstra(MGraph G,int v0,Pathmatirx *P,ShortPathTable *D){ int v,w,k,min; int final[MAXVEX]; /*final[w]=1表示求得顶点V0至Vw的最短路径*/ for(v=0;v<G.num Vertexes；v++){ //初始化数据 final[v]=0; //全部顶点初始化为未知最短路径状态 (*D)[v]=G,matirx[v0][v]; //将与V0点有连线的顶点加上权值 (*P)[v]=0; //初始化路径数组P为0 } (*D)[v0]=0; //V0至V0路径为0 final[v0]=1; //V0至V0不需要求路径 //开始主循环，每次求得V0到某个V顶点的最短路径 for(v=1;v<numVertexes;v++){ min=INFINITY; //当前所知离V0顶点的最近顶点 for(w=0;w<G.numVertexes;w++){ //寻找离V0最近的顶点 if(!final[w] && (*D)[w]<min){ k=w; min=(*D)[w]; //w顶点离V0顶点最近 } } final[k]=1; //将目前找到的最近的顶点置为1 for(w=0;w<numVertexes;w++){ //修正当前最短路径及距离 //如果经过V顶点的路径比现在这条路径长度短的话 if(!final[w] && (min+G.matirx[k][w]<(*D)[w])){ //说明找到了更短的路径，修改D[w]和P[w] (*D)[w]=min+G.matirx[k][w]; //修改当前路径长度 (*P)[w]=k; } } }}
如果想知道任一顶点到其余所有顶点的最短路径是多少，就是对每个顶点当作源点运行一次Dijkstra算法，等于在原有算法的基础上，再来一次存还，此时整个算法的时间复杂度为 O ( ∣ V ∣ 3 ) O\left(|V|^{3}\right) O(∣V∣3) 。
求所有顶点之间的最短路径问题描述如下：已知一个各边权值均大于 0 的带权有向图, 对任 意两个顶点 v i ≠ v j v_{i} \neq v_{j} vi=vj, 要求求出 v i v_{i} vi 与 v j v_{j} vj 之间的最短路径和最短路径长度。
Floyd 算法的基本思想是:
递推产生一个 n n n 阶方阵序列 A ( − 1 ) , A ( 0 ) , ⋯ , A ( k ) , ⋯ , A ( n − 1 ) A^{(-1)}, A^{(0)}, \cdots, A^{(k)}, \cdots, A^{(n-1)} A(−1),A(0),⋯,A(k),⋯,A(n−1), 其中 A ( k ) [ i ] [ j ] A^{(k)}[i][j] A(k)[i][j] 表示从顶点 v i v_{i} vi 到顶点 v j v_{j} vj 的路径长度, k k k 表示绕行第 k k k 个顶点的运算步骤。
初始时，对于任意两个顶 点 v i v_{i} vi 和 v j v_{j} vj, 若它们之间存在边, 则以此边上的权值作为它们之间的最短路径长度; 若它们之间不存在有向边, 则以∞作为它们之间的最短路径长度。以后逐步尝试在原路径中加入顶点 k ( k = 0 , 1 , ⋯ , k(k=0,1, \cdots, k(k=0,1,⋯,, n − 1 n-1 n−1 ) 作为中间顶点。若增加中间顶点后, 得到的路径比原来的路径长度减少了, 则以此新路径代替原路径。
算法描述如下:
定义一个
n
n
n 阶方阵序列
A
(
−
1
)
,
A
(
0
)
,
⋯
,
A
(
n
−
1
)
A^{(-1)}, A^{(0)}, \cdots, A^{(n-1)}
A(−1),A(0),⋯,A(n−1), 其中,
A
(
−
1
)
[
i
]
[
j
]
=
arcs
[
i
]
[
j
]
A
(
k
)
[
i
]
[
j
]
=
Min
{
A
(
k
−
1
)
[
i
]
[
j
]
,
A
(
k
−
1
)
[
i
]
[
k
]
+
A
(
k
−
1
)
[
k
]
[
j
]
}
,
k
=
0
,
1
,
⋯
,
n
−
1
\begin{gathered} A^{(-1)}[i][j]=\operatorname{arcs}[i][j] \\ A^{(k)}[i][j]=\operatorname{Min}\left\{A^{(k-1)}[i][j], A^{(k-1)}[i][k]+A^{(k-1)}[k][j]\right\}, \quad k=0,1, \cdots, n-1 \end{gathered}
A(−1)[i][j]=arcs[i][j]A(k)[i][j]=Min{A(k−1)[i][j],A(k−1)[i][k]+A(k−1)[k][j]},k=0,1,⋯,n−1
式中,
A
(
0
)
[
i
]
[
j
]
A^{(0)}[i][j]
A(0)[i][j] 是从顶点
v
i
v_{i}
vi 到
v
j
v_{j}
vj 、中间顶点是
v
0
v_{0}
v0 的最短路径的长度,
A
(
k
)
[
i
]
[
j
]
A^{(k)}[i][j]
A(k)[i][j] 是从顶点
v
i
v_{i}
vi 到
v
j
v_{j}
vj 、中 间顶点的序号不大于
k
k
k 的最短路径的长度。Floyd 算法是一个迭代的过程，每迭代一次，在从
v
i
v_{i}
vi到
v
j
v_{j}
vj 的最短路径上就多考虑了一个顶点;
经过 n n n 次迭代后, 所得到的 A ( n − 1 ) [ i ] [ j ] A^{(n-1)}[i][j] A(n−1)[i][j] 就是 v i v_{i} vi 到 v j v_{j} vj 的最短路径长度, 即方阵 A ( n − 1 ) A^{(n-1)} A(n−1) 中就保存了任意一对顶点之间的最短路径长度。
上图为带权有向图 G G G 及其邻接矩阵。应用 Floyd 算法求所有顶点之间的最短路径长度的过程如下表所示。
算法执行过程的说明如下：
初始化：方阵 A ( − 1 ) [ i ] [ j ] = arcs [ i ] [ j ] A^{(-1)}[i][j]=\operatorname{arcs}[i][j] A(−1)[i][j]=arcs[i][j] 。
第一轮：将 v 0 v_{0} v0 作为中间顶点, 对于所有顶点对 { i , j } \{i, j\} {i,j}, 如果有 A − 1 [ i ] [ j ] > A − 1 [ i ] [ 0 ] + A − 1 [ 0 ] [ j ] A^{-1}[i][j]>A^{-1}[i][0]+A^{-1}[0][j] A−1[i][j]>A−1[i][0]+A−1[0][j], 则 将 A − 1 [ i ] [ j ] A^{-1}[i][j] A−1[i][j] 更新为 A − 1 [ i ] [ 0 ] + A − 1 [ 0 ] [ j ] A^{-1}[i][0]+A^{-1}[0][j] A−1[i][0]+A−1[0][j] 。有 A − 1 [ 2 ] [ 1 ] > A − 1 [ 2 ] [ 0 ] + A − 1 [ 0 ] [ 1 ] = 11 A^{-1}[2][1]>A^{-1}[2][0]+A^{-1}[0][1]=11 A−1[2][1]>A−1[2][0]+A−1[0][1]=11, 更新 A − 1 [ 2 ] [ 1 ] = 11 A^{-1}[2][1]=11 A−1[2][1]=11, 更新后的方阵标记为 A 0 A^{0} A0 。
第二轮: 将 v 1 v_{1} v1 作为中间顶点，继续检测全部顶点对 { i , j } ∘ \{i, j\}_{\circ} {i,j}∘ 有 A 0 [ 0 ] [ 2 ] > A 0 [ 0 ] [ 1 ] + A 0 [ 1 ] [ 2 ] = 10 A^{0}[0][2]>A^{0}[0][1]+A^{0}[1][2]=10 A0[0][2]>A0[0][1]+A0[1][2]=10, 更新 A 0 [ 0 ] [ 2 ] = 10 A^{0}[0][2]=10 A0[0][2]=10, 更新后的方阵标记为 A 1 A^{1} A1 。
第三轮: 将 v 2 v_{2} v2 作为中间顶点，继续检测全部顶点对 { i , j } \{i, j\} {i,j} 。有 A 1 [ 1 ] [ 0 ] > A 1 [ 1 ] [ 2 ] + A 1 [ 2 ] [ 0 ] = 9 A^{1}[1][0]>A^{1}[1][2]+A^{1}[2][0]=9 A1[1][0]>A1[1][2]+A1[2][0]=9, 更新 A 1 [ 1 ] [ 0 ] = 9 A^{1}[1][0]=9 A1[1][0]=9, 更新后的方阵标记为 A 2 A^{2} A2 。此时 A 2 A^{2} A2 中保存的就是任意顶点对的最短路径长度。
Floyd算法执行过程表
Floyd 算法的时间复杂度为 O ( ∣ V ∣ 3 ) O\left(\mid V|^{3} \right) O(∣V∣3) 。不过由于其代码很紧凑，且并不包含其他复杂的数据结构, 因此隐含的常数系数是很小的, 即使对于中等规模的输入来说, 它仍然是相当有效的。
Floyd 算法允许图中有带负权值的边, 但不允许有包含带负权值的边组成的回路。Floyd 算法同样适用于带权无向图，因为带权无向图可视为权值相同往返二重边的有向图。
也可以用单源最短路径算法来解决每对顶点之间的最短路径问题。轮流将每个顶点作为源点, 并且在所有边权值均非负时，运行一次 Dijkstra 算法, 其时间复杂度为 O ( ∣ V 2 ∣ ) ⋅ ∣ V ∣ = O ( ∣ V ∣ 3 ) O\left(\mid V^{2} \mid \right) \cdot |V|=O\left(|V|^{3}\right) O(∣V2∣)⋅∣V∣=O(∣V∣3) 。
首先针对下面网图准备两个矩阵 D − 1 \mathrm{D}^{-1} D−1 和 P − 1 , D − 1 \mathrm{P}^{-1}, \mathrm{D}^{-1} P−1,D−1 就是网图的邻接矩 阵, P − 1 \mathrm{P}^{-1} P−1 初设为 P [ i ] [ j ] = j \mathrm{P}[\mathrm{i}][\mathrm{j}]=\mathrm{j} P[i][j]=j 这样的矩阵，它主要用来存储路径。
代码如下，因为是求所有顶点到所有顶点的最短路径，因此Pathmatirx和ShortPathTable都是二维数组。
求网图G中各顶点到其余顶点w最短路径P[v] [w]以及带权长度D[v] [w]。
typedef int Pathmatirx[MAXVEX][MAXVEX];typedef int ShortPathTable[MAXVEX][MAXVEX];void ShortestPath_Floyd(MGraph G,Pathmatirx *P,ShortPathTable *D){ int v,w,k; for(v=0;v<G.numVertexes;++v){ //初始化D与P for(w=0;w<G.numVertexes;++w){ (*D)[v][w]=G.matirx[v][w]; //D[v][w]对应点间的权值 (*P)[v][w]=w; //初始化P } } for(k=0;k<G.numVertexes;++k){ for(v=0;v<G.numVertexes;++v){ for(w=0;w<G.numVertexes;++w){ if((*D)[v][w]>(*D)[v][k]+(*D)[k][w]){ //如果经过下标为k顶点路径比原两点间路径更短，将两点间权值设置为更小的一个 (*D)[v][w]=(*D)[v][k]+(*D)[k][w]; (*P)[v][w]=(*P)[v][k]; //路径设置经过下标为k的顶点 } } } }}
如何由 P \mathrm{P} P 这个路径数组得出具体的最短路径呢?
以 v 0 \mathrm{v}_{0} v0 到 v 8 \mathrm{v}_{8} v8 为例, 从右图第 v 8 \mathrm{v}_{8} v8 列, P [ 0 ] [ 8 ] = 1 \mathrm{P}[0][8]=1 P[0][8]=1, 得到要经过顶点 v 1 \mathrm{v}_{1} v1, 然后将 1 取代 0 得到 P [ 1 ] [ 8 ] = 2 \mathrm{P}[1][8]=2 P[1][8]=2, 说 明要经过 v 2 \mathrm{v}_{2} v2, 然后将 2 取代 1 得到 P [ 2 ] [ 8 ] = 4 \mathrm{P}[2][8]=4 P[2][8]=4, 说明要经过 v 4 \mathrm{v}_{4} v4, 然后将 4 取代 2 得到 P [ 4 ] [ 8 ] = 3 \mathrm{P}[4][8]=3 P[4][8]=3, 说明要经过 v 3 , ⋯ … \mathrm{v}_{3}, \cdots \ldots v3,⋯…, 这样很容易就推导出最终的最短路径值为
v0->v1->v2->v4->v3->v6->v7->v8
求最短路径的显示代码也可以这样写：
for(v=0;v<G.numVertexes;++v){ for(w=v+1;w<G.numVertexes;w++){ printf("v%d-v%d weight: %d",v,w,D[v][w]); k=P[v][w]; //获得第一个顶点下标 printf("path: %d",v); //打印源点 while(k!=w){ //如果路径顶点下标不是终点 printf("-> %d",k); //打印路径顶点 k=P[k][w]; //获得下一个路径顶点下标 } printf("-> %d\n",w); //打印终点 } printf("\n"); }
Floyd算法的代码简洁到就是一个二重循环初始化加一个三重循环权值修正，就完成了所有顶点到所有顶点的最短路径计算。
如果需要求所有顶点至所有顶点的最短路径问题时，可以选择弗洛伊德（Floyd) 算法。
另外，虽然对求最短路径的两个算法举例都是无向图, 但它们对有向图依然 有效, 因为二者的差异仅仅是邻接矩阵是否对称而已。
在一个表示工程的有向图中，用顶点表示活动，用弧表示活动之间的优先关系, 这样的有向图为顶点表示活动的网, 称为 AOV 网（Activity On Vertex Network ) 。AOV 网中的弧表示活动之间存在的某种制约关系。
设 G = ( V , E ) \mathbf{G}=(\mathbf{V}, \mathbf{E}) G=(V,E) 是一个具有 n \mathbf{n} n 个顶点的有向图, V \mathbf{V} V 中的顶点序列 v 1 , v 2 , ⋯ ⋯ , v n \mathbf{v}_{\mathbf{1}}, \mathbf{v}_{2}, \cdots \cdots, \mathbf{v}_{\mathbf{n}} v1,v2,⋯⋯,vn, 满足若从顶点 v i \mathbf{v}_{\mathbf{i}} vi 到 v j \mathbf{v}_{\mathbf{j}} vj 有一条路径, 则在顶点序列中顶点 v i \mathbf{v}_{\mathbf{i}} vi 必在顶点 v \mathbf{v}_{\mathbf{}} v 之前。称这样的顶点序列为一个拓扑序列。
所谓拓扑排序，其实就是对一个有向图构造拓扑序列的过程。
构造时会有两个结果，如果此网的全部顶点都被输出，则说明它是不存在环 (回路) 的 AOV 网; 如果输 出顶点数少了，哪怕是少了一个, 也说明这个网存在环 (回路)，不是 AOV 网。
拓扑排序算法：
由于拓扑排序的过程中，需要删除顶点，显然用邻接表会更加方便。因此需要为 A O V \mathrm{AOV} AOV 网建立一个邻接表。
考虑到算法过程中始终要查找入度为 0 的顶点，我们在原来顶点表结点结构中, 增加一个人度域 in, 结构如下表所示, 其中 in 就是入度的数字。
对于下图的AOV网
可以得到这样的邻接表数据结构
拓扑排序结构代码：
typedef struct EdgeNode{ int adjvex; int weight; struct EdgeNode *next;}EdgeNode;typedef struct VertexNode{ int in; int data; EdgeNode *firstedge;}VertexNode,AdjList[MAXVEX];typedef struct{ AdjList adjList; int numVertexes,numEdges;}graphAdjList,*GraphAdjList;
算法中还需要辅助的数据结构—栈，用来存储处理过程中入度为0的顶点，目的是为了避免每个查找时都要去遍历定点表找有没有入度为0的顶点。
//拓扑排序，若GL没有回路，则输出拓扑排序序列并返回ok，若有回路返回errorStatus TopologicalSort(GraphAdjList GL){ EdgeNode *e; int i,k,gettop; int top=0; //用于栈指针下标 int count =0; //用于统计输出顶点个数 int *stack; //建栈存储入度为0的顶点 stack=(int *)malloc(GL->numVertexes*sizeof(int)); for(i=0;i<GL->numVertexes;i++) if(GL-adjList[i].in==0) stack[++top]=i; //将入度为0的顶点入栈 while(top!=0){ gettop=stack[top--]; //出栈 printf("%d->",GL->adjList[gettop].data); //打印此顶点 count++; //统计输出顶点数 for(e=GL->adjList[gettop].firstedge;e;e=e->next){ //对此顶点弧表遍历 k=e->adjvex; if(!(--GL-adjList[k].in)) //将k号顶点邻接点入度减1 stack[++top]=;; //若为0则入栈，以便于下次输出 } } if(count<GL->numVertexes) //count小于顶点数，说明存在环 return ERROR; else return OK;}
分析整个算法, 对一个具有 n \mathrm{n} n 个顶点 e \mathrm{e} e 条弧的 AOV 网来说，扫描顶点表，将入度为 0 的顶点入栈的时间复杂为 O ( n ) O(n) O(n), 而之后的 while 循环中, 每个顶点进一次栈，出一次栈，入度减 1 的操作共执行了 e \mathrm{e} e 次, 所以整个算法的时间复杂度为 0 ( n + e ) 0(n+e) 0(n+e)
在带权有向图中，以顶点表示事件，以有向边表示活动，以边上的权值表示完成该活动的开销（如完成活动所需的时间 ) ) ) ，称之为用边表示活动的网络, 简称 A O E \mathrm{AOE} AOE 网。
A O E \mathrm{AOE} AOE 网和 A O V \mathrm{AOV} AOV 网都 是有向无环图, 不同之处在于它们的边和顶点所代表的含义是不同的, A O E \mathrm{AOE} AOE 网中的边有权值; 而 A O V \mathrm{AOV} AOV 网中的边无权值, 仅表示顶点之间的前后关系。
A O E \mathrm{AOE} AOE 网具有以下两个性质：
(1) 只有在某顶点所代表的事件发生后，从该顶点出发的各有向边所代表的活动才能开始;
(2) 只有在进入某顶点的各有向边所代表的活动都已结束时，该顶点所代表的事件才能发生。
在 A O E \mathrm{AOE} AOE 网中仅有一个入度为 0 的顶点, 称为开始顶点（源点), 它表示整个工程的开始; 网中也仅存在一个出度为 0 的顶点，称为结束顶点（汇点), 它表示整个工程的结束。
在 AOE 网中，有些活动是可以并行进行的。从源点到汇点的有向路径可能有多条，并且这些路径长度可能不同。完成不同路径上的活动所需的时间虽然不同，但是只有所有路径上的活动都已完成，整个工程才能算结束。因此，从源点到汇点的所有路径中，具有最大路径长度的路径称为关键路径，而把关键路径上的活动称为关键活动。
完成整个工程的最短时间就是关键路径的长度，即关键路径上各活动花费开销的总和。这是因为关键活动影响了整个工程的时间，即若关键活动不能按时完成, 则整个工程的完成时间就会延长。因此，只要找到了关键活动，就找到了关键路径，也就可以得出最短完成时间。
寻找关键活动时所用到的几个参量的定义：
（1）事件
v
k
v_{k}
vk 的最早发生时间
v
e
(
k
)
v e(k)
ve(k)
它是指从源点
v
1
v_{1}
v1 到顶点
v
k
v_{k}
vk 的最长路径长度。事件
v
k
v_{k}
vk 的最早发生时间决定了所有从
v
k
v_{k}
vk 开始的活动能够开工的最早时间。可用下面的递推公式来计算:
ve(源点) =
0
\text { ve(源点) = } 0
ve(源点) = 0
v
e
(
k
)
=
Max
{
v
e
(
j
)
+
Weight
(
v
j
,
v
k
)
}
,
v
k
v e(k)=\operatorname{Max}\left\{v \mathrm{e}(j)+\operatorname{Weight}\left(v_{j}, v_{k}\right)\right\}, v_{k}
ve(k)=Max{ve(j)+Weight(vj,vk)},vk 为
v
j
v_{j}
vj 的任意后继, Weight
(
v
j
,
v
k
)
\left(v_{j}, v_{k}\right)
(vj,vk) 表示
<
v
j
,
v
k
>
<v_{j}, v_{k}>
<vj,vk> 上的权值
计算 $v e $（）值时，按从前往后的顺序进行，可以在拓扑排序的基础上计算:
1）初始时, 今 v e [ 1 … n ] = 0 v e[1 \ldots n]=0 ve[1…n]=0 。
2） 输出一个入度为 0 的顶点 v j v_{j} vj 时, 计算它所有直接后继顶点 v k v_{k} vk 的最早发生时间, 若 v e [ j ] + v e[j]+ ve[j]+ Weight ( v j , v k ) > v e [ k ] \operatorname{Weight}\left(v_{j}, v_{k}\right)>v e[k] Weight(vj,vk)>ve[k], 则 v e [ k ] = v e [ j ] + Weight ( v j , v k ) v e[k]=v e[j]+\operatorname{Weight}\left(v_{j}, v_{k}\right) ve[k]=ve[j]+Weight(vj,vk) 。 以此类推, 直至输出全部顶点。
（2）事件
v
k
v_{k}
vk 的最迟发生时间
v
l
(
k
)
v l(k)
vl(k)
它是指在不推迟整个工程完成的前提下, 即保证它的后继事件
v
j
v_{j}
vj 在其最迟发生时间
v
1
(
j
)
v 1(j)
v1(j) 能够 发生时, 该事件最迟必须发生的时间。
可用下面的递推公式来计算:
v
l
(
k
)
=
Min
{
v
l
(
j
)
−
Weight
(
v
k
,
v
j
)
}
,
v
k
v l(k)=\operatorname{Min}\left\{v l(j)-\operatorname{Weight}\left(v_{k}, v_{j}\right)\right\}, v_{k}
vl(k)=Min{vl(j)−Weight(vk,vj)},vk 为
v
j
v_{j}
vj 的任意前驱
注意：在计算 v l ( k ) v l(k) vl(k) 时，按从后往前的顺序进行，可以在逆拓扑排序的基础上计算。 计算 v l v l vl （）值时，按从后往前的顺序进行，在上述拓扑排序中，增设一个栈以记录拓扑序列, 拓扑排序结束后从栈顶至栈底便为逆拓扑有序序列。过程如下:
(1) 初始时, 今 v l [ 1 … n ] = v e [ n ] v l[1 \ldots n]=v e[n] vl[1…n]=ve[n] 。
(2) 栈顶顶点 v j v_{j} vj 出栈, 计算其所有直接前驱顶点 v k v_{k} vk 的最迟发生时间, 若 v l [ j ] − Weight ( v k , v j ) < v l [ k ] v l[j]-\operatorname{Weight}\left(v_{k}, v_{j}\right)<v l[k] vl[j]−Weight(vk,vj)<vl[k], 则 v [ [ k ] = v [ j ] − v\left[[k]=v[j]-\right. v[[k]=v[j]− Weight ( v k , y j ) ∘ \left(v_{k}, y_{j}\right)_{\circ} (vk,yj)∘ 以此类推, 直至输出全部栈中顶点。
（3）活动 a i a_{i} ai 的最早开始时间 e ( i ) e(i) e(i)
它是指该活动弧的起点所表示的事件的最早发生时间。若边 < v k , v j <v_{k}, v_{j} <vk,vj 表示活动 a i a_{i} ai, 则有 e ( i ) = v e ( k ) e(i)=v e(k) e(i)=ve(k) 。
（4）活动
a
i
a_{i}
ai 的最迟开始时间
l
(
i
)
l(i)
l(i)
它是指该活动弧的终点所表示事件的最迟发生时间与该活动所需时间之差。若边
<
v
k
,
v
j
>
<v_{k}, v_{j}>
<vk,vj> 表示 活动
a
i
a_{i}
ai, 则有
l
(
i
)
=
v
l
(
j
)
−
Weight
(
v
k
,
v
j
)
l(i)=v l(j)-\operatorname{Weight}\left(v_{k}, v_{j}\right)
l(i)=vl(j)−Weight(vk,vj) 。
（5）一个活动 a i a_{i} ai 的最迟开始时间 l ( i ) l(i) l(i) 和其最早开始时间 e ( i ) e(i) e(i) 的差额 d ( i ) = l ( i ) − e ( i ) d(i)=l(i)-e(i) d(i)=l(i)−e(i)
它是指该活动完成的时间余量, 即在不增加完成整个工程所需总时间的情况下，活动 a i a_{i} ai 可以拖延的时间。若一个活动的时间余量为零, 则说明该活动必须要如期完成, 否则就会拖延整个工 程的进度, 所以称 l ( i ) − e ( i ) = 0 l(i)-e(i)=0 l(i)−e(i)=0 即 l ( i ) = e ( i ) l(i)=e(i) l(i)=e(i) 的活动 a i a_{i} ai 是关键活动。
求关键路径的算法步骤如下:
1 ）从源点出发, 令
v
e
(
v e(
ve( 源点
)
=
0
)=0
)=0, 按拓扑有序求其余顶点的最早发生时间
v
e
v e
ve （）。
2 ）从汇点出发, 令
v
l
(
v l(
vl( 汇点
)
=
v
e
(
)=v e(
)=ve( 汇点
)
)
), 按逆拓扑有序求其余顶点的最迟发生时间
v
l
v l
vl （）。
3 ）根据各顶点的
v
e
0
v e 0
ve0 值求所有弧的最早开始时间
e
(
)
e()
e() 。
4）根据各顶点的
v
l
(
v l(
vl( 值求所有弧的最迟开始时间
l
0
l 0
l0 。
5）求
A
O
E
\mathrm{AOE}
AOE 网中所有活动的差额
d
0
d 0
d0, 找出所有
d
(
)
=
0
d()=0
d()=0 的活动构成关键路径。
如图所示为求解关键路径的过程,
简单说明如下:
1）求
v
e
(
)
v e()
ve() : 初始
v
e
(
1
)
=
0
v e(1)=0
ve(1)=0, 在拓扑排序输出顶点过程中, 求得
v
e
(
2
)
=
3
,
v
e
(
3
)
=
2
,
v
e
(
4
)
=
v e(2)=3, \quad v e(3)=2, v e(4)=
ve(2)=3,ve(3)=2,ve(4)=
max
{
v
e
(
2
)
+
2
,
v
e
(
3
)
+
4
}
=
max
{
5
,
6
}
=
6
,
v
e
(
5
)
=
6
,
v
e
(
6
)
=
max
{
v
e
(
5
)
+
1
,
v
e
(
4
)
+
2
,
v
e
(
3
)
+
3
}
=
\max \{v e(2)+2, v e(3)+4\}=\max \{5,6\}=6, v e(5)=6, \quad v e(6)=\max \{v e(5)+1, v e(4)+2, v e(3)+3\}=
max{ve(2)+2,ve(3)+4}=max{5,6}=6,ve(5)=6,ve(6)=max{ve(5)+1,ve(4)+2,ve(3)+3}=
max
{
7
,
8
,
5
}
=
8
\max \{7,8,5\}=8
max{7,8,5}=8 。
根据上述求
v
e
(
)
v e()
ve() 的过程就已经能知道关键路径。
2）求 v l ( ) v l() vl() : 初始 v l ( 6 ) = 8 v l(6)=8 vl(6)=8, 在逆拓扑排序出栈过程中, 求得 v l ( 5 ) = 7 , v l ( 4 ) = 6 , v l ( 3 ) = min v l(5)=7, v l(4)=6, v l(3)=\min vl(5)=7,vl(4)=6,vl(3)=min { v l ( 4 ) − 4 , v l ( 6 ) − 3 } = min { 2 , 5 } = 2 , v l ( 2 ) = min { v l ( 5 ) − 1 , v l ( 4 ) − 2 } = min { 4 , 4 } = 4 , v l ( 1 ) \{v l(4)-4, v l(6)-3\}=\min \{2,5\}=2, \quad v l(2)=\min \{v l(5)-1, v l(4)-2\}=\min \{4,4\}=4, v l(1) {vl(4)−4,vl(6)−3}=min{2,5}=2,vl(2)=min{vl(5)−1,vl(4)−2}=min{4,4}=4,vl(1) 必然为 0 而无须再求。
3）弧的最早开始时间 e ( e( e( 等于该弧的起点的顶点的 v e ( ) v e() ve(), 求得结果如下表所示。
4） 弧的最迟开始时间 l ( i ) l(i) l(i) 等于该弧的终点的顶点的 v l ( v l( vl( 减去该弧持续的时间, 求得结果如表所示。
5）根据 l ( i ) − e ( i ) = 0 l(i)-e(i)=0 l(i)−e(i)=0 的关键活动, 得到的关键路径为 ( v 1 , v 3 , v 4 , v 6 ) \left(v_{1}, v_{3}, v_{4}, v_{6}\right) (v1,v3,v4,v6) 。
为了代码书写的方便，对上述参数重新做定义：
求事件的最早发生时间 etv 的过程，就是从头至尾找拓扑序列的过程, 因此, 在求关键路径之前, 需要先调用一次拓扑序列算法的代码来计算 e t v \mathrm{etv} etv 和拓扑序列列表。为此，我们首先在程序开始处声明几个全局变量。
int *etv,*ltv; //事件0最早发生实践和最迟发生时间数组int *stack2; //用于存储拓扑序列的栈int top2; //用于Stack2的指针
改进的求拓扑序列算法
//拓扑排序，用于计算关键路径Status TopologicalSort(GraphAdjList GL){ EdgeNode *e; int i,k,gettop; int top=0; //用于栈指针下标 int count =0; //用于统计输出顶点个数 int *stack; //建栈存储入度为0的顶点 stack=(int *)malloc(GL->numVertexes*sizeof(int)); for(i=0;i<GL->numVertexes;i++) if(GL-adjList[i].in==0) stack[++top]=i; //将入度为0的顶点入栈 top2=0; etv=(int*)malloc(GL->numVertexes*sizeof(int)); //事件最早发生时间 for(i=0;i<GL->numVertexes;i++) etv[i]=0; //初始化为0 stacks2=(int*)malloc(GL->numVertexes*sizeof(int)); while(top!=0){ gettop=stack[top--]; //出栈 printf("%d->",GL->adjList[gettop].data); //打印此顶点 count++; //统计输出顶点数 stack2[++top2]=gettop; //将弹出的顶点序号压入拓扑序列的栈 for(e=GL->adjList[gettop].firstedge;e;e=e->next){ //对此顶点弧表遍历 k=e->adjvex; if(!(--GL-adjList[k].in)) //将k号顶点邻接点入度减1 stack[++top]=;; //若为0则入栈，以便于下次输出 if((etv[gettop]+e->weight)>etv[k]) etv[k]=etv[gettop]+e->weight; } } if(count<GL->numVertexes) //count小于顶点数，说明存在环 return ERROR; else return OK;}
由此可以得出计算顶点
v
k
v_{\mathrm{k}}
vk 即求
etv
[
k
]
\operatorname{etv}[\mathrm{k}]
etv[k] 的最早发生时间的公式是：
e
t
v
[
k
]
=
{
0
,
当
k
=
0
时
max
{
e
t
v
[
i
]
+
l
e
n
<
v
i
,
v
k
>
}
,
ヨ
k
≠
0
且
<
v
i
,
v
k
>
∈
P
[
k
]
时
e t v[k]= \begin{cases}0, & \text { 当 } k=0 \text { 时 } \\ \max \left\{e t v[i]+l e n<v_{i}, v_{k}>\right\}, ヨ & k \neq 0 \text { 且 }<v_{i}, v_{k}>\in P[k] \text { 时 }\end{cases}
etv[k]={0,max{etv[i]+len<vi,vk>},ヨ 当 k=0 时 k=0 且 <vi,vk>∈P[k] 时
其中
P
[
K
]
\mathrm{P}[\mathrm{K}]
P[K] 表示所有到达顶点
v
k
\mathrm{v}_{\mathrm{k}}
vk 的弧的集合。比如下图的
P
[
3
]
\mathrm{P[3]}
P[3] 就是
<
v
1
,
v
3
>
<\mathrm{v}_{1}, \mathrm{v}_{3}>
<v1,v3> 和
⟨
v
2
,
v
3
>
\left\langle\mathrm{v}_{2}, \mathrm{v}_{3}>\right.
⟨v2,v3> 两条弧。
l
e
n
<
v
i
v
k
>
\mathrm{len}<\mathrm{v}_{\mathrm{i}} \mathrm{v}_{\mathrm{k}}>
len<vivk> 是弧
<
v
i
,
v
k
>
<\mathrm{v}_{\mathrm{i}}, \mathrm{v}_{\mathrm{k}}>
<vi,vk> 上的权值。
/求关键路径，GL为有向网，输出GL的各项关键活动void CriticalPath(GraphAdjList GL){ EdgeNode *e; int i,gettop,k,j; int ete,lte; //生命活动最早发生时间和最迟发生时间 TopologicalSort(GL); //求拓扑序列，计算数组etv和stack2的值 ltv=(int *)malloc(GL->numVertexes*sizeof(int)); //事件最晚发生时间 for(i=0;i<GL-numVertexes;i++) ltv[i]=etv[GL-numVertexes-1]; //初始化ltv while(top2!=0){ //计算ltv gettop=stack2[top2--]; //将拓扑序列出栈，后进先出 for(e=GL->adjist[gettop].firstedge;e;e=e-next){ //求各项顶点时间的最迟发生时间ltv值 k=e-adjvex; if(ltv[k]-e->weight<ltv[gettop]) //求各顶点事件最迟发生时间ltv ltv[gettop]=ltv[k]=e=>weight; } } for(j=0;j<GL->numVertexes;j++){ //求ete，lte和关键活动 for(e=GL->adjList[j].firstedge;e;e=e->next){ k=e-adjvex; ete=etv[j]; //活动最早发生时间 lte=ltv[k]-e->weight; //活动最迟发生时间 if(ete==lte) //两者相等即在关键路径上 printf("<v%d,v%d>length:%d,",GL->adjList[j].data,GL->adjList[k].data,e->weight); } }}
关键路径算法时间复杂度为O(n+e)。
对于关键路径，需要注意以下几点:
1 ）关键路径上的所有活动都是关键活动, 它是决定整个工程的关键因素, 因此可通过加快 关键活动来缩短整个工程的工期。但也不能任意缩短关键活动, 因为一旦缩短到一定的 程度，该关键活动就可能会变成非关键活动。
2）网中的关键路径并不唯一, 且对于有几条关键路径的网, 只提高一条关键路径上的关键 活动速度并不能缩短整个工程的工期, 只有加快那些包括在所有关键路径上的关键活动 才能达到缩短工期的目的。