第８章 图
图的基本概念
图的基本运算
生成树与最小生成树
拓扑排序
图的基本存储结构
最短路径
关键路径
图的遍历
8.1 图的基本概念一、图的定义图是由一个非空的顶点集合和一个描述顶点之间多对多关系的边（或弧）集合组成的一种数据结构，
它可以形式化地表示为：
图＝（ V,E）
其中 V={x|x?某个数据对象集 }，它是顶点的有穷非空集合； E={（ x,y） |x,y?V}或 E={<x,y>|x，
y?V且 P（ x,y） }，它是顶点之间关系的有穷集合，
也叫做边集合,P（ x,y）表示从 x到 y的一条单向通路。
图的应用举例例 1 交通图（公路、铁路）
顶点：地点边：连接地点的公路交通图中的有单行道双行道，分别用有向边、无向边表示；
V0
V4V3
V1
V2
V0 V1
V2 V3
例 2 电路图顶点：元件边：连接元件之间的线路例 3 通讯线路图顶点：地点边：地点间的连线例 4 各种流程图如产品的生产流程图顶点：工序边：各道工序之间的顺序关系通常,也将图 G的顶点集和边集分别记为 V（ G）
和 E（ G） 。 E（ G） 可以是空集,若 E（ G） 为空,
则图 G只有顶点而没有边 。
若图 G中的每条边都是有方向的，则称 G为 有向图 。在有向图中，一条有向边是由两个顶点组成的有序对，有序对通常用尖括号表示。例如，有序对 <vi，
vj>表示一条由 vi到 vj的有向边。有向边又称为 弧,弧的始点称为 弧尾,弧的终点称为 弧头 。若图 G中的每条边都是没有方向的，则称 G为 无向图 。无向图中的边均是顶点的无序对，无序对通常用圆括号表示。
图 8-1
v1 v2
v3 v4
v1 v2
v4 v5
v3
（ a）有向图 G1（ b）无向图 G2
图 8.1（ a） 表示的是有向图 G1,该图的顶点集和边集分别为：
V（ G1） ={v1,v2,v3,v4}
E（ G1） ={<v1,v2>,<v1,v3>,<v2,v4>,<v3,v2>}
例有序对 <vi,vj>,
用以为 vi起点、以 vj为终点的有向线段表示，称为有向边或弧；
例：图 8-1
v1 v2
v3 v4
v1 v2
v4 v5
v3
（ a）有向图 G1（ b）无向图 G2
图 8.1（ b） 表示的是无向图 G2,该图的顶点集和边集分别为：
V（ G2） ={v1,v2,v3,v4,v5}
E（ G2） ={（ vl,v2）,（ v1,v3）,（ v1,v4）,
（ v2,v3）,（ v2,v5）,（ v4,v5） }
无序对 (vi,vj)：
用连接顶点 vi,vj的线段表示，称为无向边；
在以后的讨论中,我们约定：
（ 1） 一条边中涉及的两个顶点必须不相同,即：
若 （ vi,vj） 或 <vi,vj>是 E（ G） 中的一条边,则要求 vi≠vj；
（ 2） 一对顶点间不能有相同方向的两条有向边；
（ 3） 一对顶点间不能有两条无向边,即只讨论简单的图 。
若用 n表示图中顶点的数目，用 e表示图中边的数目，按照上述规定，容易得到下述结论：对于一个具有 n个顶点的无向图，其边数 e小于等于 n（ n-1）
/2，边数恰好等于 n（ n-1） /2的无向图称为 无向完全图 ；对于一个具有 n个顶点的有向图，其边数 e小于等于 n（ n-1），边数恰好等于 n（ n-1）的有向图称为 有向完全图 。也就是说完全图具有最多的边数，
任意一对顶点间均有边相连。
二、完全图例：图 8-2
v1
v2 v3
v4
v1
v2 v3
v4
（ a）无向完全图 G3（ b）有向完全图 G4
图 8.2所示的 G3与 G4分别是具有 4个顶点的无向完全图和有向完全图。图 G3共有 4个顶点 6条边；图
G4共有 4个顶点 12条边。
若（ vi,vj）是一条无向边，则称顶点 vi和 vj互为邻接点 。
若 <vi,vj>是一条有向边，则称 vi邻接到 vj,vj邻接于 vi，并称有向边 <vi,vj>关联于 vi与 vj，或称有向边 <vi,vj>与顶点 vi和 vj相关联。
三、度、入度、出度在图中，一个顶点的 度 就是与该顶点相关联的边的数目，顶点 v的度记为 D（ v）。例如在图 8.2
（ a）所示的无向图 G3中，各顶点的度均为 3。
若 G为有向图，则把以顶点 v为终点的边的数目称为顶点 v的 入度,记为 ID（ v）；把以顶点 v为始点的边的数目称为 v的 出度,记为 OD（ v），有向图中顶点的度数等于顶点的入度与出度之和，即 D
（ v） =ID（ v） +OD（ v）。
无论有向图还是无向图,图中的每条边均关联于两个顶点,因此,顶点数 n,边数 e和度数之间有如下关系：
n
i
ivD
1
)(
2
1e= ………,（式 8-1）
四、子图给定两个图 Gi和 Gj，其中 Gi=（ Vi,Ei）,Gj=
（ Vj,Ej），若满足 Vi?Vj,Ei?Ej，则称 Gi是 Gj的子图 。
v1 v2
v4
v2 v3
v4
v1
v2 v3
v4
v1
v4
v2 v3
v4
v1 v1
v3v2
v4
子图示例
（ a）无向图 G3的部分子图
（ b）有向图 G4的部分子图五、路径无向图 G中若存在着一个顶点序列 v,v1’,v2’,…,
vm’,u,且 （ v,v1’）,（ v1’,v2’）,…,（ vm’,u）
均属于 E（ G）,则称该顶点序列为顶点 v到顶点 u的一条 路径,相应地,顶点序列 u,vm’,vm-1’,…,v1’、
v是顶点 u到顶点 v的一条路径 。
如果 G是有向图,路径也是有向的,它由 E（ G）
中的有向边 <v,v1’>,<v1’,v2’>,…,<vm’,u>组成 。 路径长度 是该路径上边或弧的数目 。
如果一条路径上除了起点 v和终点 u相同外，其余顶点均不相同，则称此路径为一条 简单路径 。起点和终点相同（ v=u）的简单路径称为 简单回路 或 简单环 。
六、连通图与强连通图在无向图 G中，若从顶点 vi到顶点 vj有路径，则称 vi与 vj是连通的。若 V（ G）中任意两个不同的顶点 vi和 vj都连通（即有路径），则称 G为 连通图 。例如，图 8.1（ b）所示的无向图 G2、图 8.2（ a）所示的无向图 G3是都是连通图。
无向图 G的极大连通子图称为 G的 连通分量 。
根据连通分量的定义，可知任何连通图的连通分量是其自身，非连通的无向图有多个连通分量。
例：非连通图及其连通分量示例
（ a）非连通图 G5 （ b） G5的两个连通分量 H1和 H2
在有向图 G中，若对于 V（ G）中任意两个不同的顶点 vi和 vj，都存在从 vi到 vj以及从 vj到 vi的路径，则称
G是 强连通图。
V1 V2
V4
V5
V3
V1 V2
V4
V5
V3
有向图的极大强连通子图称为 G的强连通分量。
根据强连通图的定义，可知强连通图的唯一强连通分量是其自身，而非强连通的有向图有多个强连分量。例如，图 8.2（ b）所示的有向图 G4是一个具有
4个顶点的强连通图，图 8.5（ a）所示的有向图 G6
不是强连通图（ v2,v3,v4没有到达 v1的路径），
它的两个强连通分量 H3与 H4如图 8.5（ b）所示。
v1
v2
v3 v4
v1
v2
v3 v4
（ a）非强连通图 G6 （ b） G6的两个强连通分量 H3和 H4
七、网络有时在图的每条边上附上相关的数值，这种与图的边相关的数值叫 权 。
权可以表示两个顶点之间的距离、耗费等具有某种意义的数。若将图的每条边都赋上一个权，则称这种带权图为网络。
V0
V1 V3
V234
56 78 25
V0
V2V1 45
5064
（ a）无向网络 G7 （ b）有向网络 G8
作业：
8.1 对于无向图 8.29,试给出
（ 1） 图中每个顶点的度；
（ 2） 该图的邻接矩阵；
（ 4） 该图的连通分量 。
v0
v3 v4
v2
v1 v5 v6
图 8.29 无向图
8.2 给定有向图 8.30,试给出
（ 1） 顶点 D的入度与出度；
（ 2） 该图的出边表与入边表；
（ 3） 该图的强连通分量 。
A
B
C
D
E
图 8.30 有向图
8.2 图的基本运算图是一种复杂数据结构,由图的定义及图的一组基本操作构成了图的抽象数据类型 。
ADT Graph{
数据对象 V,V是具有相同特性的数据元素的集合,称为顶点集 。
数据关系 R：
R={<v,w>|v,w?V且 P（ v,w）,P（ v,w） 定义了边 （ 或弧 ） （ v,w） 的信息 }
图的基本操作如下：
（ 1） creatgraph（ &g） 创建一个图的存储结构 。
（ 2） insertvertex（ &g,v） 在图 g中增加一个顶点 v。
（ 3） deletevertex（ &g,v） 在图 g中删除顶点 v及所有和顶点 v相关联的边或弧 。
（ 4） insertedge（ &g,v,u） 在图 g中增加一条从顶点 v到顶点 u的边或弧 。
（ 5） deleteedge（ &g,v,u） 在图 g中删除一条从顶点 v到顶点 u的边或弧 。
（ 6） trave（ g） 遍历图 g。
（ 7） locatevertex（ g,v） 求顶点 v在图 g中的位序 。
（ 8） fiirstvertex（ g,v） 求图 g中顶点 v的第一个邻接点 。
（ 9） degree（ g,v） 求图 g中顶点 v的度数 。
（ 10） nextvertex（ g,v,w） 求图 g中与顶点 v相邻接的顶点 w的下一个邻接点 。 即求图 g中顶点 v的某个邻接点,它的存储顺序排在邻接点 w的存储位置之后 。
} ADT Graph
8.3图的基本存储结构图的存储结构至少要保存两类信息：
1)顶点的数据
2)顶点间的关系约定,
G=<V,E>是图,V={v0,v1,v2,… v n-1 },设顶点的角标为它的编号如何表示顶点间的关系？
V0
V4V3
V1
V2
V0 V1
V2 V3
8.3.1邻接矩阵及其实现给定图 G=（ V,E），其中 V（ G） ={v0,…,
vi,…,vn-1},G的邻接矩阵（ Adacency Matrix）是具有如下性质的 n阶方阵：
,
),(,,][A
否则或者如果
0
><1 EjiEjiji,
无向图的邻接矩阵是对称的，有向图的邻接矩阵可能是不对称的。
一、非网络的邻接矩阵
v0
v1 v3
v2
v3
v1
v0 v2
图的邻接矩阵示例
0 1 1 1
1 0 1 0
1 1 0 1
1 0 1 0
0 1 0 0
1 0 1 0
1 1 0 0
0 1 0 0
A1= A2=
图 8.7 无向图 G9及有向图 G10的邻接矩阵表示用邻接矩阵表示图，很容易判定任意两个顶点之间是否有边相连，并求得各个顶点的度数。对于无向图，顶点 vi的度数是邻接矩阵中第 i行或第 i列值为 1的元素个数，即：
D（ vi） = = … （ 8-2）
1
0
],[
n
j
jiA?
1
0
],[
n
j
ijA
对于有向图，邻接矩阵中第 i行值为 1的元素个数为顶点 vi的出度，第 i列值为 1的元素的个数为顶点 vi的入度，即：
OD（ vi） = ; ID（ vi） = … （ 8-3）
1
0
],[
n
j
jiA?
1
0
],[
n
j
ijA
二、网络的邻接矩阵当 G=（ V,E）是一个网络时,G的邻接矩阵是具有如下性质的 n阶方阵：
Wij 当 （ vi,vj） 或 < vi,vj >?E（ G）
0 当 （ vi,vj） 或 < vi,vj >E（ G） 且 i=j
∞ 当 （ vi,vj） 或 < vi,vj > E（ G） 且 i≠j
A[i,j]=
其中 Wij表示边上的权值； ∞表示一个计算机允许的、大于所有边上权值的数。
V0
V1 V3
V234
56 78 25
V0
V2V1 45
5064
网络的邻接矩阵示例
0 56 34 78
56 0 ∞ ∞
34 ∞ 0 25
78 ∞ 25 0
0 ∞ 50
0 ∞ 45
64 ∞ 0
A3= A4=
（ a） G7的邻接矩阵 （ b） G8的邻接矩阵图 8.8 网络邻接矩阵示例邻接矩阵存储结构
#define FINITY 5000 /*此处用 5000代表无穷大 */
#define m 20 /*最大顶点数 */
typedef char vertextype; /*顶点值类型 */
typedef int edgetype; /*权值类型 */
typedef struct{
vertextype vexs[m]; /*顶点信息域 */
edgetype edges[m][m]; /*邻接矩阵 */
int n,e; /*图中顶点总数与边数 */
} mgraph; /*邻接矩阵表示的图类型 */
文件名,mgraph.h
/*********************************************************/
/* 图的邻接矩阵创建算法 */
/* 文件名,c_ljjz.c 函数名,creatmgraph1() */
/*********************************************************/
#include <stdio.h>
#include "mgraph.h"
void creatmgraph1(mgraph *g)
{int i,j,k,w; /*建立有向网络的邻接矩阵存储结构 */
printf("please input n and e:\n");
scanf("%d%d",&g->n,&g->e); /*输入图的顶点数与边数 */
getchar(); /*取消输入的换行符 */
printf("please input vexs:\n");
for(i=0;i<g->n;i++) /*输入图中的顶点值 */
g->vexs[i]=getchar();
for(i=0;i<g->n;i++) /*初始化邻接矩阵 */
for(j=0;j<g->n;j++)
if (i==j) g->edges[i][j]=0;
else g->edges[i][j]=FINITY;
printf("please input edges:\n");
for (k=0;k<g->e;k++) /*输入网络中的边 */
{ scanf("%d%d%d",&i,&j,&w);
g->edges[i][j]=w;
/*若是建立无向网,只需在此加入语句 g->edges[j][i]=w;即可 */
} }
说明,
当建立有向网时，边信息以三元组（ i,j,w）的形式输入,i,j分别表示两顶点的序号,w表示边上的权。
对于每一条输入的边信息（ i,j,w），只需将 g-
>edges[i][j]赋值为 w。
算法 8.5中用到的 creatmgraph2()是用于建立无向网络的函数，它与 creatmgraph1()的区别在于对每一条输入的边信息（ i,j,w），需同时将 g->edges[i][j] 和
g->edges[j][i]赋值为 w。
当建立非网络的存储结构时，所有的边信息只需按二元组（ i,j）的形式输入。
8.3.2邻接表及其实现用邻接矩阵表示法存储图，占用的存储单元个数只与图中顶点的个数有关，而与边的数目无关。
一个含有 n个顶点的图，如果其边数比 n2少得多，
那么它的邻接矩阵就会有很多空元素，浪费了存储空间。
无向图的邻接表对于图 G中的每个顶点 vi，该方法把所有邻接于 vi
的顶点 vj链成一个带头结点的单链表，这个单链表就称为顶点 vi的邻接表。单链表中的每个结点至少包含两个域，一个为 邻接点域 （ adjvex），它指示与顶点 vi
邻接的顶点在图中的位序，另一个为 链域 （ next），
它指示与顶点 vi邻接的下一个结点。
adjvex nextvertex firstdege
为了便于随机访问任一顶点的邻接表，可将所有头结点顺序存储在一个向量中就构成了图的邻接表存储。最后将图的顶点数及边数等信息与邻接表放在一起来描述图的存储结构。
v0
v1 v3
v2
图 8.7 无向图 G9
1 2 3 ^
0 2 ^
0 1 3 ^
0 2 ^
V0
V1
V2
V3
图 8.9 G9的邻接表表头结点结构边结点结构对于无向图,vi的邻接表中每个表结点都对应于与 vi相关联的一条边；对于有向图来说，如果每一顶点 vi的邻接表中每个表结点都存储以 vi的为始点射出的一条边，则称这种表为有向图的 出边表 （有向图的邻接表），反之，若每一顶点 vi的邻接表中每个表结点都对应于以 vi为终点的边（即射入 vi的边），则称这种表为有向图的 入边表 （又称逆邻接表）。
v0
v1
v2
v3
1 ^
0 2 ^
0 1 ^
1 ^
G10的出边表
0
1
2
3 ^
2 ^
0 2
1 ^
3 ^
G10的入边表
v3
v1
v0 v2
图 8.7(b)有向图 G10
在无向图的邻接表中，顶点 vi的度为第 i个链表中结点的个数；而在有向图的出边表中，第 i个链表中的结点个数是顶点 vi的出度；为了求入度，必须对整个邻接表扫描一遍，所有链表中其邻接点域的值为 i
的结点的个数是顶点 vi的入度。
1 2 3 ^
0 2 ^
0 1 3 ^
0 2 ^
V0
V1
V2
V3
V0的度为 3
v0
v1
v2
v3
1 ^
0 2 ^
0 1 ^
1 ^
G10的出边表
V0的出度为
1，入度为 2
邻接表的存储结构
/****************************************************/
/* 邻接表存储结构 文件名,adjgraph.h */
/****************************************************/
#define m 20 /*预定义图的最大顶点数 */
typedef char datatype; /*顶点信息数据类型 */
typedef struct node{ /*边表结点 */
int adjvex; /*邻接点 */
struct node *next;
}edgenode; adjvex next
边结点结构
typedef struct vnode{ /*头结点类型 */
datatype vertex; /*顶点信息 */
edgenode *firstedge; /*邻接链表头指针 */
}vertexnode;
typedef struct{ /*邻接表类型 */
vertexnode adjlist [m]; /*存放头结点的顺序表 */
int n,e; /*图的顶点数与边数 */
}adjgraph;
vertex firstdege
头结点结构
/********************************************************/
/* 无向图的邻接表创建算法 */
/* 文件名 c_ljb.c 函数名,createadjgraph() */
/********************************************************/
void createadjgraph(adjgraph *g)
{ int i,j,k;
edgenode *s;
printf("Please input n and e:\n");
scanf("%d%d",&g->n,&g->e); /*输入顶点数与边数 */
getchar();
printf("Please input %d vertex:",g->n);
for(i=0;i<g->n;i++)
{scanf(“%c”,&g->adjlist[i].vertex); /*读入顶点信息 */
g->adjlist[i].firstedge=NULL; /*边表置为空表 */
}
printf("Please input %d edges:",g->e);
for(k=0;k<g->e;k++) /*循环 e次建立边表 */
{ scanf("%d%d",&i,&j); /*输入无序对 （ i,j） */
s=(edgenode *)malloc(sizeof(edgenode));
s->adjvex=j; /*邻接点序号为 j*/
s->next=g->adjlist[i].firstedge;
g->adjlist[i].firstedge=s; /*将新结点 *s插入顶点 vi
的边表头部 */
s=(edgenode *)malloc(sizeof(edgenode));
s->adjvex=i; /*邻接点序号为 i*/
s->next=g->adjlist[j].firstedge;
g->adjlist[j].firstedge=s;
/*将新结点 *s插入顶点 vj的边表头部 */
}
}
算法 8.2 建立无向图的邻接表算法说明：一个图的邻接矩阵表示是唯一的，但其邻接表表示不唯一，这是因为在邻接表结构中，各边表结点的链接次序取决于建立邻接表的算法以及边的输入次序。
4 5
ABCD
0 1 0 2 0 3 1 2 2 3
A
B D
C
例,若需建立下图所示的无向图邻接表存储结构,则在执行程序 c_ljb.c时如果输入的信息为：
则将建立如下的邻接表存储结构。
A 3-->2-->1
B 2-->0
C 3-->1-->0
D 2-->0
8.3.3邻接多重表
在邻接多重表中，每一条边只有一个边结点。为有关边的处理提供了方便。
–边结点的结构
mark vexi linki vexj linkj
其中,mark 是记录是否处理过的标记； vexi和
vexj是依附于该边的两顶点位置。 lniki域是链接指针，
指向下一条依附于顶点 vexi的边； linkj也是链接指针，
指向下一条依附于顶点 vexj的边。需要时还可设置一个存放与该边相关的权值的域 cost。
–顶点结点的结构存储顶点信息的结点表以顺序表方式组织，每一个顶点结点有两个数据成员：其中,vertex 存放与该顶点相关的信息,firstedge 是指示第一条依附于该顶点的边的指针。
在邻接多重表中,所有依附于同一个顶点的边都链接在同一个单链表中。
从顶点 i 出发,可以循链找到所有依附于该顶点的边，也可以找到它的所有邻接顶点。
vertex Firstedge
V0
V1 V3
V234
56 78 25
V0
V1
V2
V3
56 0 1 ^
34 0 2
78 0 ^ 3
25 2 ^ 3 ^
0
1
2
3
无向网络的邻接多重表示例其中边表结点增加了一个存储权值的数据域 。
8.4 图的遍历图的遍历：从图的某顶点出发，访问图中所有顶点，
并且每个顶点仅访问一次。在图中，访问部分顶点后，
可能又沿着其他边回到已被访问过的顶点。为保证每一个顶点只被访问一次，必须对顶点进行标记，一般用一个辅助数组 visit[n]作为对顶点的标记，当顶点 vi未被访问,visit[i]值为 0；当 vi已被访问，则 visit[i]值为 1。
图的遍历与树的遍历有什么不同有两种遍历方法 （ 它们对无向图，有向图都适用）
深度优先遍历
广度优先遍历
8.4.1深度优先遍历从图中某顶点 v出发：
1）访问顶点 v；
2）依次从 v的未被访问的邻接点出发，继续对图进行深度优先遍历；
对于给定的图 G=（ V,E）,首先将 V中每一个顶点都标记为未被访问,然后,选取一个源点 v?V,将 v
标记为已被访问,再递归地用深度优先搜索方法,依次搜索 v的所有邻接点 w。 若 w未曾访问过,则以 w为新的出发点继续进行深度优先遍历,如果从 v出发有路的顶点都已被访问过,则从 v的搜索过程结束 。 此时,如果图中还有未被访问过的顶点 （ 该图有多个连通分量或强连通分量 ）,则再任选一个未被访问过的顶点,并从这个顶点开始做新的搜索 。 上述过程一直进行到 V中所有顶点都已被访问过为止 。
V0
V7
V6V5V4V3
V2V1
V0
V3
V2
V6V4
例序列 1：
V0,V1,V3,V7,V4,V2,V5,V6
深度优先遍历过程：
由于没有规定访问邻接点的顺序，
深度优先序列不是唯一的序列 2：
V0,V1,V4,V7,V3,V2,V5,V6
c0
c1
c3
c2
c4
c5
c0
c1
c3
c2
c4
c5
DFS序列,c0? c1? c3? c4? c5? c2
但是，当采用邻接表存储结构并且存储结构已确定的情况下，遍历的结果将是确定的。
采用邻接表存储结构的深度优先遍历算法实现：
/*********************************************************/
/* 图的深度优先遍历算法 */
/* 文件名,dfs.c 函数名,dfs(),dfstraverse() */
/*********************************************************/
int visited[m];
void dfs(adjgraph g,int i)
{ /*以 vi为出发点深度优先遍历顶点 vi所在的连通分量 */
edgenode *p;
printf("visit vertex,%c \n",g.adjlist[i].vertex); /*访问顶点 i*/
visited[i]=1;
p=g.adjlist[i].firstedge;
while (p) /*从 p的邻接点出发进行深度优先搜索 */
{ if (!visited[p->adjvex])
dfs(g,p->adjvex); /*递归 */
p=p->next;
}
}
void dfstraverse(adjgraph g)
{ /* 深度优先遍历图 g */
int i;
for (i=0;i<g.n;i++)
visited[i]=0; /*初始化标志数组 */
for (i=0;i<g.n;i++)
if (!visited[i]) /*vi未访问过 */
dfs(g,i);
}
算法 8.3 图的深度优先遍历算法（邻接表表示法）
算法分析：
对于具有 n个顶点和 e条边的无向图或有向图，遍历算法 dfstraverse对图中每个顶点至多调用一次 dfs。
从 dfstraverse中调用 dfs或 dfs内部递归调用自己的最大次数为 n。当访问某顶点 vi时,dfs的时间主要耗费在从该顶点出发搜索它的所有邻接点上。用邻接表表示图时，需搜索第 i个边表上的所有结点，因此，对所有 n个顶点访问，在邻接表上需将边表中所有 O（ e）
个结点检查一遍。所以,dfstraverse算法的时间复杂度为 O（ n+e）。
8.4.2广度优先遍历图中某未访问过的顶点 vi出发：
1）访问顶点 vi；
2）访问 vi 的所有未被访问的邻接点 w1,w2,…w k ；
3）依次从这些邻接点出发，访问它们的所有未被访问的邻接点 ; 依此类推，直到图中所有访问过的顶点的邻接点都被访问；
V0
V7
V6V5V4V3
V2V1
V7
求图 G 的以 V0起点的的广度优先序列
V0,V1,V2,V3,V4,V5,V6,V7
例
c0
c1
c3
c2
c4
c5
从 C0出发的 BFS序列为：
由于没有规定访问邻接点的顺序，
广度优先序列不是唯一的
c0? c1? c2? c3? c4? c5
从图中某顶点 vi出发：
1）访问顶点 vi ；（容易实现）
2）访问 vi 的所有未被访问的邻接点 w1,w2,…w k ；
3）依次从这些邻接点（在步骤 2）访问的顶点）出发，访问它们的所有未被访问的邻接点 ; 依此类推，
直到图中所有访问过的顶点的邻接点都被访问；
为实现 3），需要保存在步骤 (2）中访问的顶点，而且访问这些顶点邻接点的顺序为：先保存的顶点，
其邻接点先被访问。
广度优先算法：
在广度优先遍历算法中，
需设置一队列 Q，
保存已访问的顶点，
并控制遍历顶点的顺序。
QUEUE
V0 V1 V2 V3 V4 V5 V6 V7
V1 V2 V3V0 V4 V5 V6 V7
V0
V7
V6V5V4V3
V2V1
数据结构：
1）全局标志数组
int visited[m]; /*全局标志向量 */
2）邻接表存储结构
/******************************************************/
/* 图的广度优先遍历算法 */
/* 程序名 bfs.c 函数名 bfs(),bfstraverse() */
/******************************************************/
void bfs(adjgraph g,int i)
{ int j; /*从顶点 i出发广度优先遍历顶点 i所在的连通分量 */
edgenode *p;
int queue[20],head,tail; /*FIFO队列 */
head=-1; tail=-1; /*初始化空队列 */
printf("%c ",g.adjlist[i].vertex); /*访问源点 v*/
visited[i]=1;
queue[++tail]=i; /*被访问结点进队 */
while (tail>head) /*当队列非空时,执行下列循环体 */
{ j=queue[++head]; /*出队 */
p=g.adjlist[j].firstedge;
while (p) /*广度优先搜索邻接表 */
{ if (visited[p->adjvex]==0)
{ printf("%c ",g.adjlist[p->adjvex].vertex);
queue[++tail]=p->adjvex;
visited[p->adjvex]=1;
}
p=p->next;
}
} }
int bfstraverse(adjgraph g,datatype v)
{ int i,count=0; /*广度优先遍历图 g*/
for (i=0;i<g.n;i++) visited[i]=0; /*初始化标志数组 */
i=loc(g,v); /*寻找顶点 v在邻接表中的位序 */
if (i!=-1)
{ count++; /*连通分量个数加 1*/
bfs(g,i);
}
for (i=0;i<g.n;i++)
if (!visited[i]) /*vi未访问过 */
{ printf("\n");
count++; /*连通分量个数加 1*/
bfs(g,i); /*从顶点 i出发广度优先遍历图 g*/
}
return count; /*返回无向图 g中连通分量的个数 */
}
算法 8.4 图的广度优先遍历算法（邻接表表示法）
算法的时间复杂度与深度优先算法相同。
作业：
8.4 图 8.31是某个无向图的邻接表,请
（ 1） 画出此图；
（ 2） 写出从顶点 A开始的 DFS遍历结果 。
（ 3） 写出从顶点 A开始的 BFS遍历结果 。
8.5生成树与最小生成树对于一个无向的连通图 G=（ V,E），设 G'是它的一个子图，如果 G'中包含了 G中所有的顶点
（即 V（ G'） =V（ G））且 G'是无回路的连通图，
则称 G'为 G一棵的生成树。
深度优先生成树：按深度优先遍历生成的生成树广度优先生成树：按广度优先遍历生成的生成树
c0
c1
c3
c2
c4
c5
c0
c1
c3
c2
c4
c5
有向图的生成树
c0
c1 c3c2 c4
c5 c6
c0
c1 c3c2 c4
c5 c6
c0
c1 c3c2 c4
c5 c6
（ a）以 c0为根的有向图 （ b） DFS生成树 （ c） BFS生成树非连通图的生成森林
V0 V1
V3 V4
V2 V6
V8
V7
V5
V9
V0
V1
V3 V
4
V2
V6 V
8
V7V
5
V9
V0 V1
V3 V4
V2
V8
V7
V9V6
V5
（ a）不连通的无向图 G12 （ b）图 G12的一个 DFS生成森林
（ c）图 G12的一个 BFS生成森林
8.5.1最小生成树的定义若有一个连通的无向图 G,有 n 个顶点，并且它的边是有权值的。在 G 上构造生成树 G’,使这 n-1
条边的权值之和在所有的生成树中最小 。
例要在 n 个城市间建立交通网,要考虑的问题如何在保证 n 点连通的前题下最节省经费?
),(
)(
Evu
uvwTW
A
B
C D
E F
10
10
15 12
12 8
7 6
6
5
上述问题即要使得生成树各边权值之各最小，即：
构造最小生成树的准则：
必须只使用该网络中的边来构造最小生成树；
必须使用且仅使用 n-1条边来联接网络中的 n个顶点；
不能使用产生回路的边。
假设 G=（ V,E）是一个连通网,U是顶点集 V的一个非空真子集，若（ u,v）是满足 u?U,v?V-U的边（称这种边为两栖边）且（ u,v）在所有的两栖边中具有最小的权值（此时，称（ u,v）为最小两栖边），则必存在一棵包含边（ u,v）的最小生成树。
MST性质：
证明：
u v v’
u’
U V-U
设（ u,v）是连接 U与（ V-U）之间所有边中的最小代价边（最小两栖边）。反证时假设 G中的任何一棵最小生成树都不含此最小两栖边。设 T是连通网上的一棵最小生成树，当将（ u,v）加入到 T中时，由生成树的定义,T中必存在一条包含（ u,v
）的回路。另一方面，由于 T是生成树，则在 T上必存在另一条边（ u’,v’），其中 u’? U,v’? V-
U,且 u和 u’之间,v和 v’之间均有路径相通，删去边（ u’,v’），便可消除上述回路，同时得到另一棵生成树 T’。因为（ u,v）的代价不高于（ u’,v’
），则 T’的代价亦不高于 T,T’是包含（ u,v）的一棵最小生成树。由此和假设矛盾。
普里姆算法的基本思想：
8.5.2最小生成树的普里姆算法
(Prim)算法 和 (Kruskal)算法 是两个利用 MST性质构造最小生成树的算法。
从连通网络 G = { V,E }中的某一顶点 u0 出发，选择与它关联的具有最小权值的边 (u0,v)，将其顶点加入到生成树的顶点集合 U中。
以后每一步从一个顶点在 U中，而另一个顶点不在 U中的各条边中选择权值最小的边 (u,v),把它的顶点加入到 集合 U中。如此继续下去，直到网络中的所有顶点都加入到生成树顶点集合 U中为止。
Prim算法的基本步骤如下：
（ 1） 初始化,U={u0},TREE={};
（ 2） 如果 U=V（ G）,则输出最小生成树 T,并结束算法；
（ 3） 在所有两栖边中找一条权最小的边 （ u,v）
（ 若候选两栖边中的最小边不止一条,可任选其中的一条 ）,将边 （ u,v） 加入到边集 TREE中,并将顶点 v并入集合 U中 。
（ 4） 由于新顶点的加入,U的状态发生变化,需要对 U与 V-U之间的两栖边进行调整 。
（ 5） 转步骤 （ 2）
A
B
C D
E F
10
10
15 12
12 8
7 6
6
5
（ a）无向网
5
A
B
C D
E F
10
7 6
10
（ e）选取（ B,F）
A
B
C D
E F
10
15 12
∞
∞
（ b）初始状态
5
A
B
C D
E F
10
15 7 6
（ c）选取（ A,B）
5
A
B
C D
E F
10
15 7 6
（ d）选取（ B,D）
5
A
B
C D
E F
10
7 6
10
（ f）选取（ B,C）
5
A
B
C D
E F
10
7 6
10
（ g）选取（ E,F）
Prim算法实现：
1、连通图用邻接矩阵 net表示：
edges[i][j]=
Wij 当（ vi,vj）? E（ G）且权为 Wij
否则?
0 当 i==j
2、边 tree（生成树） edge tree[n-1]
typedef struct edgedata
{ int beg,en; /*beg,en是结点序号 */
int length; /*边长 */
} edge;
beg
en
length
tree 0 1 2 3 4
0 0 0 0 0
1 2 3 4 5
10 12 ∞ 15 ∞
(a)初始态 K=0 m=1
K=0
beg
en
length
tree 0 1 2 3 4
0 0 0 0 0
1 2 3 4 5
10 12 ∞ 15 ∞
(b)最小两栖边（ 0,1）
Prim算法构造最小生成树的过程
K=1
beg
en
length
tree 0 1 2 3 4
0 1 1 0 1
1 2 3 4 5
10 7 5 15 6
(c)最小两栖边（ 0,3）
K=2
beg
en
length
tree 0 1 2 3 4
0 1 1 0 1
1 3 2 4 5
10 5 7 15 6
(d)最小两栖边（ 1,5）
K=3
beg
en
length
tree 0 1 2 3 4
0 1 1 5 1
1 3 5 4 2
10 5 6 10 7
(e)最小两栖边（ 1,2）
beg
en
length
tree 0 1 2 3 4
0 1 1 1 5
1 3 5 2 4
10 5 6 7 10
(f) tree中存储了最小生成树的边算法关键一步,求第 k条轻边，将其加入 tree中
1）求当前最小两栖边及应添加的点 v
min=tree[k].length;
s=k;
for (j=k+1;j<=g.n-2;j++)
if (tree[j].length<min)
{min=tree[j].length;
s=j;
}
v=tree[s].en; /*入选顶点为 v*/
2）通过交换，将当前轻边加入 tree中
x=tree[s]; tree[s]=tree[k]; tree[k]=x;
3）调整各剩余点对应的最小两栖边（由 v加入引起）
for (j=k+1;j<=g.n-2;j++)
{ d=g.edges[v][tree[j].en];
if (d<tree[j].length)
{ tree[j].length=d;
tree[j].beg=v;
}
}
算法总体控制：
1）初始化：建立初始入选点，并初始化生成树边集 tree。
for (v=1;v<=g.n-1;v++)
{ tree[v-1].beg=0; /* 此处从顶点 v0开始求最小生成树 */
tree[v-1].en=v;
tree[v-1].length=g.edges[0][v];
}
2）依次求当前最小两栖边，并将其加入 tree
for (k=0;k<=g.n-3;k++) 执行关键一步一般来讲，
由于普里姆算法的 时间复杂度为 O(n2)，则适于稠密图。
程序演示,prim.c
8.5.3最小生成树的克鲁斯卡尔算法
Kruskal算法基本思想：
为使生成树上边的权值之和最小，显然，其中每一条边的权值应该尽可能地小。克鲁斯卡尔算法的做法就是：先构造一个只含 n个顶点的子图 SG，
然后从权值最小的边开始，若它的添加不使 SG中产生回路，则在 SG上加上这条边，如此重复，直至加上 n-1条边为止。
克鲁斯卡尔算法需对 e条边按权值进行排序，其时间复杂度为 O(eloge)，则适于稀疏图。
算法：
（ 1） 初始化,TV={v0,v1,…,vn},TE={}；
（ 2） 如果 TE具有 n-1条边,则输出最小生成树 T，
并结束算法 。
（ 3） 在有序的 E（ G） 边表序列中,从当前位置向后寻找满足下面条件的一条边 （ u,v）,使得 u在一个连通分量上,v在另一个连通分量上,即 （ u，
v） 是满足此条件权值最小的边,将其加入到 T中,
合并 u与 v所在的两个连通分量为一个连通分量 。
（ 4） 转 （ 2）
v0
v1
v2
v3
v4 v5
6 5
15 5
4 23 6
6
(a) 无向网络图
Kruskal算法动态演示：
15
4 23
v0
v1
v2
v3
v4 v5
(b) 最小生成树求解过程
5
A
B
C D
E F
(a)
5
A
B
C D
E F
6
(b)
5
A
B
C D
E F
67
(c)
5
A
B
C D
E F
67
10
(d)
5
A
B
C D
E F
67
10
10
(e)
Kruskal算法构造最小生成树的过程
/*********************************************/
/* kruskal求解最小生成树算法 */
/* 文件名 kruskal.c 函数名 kruskal() */
/*********************************************/
void kruskal(edge adjlist[],edge tree[],int cnvx[],int n)
{ int v=0,j,k;
for (j=0;j<n;j++)
cnvx[j]=j; /* 设置每一个顶点的连通分量 */
for (k=0;k<n-1;k++) /*树中共有 n-1条边 */
{ while (cnvx[adjlist[v].beg]==cnvx[adjlist[v].en] ) v++;
/*找到属于两个连通分量权最小的边 */
tree[k]=adjlist[v]; /*将边 v加入到生成树中 */
for (j=0;j<n;j++) /*两个连通分量合并为一个连通分量 */
if (cnvx[j]==cnvx[adjlist[v].en])
cnvx[j]=cnvx[adjlist[v].beg];
v++;
}
printf("最小生成树是,\n");
for (j=0;j<n-1;j++)
printf("%3d%3d%6d\n",tree[j].beg,tree[j].en,tree[j].length);
}
算法 8.6 Kruskal求解最小生成树
8.6最短路径问题的提出：
交通咨询系统,通讯网,计算机网络常要寻找两结点间最短路径；
交通咨询系统,A到 B 最短路径；
计算机网络,发送 Email节省费用 A到 B沿最短路径传送；
路径长度：路径上边数路径上边的权值之和最短路径：两结点间权值之和最小的路径；
A
B
D
CF
E 2
4
1528
8
18
10
13
始点 终点 最短路径 路径长度
A B （ A,C,B） 19
C （ A,C） 4
D （ A,C,F,D） 25
E （ A,C,B,E） 29
F （ A,C,F） 12
4
如何求从某源点到其余各点的最短路径？
本节介绍求最短路径的两个算法
求从某个源点到其他各顶点的最短路径 （ 单源最短路径 ） 。
求每一对顶点之间的最短路径 。
8.6.1单源最短路径单源最短路径问题是指：对于给定的有向网 G=（ V，
E）,求源点 v0到其它顶点的最短路径 。
Dijkstra提出了一个按路径长度递增的顺序逐步产生最短路径的方法，称为 Dijkstra算法。
Dijkstra算法的基本思想：
把图中所有顶点分成两组,第一组 包括已确定最短路径的顶点,初始时只含有一个源点,记为集合 S；
第二组 包括尚未确定最短路径的顶点,记为 V-S。 按最短路径长度递增的顺序逐个把 V-S中的顶点加到 S中去,直至从 v0出发可以到达的所有顶点都包括到 S中 。
在这个过程中,总保持从 v0到第一组 （ S） 各顶点的最短路径都不大于从 v0到第二组 （ V-S） 的任何顶点的最短路径长度,第二组的顶点对应的距离值是从 v0到此顶点的只包括第一组 （ S） 的顶点为中间顶点的最短路径长度 。 对于 S中任意一点 j,v0到 j的路径长度皆小于 v0到 （ V-S） 中任意一点的路径长度 。
引入一个辅助数组 d[]。它的每一个分量 d[i]表示当前找到的从 源点 v0到 顶点 vi 的最短路径的长度。初始状态：
–若从源点 v0到顶点 vi有边，则 d[i]为该边上的权值
–若从源点 v0到顶点 vi 没有边，则 d[i]为 +? 。
一般情况下，假设 S 是已求得的最短路径的终点的集合，则可证明：下一条最短路径必然是从 v0 出发，中间只经过 S中的顶点便可到达的那些顶点 vx (vx?V-S
)的路径中的一条。
每次求得一条最短路径之后，其终点 vk 加入集合 S，
然后 对所有的 vi?V-S，修改其 d[i]值。
Dijkstra算法可描述如下：
１） 初始化：把图中的所有顶点分成两组；初始化源点到各点的距离向量。
S：已确定最短路径的点集，初始 S ← { v0 };
S：尚未确定最短路径的点集，初始 S ← V（ G） -V0 ;
d[j] ← g.edges[v0][j],j = 1,2,…,n-1;
// n为图中顶点个数
２） 求出 S与 S间的最短路径，及相应的点 v
d[v] ← min{ d[i] },i? V（ G） - S ;
S ← S U { v };
v0
s
vmin
s
v0
s
v
s
i
v0
s
v
min
s
３）由于 v的加入，修改 S中各结点与 S中各点的最短距离：
d[i] ← min{ d[i],d[v] + edges[v][i] },
对于每一个 i? V- S ;
４）判断,若 S = V,则算法结束，否则转２）。
iedges[v][i]
Dijkstra算法中各辅助数组的变化如何从表中读取源点 0到终点 v
的最短路径？例如顶点 A到 D的最短距离是 d[3]=25,根据 p[3] =5
→ p[5] =2 → p[2]=0，反过来排列，得到路径 0,2,5,3（即 A,C
,F,D）。
A
B
D
CF
E 2
4
1528
8
18
10
13
4
算法实现如下：
/***************************************************/
/* 单源最短路径算法 文件名,dijkstra.c */
/* 函数名,spath_dij(),print_gpd() */
/***************************************************/
#include "c_ljjz.c" /*引入邻接矩阵创建程序 */
typedef enum{FALSE,TRUE} boolean; /*false为 0,true为 1*/
typedef int dist[m]; /* 距离向量类型 */
typedef int path[m]; /* 路径向量类型 */
void spath_dij(mgraph g,int v0,path p,dist d)
{ boolean final[m];
int i,k,j,v,min,x;
/* 第 1步 初始化集合 S与距离向量 d */
for (v=0;v<g.n;v++)
{ final[v]=FALSE;
d[v]=g.edges[v0][v];
if (d[v]<FINITY && d[v]!=0) p[v]=v0; else p[v]=-1;
/* v无前驱 */
}
final[v0]=TRUE; d[v0]=0; /*初始时 s中只有 v0一个顶点 */
/* 第 2步 依次找出 n-1个结点加入 S中 */
for (i=1;i<g.n;i++)
{ min=FINITY;
for (k=0;k<g.n;++k) /*找最小边及对应的入选顶点 */
if (!final[k] && d[k]<min) {v=k;min=d[k];} /* !final[k] 表示 k还在 V-S中 */
printf("\n%c---%d\n",g.vexs[v],min); /*输出本次入选的顶点及距离 */
if (min==FINITY) return;
final[v]=TRUE; /* V加入 S*/
/*第 3步 修改 S与 V-S中各结点的距离 */
for (k=0;k<g.n;++k)
if ( !final[k] && (min+g.edges[v][k]< d[k]) )
{ d[k]=min+g.edges[v][k];
p[k]=v; }
} /* end for */
}
void print_gpd(mgraph g,path p,dist d)
{ /*输出有向图的最短路径 */
int st[20],i,pre,top=-1; /*定义栈 st并初始化空栈 */
for (i=0;i<g.n;i++)
{ printf("\nDistancd,%7d,path:",d[i]);
st[++top]=i;
pre=p[i]; /*从第 i个顶点开始向前搜索最短路径上的顶点 */
while (pre!=-1)
{ st[++top]=pre;
pre=p[pre]; }
while (top>0)
printf("%2d",st[top--]); } }
void main() /*主程序 */
{ mgraph g; /* 有向图 */
path p; /* 路径向量 */
dist d; /* 最短路径向量 */
int v0;
creatmgraph1(&g); /*创建有向网的邻接矩阵 */
print(g); /*输出图的邻接矩阵 */
printf("please input the source point v0:");
scanf("%d",&v0); /*输入源点 */
spath_dij(g,v0,p,d); /*求 v0到其他各点的最短距离 */
print_gpd(g,p,d); /*输出 V0到其它各点的路径信息及距离 */
}
8.6.2所有顶点对的最短路径
问题的提法：已知一个各边权值均大于 0的带权有向图，对每一对顶点 vi? vj，要求求出 vi 与 vj之间的最短路径和最短路径长度。
解决这个问题显然可以利用单源最短路径算法,
具体做法是依次把有向网 G中的每个顶点作为源点
,重复执行 Dijkstra算法 n次,即执行循环体,总的时间复杂度为 O(n3)。
for （ v=0； v<g.n； v++）
{ spath_dij（ g,v,p,d） ；
print_gpd（ g,p,d） ；
}
下面将介绍用弗洛伊德 (Floyd)算法来实现此功能,时间复杂度仍为 O(n3),但该方法比调用 n次迪杰斯特拉方法更直观一些。
2,弗洛伊德算法的基本思想弗洛伊德算法仍然使用前面定义的图的邻接矩阵
edges[N][N]来存储带权有向图。算法的基本思想是,
设置一个 NxN的矩阵 A[N][N]，其中除对角线的元素都等于 0外，其它元素 A[i][j]的值表示顶点 i到顶点 j的最短路径长度，运算步骤为：
开始时，以任意两个顶点之间的有向边的权值作为路径长度，没有有向边时，路径长度为 ∞，此时,A
[i][j]=edges[i][j],
以后逐步尝试在原路径中加入其它顶点作为中间顶点,如果增加中间顶点后,得到的路径比原来的路径长度减少了,则以此新路径代替原路径,修改矩阵元素 。 具体做法为：
第一步,让所有边上加入中间顶点 0,取 A[i][j]与
A[i][0]+A[0][j]中较小的值作 A[i][j]的值,
第二步,让所有边上加入中间顶点 1,取 A[i][j]与
A[i][1]+A[1][j]中较小的值,完成后得到 A[i][j] …,如此进行下去,当第 n步完成后,得到 A[i][j],即为我们所求结果,A[i][j]表示顶点 i到顶点 j的最短距离 。
因此,弗洛伊德算法可以描述为,
A(-1)[i][j]=edges[i][j]; /*edges为图的邻接矩阵 */
A(k+1)[i][j]=min{Ak [i][j],Ak [i][k+1]+Ak [k+1][j]}
其中 k=-1,1,2,…,n-2
下面给出 Floyd的算法实现 。
/*************************************************/
/* Floyd 所有顶点对最短路径算法 */
/* 文件名,floyd.c 函数名,floyd1() */
/*************************************************/
typedef int dist[m][m]; /* 距离向量 */
typedef int path[m][m]; /* 路径向量 */
void floyd1(mgraph g,path p,dist d)
{ int i,j,k;
for (i=0;i<g.n;i++) /*初始化 */
for (j=0;j<g.n;j++)
{ d[i][j]=g.edges[i][j];
if (i!=j && d[i][j]<FINITY ) p[i][j]=i; else p[i][j]=-1;
}
for (k=0;k<g.n;k++) /*递推求解每一对顶点间的最短距离 */
{ for (i=0;i<g.n;i++)
for (j=0;j<g.n;j++)
if (d[i][j]>(d[i][k]+d[k][j]))
{ d[i][j]=d[i][k]+d[k][j];
p[i][j]=k;
}
}
}
算法 8.8 求网络中每一对顶点之间的最短路径
2
0
3
1
6
8
3 5 9
1
4
2
0 1 ∞ 4
∞ 0 9 2
3 5 0 8
∞ ∞ 6 0
例求下图中所在顶点对之间的最短路径。
D D-1 D0 D1 D2 D3
0 1 2 3 0 1 2 3 0 1 2 3 0 1 2 3 0 1 2 3
0 0 1 ∞ 4 0 1 ∞ 4 0 1 10 3 0 1 10 3 0 1 9 3
1 ∞ 0 9 2 ∞ 0 9 2 ∞ 0 9 2 12 0 9 2 11 0 8 2
2 3 5 0 8 3 4 0 7 3 4 0 6 3 4 0 6 3 4 0 6
3 ∞ ∞ 6 0 ∞ ∞ 6 0 ∞ ∞ 6 0 9 10 6 0 9 10 6 0
P P-1 P0 P1 P2 P30 1 2 3 0 1 2 3 0 1 2 3 0 1 2 3 0 1 2 3
0 1 0 -1 0 -1 0 -1 0 -1 0 1 1 -1 0 1 1 -1 0 3 1
1 -1 -1 1 1 -1 -1 1 1 -1 -1 1 1 2 -1 1 1 3 -1 3 1
2 2 2 -1 2 2 0 -1 0 2 0 -1 1 2 0 -1 1 2 0 -1 1
3 -1 -1 3 -1 -1 -1 3 -1 -1 -1 3 -1 2 2 3 -1 2 2 3 -1
8.7 拓扑排序有向无环图：没有回路的有向图某工程可分为 7个子工程，若用顶点表示子工程（
也称活动）,用弧表示子工程间的顺序关系。工程流程可用如下 AOV网表示
AOV网 ( activity on vertex net )
用顶点表示活动，边表示活动的顺序关系的有向图称为 AOV网。
应用,工程流程、生产过程中各道工序的流程、程序流程、课程的流程。
一 AOV网对工程问题，人们至少关心如下两类问题：
1）工程能否顺序进行，即工程流程是否“合理”？
2）完成整项工程至少需要多少时间，哪些子工程是影响工程进度的关键子工程？
二 AOV网与拓扑排序
拓扑排序
V5V3
V2
V0
V1 V4 V6
例 1 某工程可分为 V0,V1,V2,V3,V4,V5,V6 7
个子工程,工程流程可用如下 AOV网表示。其中顶点
：表示子工程（也称活动）,弧：表示子工程间的顺序关系。
为求解工程流程是否“合理”，通常用 AOV网的有向图表示工程流程。
V5V3
V2
V0
V1 V4 V6
例 课程流程图某校计算机专业课程流程可 AOV网表示。其中顶点：
表示课程（也称活动）,弧：表示课程间的先修关系；
课程代号 课程名称先修课程
C0
C1
C2
C3
C4
C5
C6
C7
C8
高等数学信息技术基础离散数学数据结构程序设计语言编译原理操作系统电子线路基础计算机组成原理无无
C0,C1
C2,C4
C1
C3,C4
C3,C8
C0
C7
C0
C2
C1
C7 C8 C6
C3
C4 C5
如何安排施工计划？
如何安排教学计划？
两个可行的学习计划为：
C0?C1?C2?C4?C7?C8?C3?C6?C5
和
C1?C0?C7?C8?C2?C4?C3?C5?C6
可行的计划的特点：若在流程图中顶点 v是顶点
u 的前趋，则在计划序列中顶点 v 也是 u的前趋。
拓扑序列,有向图 D的一个顶点序列称作一个拓扑序列，如果该序列中任两顶点 v,u,若在 D中 v是 u前趋，则在序列中 v也是 u前趋。
拓扑排序,就是将有向图中顶点排成拓扑序列。
拓扑排序的应用
安排施工计划
判断工程流程的是否合理如何判断 AOV网（有向图）
是否存在有向回路？ AOV网（有向图）
不存在有向回路当且仅当能对 AOV网进行拓扑排序
1) 输入 AOV网络。令 n 为顶点个数。
2) 在 AOV网络中选一个没有直接前驱（入度为 0）
的顶点,并输出之 ;
3) 从图中删去该顶点,同时删去所有它发出的有向边 ;
4) 重复以上 (2),(3)步,直到
–全部顶点均已输出，拓扑有序序列形成，拓扑排序完成；或
–图中还有未输出的顶点，但已跳出处理循环。
这说明图中还剩下一些顶点，它们都有直接前驱，再也找不到没有前驱的顶点了。这时 AOV
网络中必定存在有向环。
拓扑排序过程拓扑排序的过程
C0 C1 C2
C3 C4 C5
(a) 有向无环图
C1 C2
C5C3
(c) 输出顶点 C0
C0 C2
C5
C1
C3
(d) 输出顶点 C3
C0 C1 C2
C3 C4 C5
(b) 输出 C4
C1 C2
C5
(e) 输出顶点 C2
C5
C1
(f) 输出顶点 C1
C5
(g) 输出顶点 C5
最后得到的拓扑有序序列为 C4,C0,C3,C2,
C1,C5 。它满足图中给出的所有前驱和后继关系，
对于本来没有这种关系的顶点，如 C4和 C2，也排出了先后次序关系。
(h) 拓扑排序完成
AOV网络及其邻接表表示
C0
C1
C2
C3 0
C4
C5 0
0
1
2
3
4
5
id data firstedge
1
3
0
1
0
3
1
adjvex nxet
3 0
5
1 5 0
0 1 5 0
C0 C1 C2
C3 C4 C5
这种带入度的邻接表存储结构定义如下：
#define m 20
typedef char vertextype;
typedef struct node{ /*边结点类型定义 */
int adjvex;
struct node *next;
}edgenode;
typedef struct de /*带顶点入度的头结点定义 */
{ edgenode* firstedge;
vertextype vertex;
int id; /*顶点的入度域 */
}vertexnode;
typedef struct{ /*AOV网络的邻接表结构 */
vertexnode adjlist[m];
int n,e;
}aovgraph;
基于这种存储结构,拓扑排序算法可描述为算法 8.9。
/*************************************************/
/* 拓扑排序算法 */
/* 文件名,topsort.c 函数名,topsort() */
/*************************************************/
int topsort(aovgraph g) /*函数返回拓扑排序输出的顶点个数 */
{int k=0,i,j,v,flag[m];
int queue[m]; /*队列 */
int h=0,t=0;
edgenode* p;
for (i=0;i<g.n;i++) flag[i]=0; /*访问标记初始化 */
for(i=0;i<g.n;i++) /*先将所有入度为 0的顶点进队 */
if( g.adjlist[i].id==0 && flag[i]==0)
{ queue[++t]=i;flag[i]=1; }
while (h<t) /*当队列不空时 */
{ v=queue[++h]; /*队首元出队 */
printf("%c----->",g.adjlist[v].vertex);
k++; /*计数器加 1*/
p=g.adjlist[v].firstedge;
while(p) /*将所有与 v邻接的顶点的入度减 1*/
{ j=p->adjvex;
if (--g.adjlist[j].id==0 && flag[j]==0)
/*若入度为 0则将其进队 */
{queue[++t]=j; flag[j]=1;}
p=p->next;
}
}
return k;
}
算法 8.9 拓扑排序
8.8 关键路径
如果在无有向环的带权有向图中
– 用有向边表示一个工程中的活动 (Activity)
– 用边上权值表示活动持续时间 (Duration)
– 用顶点表示事件 (Event)
则这样的有向图叫做用边表示活动的网络，简称
AOE (Activity On Edges) 网络。
AOE网络在某些工程估算方面非常有用。例如，
可以使人们了解：
(1) 完成整个工程至少需要多少时间 (假设网络中没有环 )?
(2) 为缩短完成工程所需的时间,应当加快哪些活动?
在 AOE网络中,有些活动顺序进行，有些活动并行进行。
从源点到各个顶点，以至从源点到汇点的有向路径可能不止一条。这些路径的长度也可能不同。完成不同路径的活动所需的时间虽然不同，但只有各条路径上所有活动都完成了，整个工程才算完成。
因此，完成整个工程所需的时间取决于从源点到汇点的最长路径长度，即在这条路径上所有活动的持续时间之和。 这条路径长度最长的路径就叫做关键路径 (Critical Path)。
要找出关键路径，必须找出关键活动，即不按期完成就会影响整个工程完成的活动。
关键路径上的所有活动都是关键活动。因此，只要找到了关键活动，就可以找到关键路径,
例如，下图就是一个 AOE网 。
V3
V1
a4=3
a1=3
a2=2 a6=3a5=4
a3=2 a7=2
a8=1
顶点表示事件边表示活动事件 Vj发生表示
akj已结束ak
VjVi
事件 Vi发生表示
ak可以开始
AOE网
V2
V4
V5
V6
v0
v1
v2
v4
v3
v6
v7
v8
v5
v9
a0=8
a1=6
a2=7
a3=3
a4=10
a5=9
a6=9
a7=13
a11=2
a10=8
a9=19
a8=4
a13=14
a12=6
a14=10
关键路径求解方法：
在 AOE网中从源点 v0到事件 vi的最长路径长度是事件 vi的最早发生时间。这个时间决定了所有以 vi
为尾的弧表示的活动的最早开始时间。
定义以下几个量：
e（ i）：表示活动 ai的最早开始时间。
l（ i）：表示活动最迟开始时间的向量。
关键活动特征,e（ i） =l（ i）
l（ j） -e（ j）的值表示完成活动 aj的时间余量，提前完成非关键活动并不能提高整个工程的进度。
事件可能的最早开始时间 ve（ i）：对于某一事件
vi，它可能的最早发生时间 ve（ i）是从源点到顶点
vi的最大路径长度。
事件允许的最晚发生时间 vl（ i）：对于某一事件 vi，
它允许的最晚发生时间是在保证按时完成整个工程的前提下，该事件最晚必须发生的时间
ve（ 0） =0；
ve（ i） =
)(
)11}(,)(m a x {
ipj
nivvjve ij
持续的时间活动
vi
集合 p（ i）
对于图 8.25所示的 AOE网络,可按其中的一个拓扑序列 （ v0、
v1,v2,v4,v3,v6,v7,v5,v8,v9） 求解每个事件的最早开始时间：
ve（ 0） =0
ve（ 1） = 8,ve（ 2） =6,ve（ 4） =7；
ve（ 3） =max{ve（ 1） +len（ a3）,ve（ 2） +len（ a4） }=16；
ve（ 6） =max{ve（ 2） +len（ a5）,ve（ 4） +len（ a6） }=16；
ve（ 7） =max{ve（ 6） +len（ a11）,ve（ 4） +len（ a7） }=20；
ve（ 5） = ve（ 3） +len（ a8） =20；
ve（ 8） =max{ve（ 3） +len（ a9）,ve（ 6） +len（ a10）,ve（ 7）
+len（ a12） }=35；
ve（ 9） =max{ve（ 5） +len（ a13）,ve（ 8） +len（ a14） }=45；
e（ k） =ve（ i） ；
l（ k） =vl（ j） -len（ <vi,vj>）；
求每一个顶点 i的最晚允许发生时间 vl（ i） 可以沿图中的汇点开始,按图中的逆拓扑序逐个递推出每个顶点的 vl（ i） 。
vl（ n-1） =ve（ n-1） ；
vl（ i） =
)(
)20) } (,()(m i n {
isj
nivvl e njv jil
vi
集合 s（ i）
对于图 8.25所示的 AOE网,按照 （ 8-7） 式求得的各个事件允许的最晚发生时间如下：
vl（ 9） =ve（ 9） =45
vl（ 8） =vl（ 9） -len（ <v8,v9>） =45-10=35
vl（ 5） =vl（ 9） -len（ <v5,v9>） =45-14=31
vl（ 7） =vl（ 8） -len（ <v7,v8>） =35-6=29
vl（ 6） =min{vl（ 7） -len（ <v6,v7>）,vl（ 8） -len（ <v6，
v8>） }=min{27,27}=27
vl（ 3） =min{vl（ 5） -len（ <v3,v5>）,vl（ 8） -len（ <v3，
v8>） }=min{27,16}=16
vl（ 4） =min{vl（ 6） -len（ <v4,v6>）,vl（ 7） -len（ <v4，
v7>） }=min{18,16}=16
vl（ 2） =min{vl（ 3） -len（ <v2,v3>）,vl（ 6） -len（ <v2，
v6>） }=min{6,18}=6
vl（ 1） =vl（ 3） -len（ <v1,v3>） =13
vl（ 0） =min{vl（ 1） -8,vl（ 2） -6,vl（ 4） -7}=min{5,0，
9}=0
顶点 ve vl 活动 e l l-e 关键活动
v0
v1
v2
v3
v4
v5
v6
v7
v8
v9
0
8
6
16
7
20
16
20
35
45
0
13
6
16
16
31
27
29
35
45
a0
a1
a2
a3
a4
a5
a6
a7
a8
a9
a10
a11
a12
a13
a14
0
0
0
8
6
6
7
7
16
16
16
16
20
20
35
5
0
9
13
6
18
18
16
27
16
27
27
29
31
35
5
0
9
5
0
12
11
9
11
0
11
11
9
11
0
√
√
√
√
作业：
8-9
8-10
8-11
图的基本概念
图的基本运算
生成树与最小生成树
拓扑排序
图的基本存储结构
最短路径
关键路径
图的遍历
8.1 图的基本概念一、图的定义图是由一个非空的顶点集合和一个描述顶点之间多对多关系的边（或弧）集合组成的一种数据结构，
它可以形式化地表示为：
图＝（ V,E）
其中 V={x|x?某个数据对象集 }，它是顶点的有穷非空集合； E={（ x,y） |x,y?V}或 E={<x,y>|x，
y?V且 P（ x,y） }，它是顶点之间关系的有穷集合，
也叫做边集合,P（ x,y）表示从 x到 y的一条单向通路。
图的应用举例例 1 交通图（公路、铁路）
顶点：地点边：连接地点的公路交通图中的有单行道双行道，分别用有向边、无向边表示；
V0
V4V3
V1
V2
V0 V1
V2 V3
例 2 电路图顶点：元件边：连接元件之间的线路例 3 通讯线路图顶点：地点边：地点间的连线例 4 各种流程图如产品的生产流程图顶点：工序边：各道工序之间的顺序关系通常,也将图 G的顶点集和边集分别记为 V（ G）
和 E（ G） 。 E（ G） 可以是空集,若 E（ G） 为空,
则图 G只有顶点而没有边 。
若图 G中的每条边都是有方向的，则称 G为 有向图 。在有向图中，一条有向边是由两个顶点组成的有序对，有序对通常用尖括号表示。例如，有序对 <vi，
vj>表示一条由 vi到 vj的有向边。有向边又称为 弧,弧的始点称为 弧尾,弧的终点称为 弧头 。若图 G中的每条边都是没有方向的，则称 G为 无向图 。无向图中的边均是顶点的无序对，无序对通常用圆括号表示。
图 8-1
v1 v2
v3 v4
v1 v2
v4 v5
v3
（ a）有向图 G1（ b）无向图 G2
图 8.1（ a） 表示的是有向图 G1,该图的顶点集和边集分别为：
V（ G1） ={v1,v2,v3,v4}
E（ G1） ={<v1,v2>,<v1,v3>,<v2,v4>,<v3,v2>}
例有序对 <vi,vj>,
用以为 vi起点、以 vj为终点的有向线段表示，称为有向边或弧；
例：图 8-1
v1 v2
v3 v4
v1 v2
v4 v5
v3
（ a）有向图 G1（ b）无向图 G2
图 8.1（ b） 表示的是无向图 G2,该图的顶点集和边集分别为：
V（ G2） ={v1,v2,v3,v4,v5}
E（ G2） ={（ vl,v2）,（ v1,v3）,（ v1,v4）,
（ v2,v3）,（ v2,v5）,（ v4,v5） }
无序对 (vi,vj)：
用连接顶点 vi,vj的线段表示，称为无向边；
在以后的讨论中,我们约定：
（ 1） 一条边中涉及的两个顶点必须不相同,即：
若 （ vi,vj） 或 <vi,vj>是 E（ G） 中的一条边,则要求 vi≠vj；
（ 2） 一对顶点间不能有相同方向的两条有向边；
（ 3） 一对顶点间不能有两条无向边,即只讨论简单的图 。
若用 n表示图中顶点的数目，用 e表示图中边的数目，按照上述规定，容易得到下述结论：对于一个具有 n个顶点的无向图，其边数 e小于等于 n（ n-1）
/2，边数恰好等于 n（ n-1） /2的无向图称为 无向完全图 ；对于一个具有 n个顶点的有向图，其边数 e小于等于 n（ n-1），边数恰好等于 n（ n-1）的有向图称为 有向完全图 。也就是说完全图具有最多的边数，
任意一对顶点间均有边相连。
二、完全图例：图 8-2
v1
v2 v3
v4
v1
v2 v3
v4
（ a）无向完全图 G3（ b）有向完全图 G4
图 8.2所示的 G3与 G4分别是具有 4个顶点的无向完全图和有向完全图。图 G3共有 4个顶点 6条边；图
G4共有 4个顶点 12条边。
若（ vi,vj）是一条无向边，则称顶点 vi和 vj互为邻接点 。
若 <vi,vj>是一条有向边，则称 vi邻接到 vj,vj邻接于 vi，并称有向边 <vi,vj>关联于 vi与 vj，或称有向边 <vi,vj>与顶点 vi和 vj相关联。
三、度、入度、出度在图中，一个顶点的 度 就是与该顶点相关联的边的数目，顶点 v的度记为 D（ v）。例如在图 8.2
（ a）所示的无向图 G3中，各顶点的度均为 3。
若 G为有向图，则把以顶点 v为终点的边的数目称为顶点 v的 入度,记为 ID（ v）；把以顶点 v为始点的边的数目称为 v的 出度,记为 OD（ v），有向图中顶点的度数等于顶点的入度与出度之和，即 D
（ v） =ID（ v） +OD（ v）。
无论有向图还是无向图,图中的每条边均关联于两个顶点,因此,顶点数 n,边数 e和度数之间有如下关系：
n
i
ivD
1
)(
2
1e= ………,（式 8-1）
四、子图给定两个图 Gi和 Gj，其中 Gi=（ Vi,Ei）,Gj=
（ Vj,Ej），若满足 Vi?Vj,Ei?Ej，则称 Gi是 Gj的子图 。
v1 v2
v4
v2 v3
v4
v1
v2 v3
v4
v1
v4
v2 v3
v4
v1 v1
v3v2
v4
子图示例
（ a）无向图 G3的部分子图
（ b）有向图 G4的部分子图五、路径无向图 G中若存在着一个顶点序列 v,v1’,v2’,…,
vm’,u,且 （ v,v1’）,（ v1’,v2’）,…,（ vm’,u）
均属于 E（ G）,则称该顶点序列为顶点 v到顶点 u的一条 路径,相应地,顶点序列 u,vm’,vm-1’,…,v1’、
v是顶点 u到顶点 v的一条路径 。
如果 G是有向图,路径也是有向的,它由 E（ G）
中的有向边 <v,v1’>,<v1’,v2’>,…,<vm’,u>组成 。 路径长度 是该路径上边或弧的数目 。
如果一条路径上除了起点 v和终点 u相同外，其余顶点均不相同，则称此路径为一条 简单路径 。起点和终点相同（ v=u）的简单路径称为 简单回路 或 简单环 。
六、连通图与强连通图在无向图 G中，若从顶点 vi到顶点 vj有路径，则称 vi与 vj是连通的。若 V（ G）中任意两个不同的顶点 vi和 vj都连通（即有路径），则称 G为 连通图 。例如，图 8.1（ b）所示的无向图 G2、图 8.2（ a）所示的无向图 G3是都是连通图。
无向图 G的极大连通子图称为 G的 连通分量 。
根据连通分量的定义，可知任何连通图的连通分量是其自身，非连通的无向图有多个连通分量。
例：非连通图及其连通分量示例
（ a）非连通图 G5 （ b） G5的两个连通分量 H1和 H2
在有向图 G中，若对于 V（ G）中任意两个不同的顶点 vi和 vj，都存在从 vi到 vj以及从 vj到 vi的路径，则称
G是 强连通图。
V1 V2
V4
V5
V3
V1 V2
V4
V5
V3
有向图的极大强连通子图称为 G的强连通分量。
根据强连通图的定义，可知强连通图的唯一强连通分量是其自身，而非强连通的有向图有多个强连分量。例如，图 8.2（ b）所示的有向图 G4是一个具有
4个顶点的强连通图，图 8.5（ a）所示的有向图 G6
不是强连通图（ v2,v3,v4没有到达 v1的路径），
它的两个强连通分量 H3与 H4如图 8.5（ b）所示。
v1
v2
v3 v4
v1
v2
v3 v4
（ a）非强连通图 G6 （ b） G6的两个强连通分量 H3和 H4
七、网络有时在图的每条边上附上相关的数值，这种与图的边相关的数值叫 权 。
权可以表示两个顶点之间的距离、耗费等具有某种意义的数。若将图的每条边都赋上一个权，则称这种带权图为网络。
V0
V1 V3
V234
56 78 25
V0
V2V1 45
5064
（ a）无向网络 G7 （ b）有向网络 G8
作业：
8.1 对于无向图 8.29,试给出
（ 1） 图中每个顶点的度；
（ 2） 该图的邻接矩阵；
（ 4） 该图的连通分量 。
v0
v3 v4
v2
v1 v5 v6
图 8.29 无向图
8.2 给定有向图 8.30,试给出
（ 1） 顶点 D的入度与出度；
（ 2） 该图的出边表与入边表；
（ 3） 该图的强连通分量 。
A
B
C
D
E
图 8.30 有向图
8.2 图的基本运算图是一种复杂数据结构,由图的定义及图的一组基本操作构成了图的抽象数据类型 。
ADT Graph{
数据对象 V,V是具有相同特性的数据元素的集合,称为顶点集 。
数据关系 R：
R={<v,w>|v,w?V且 P（ v,w）,P（ v,w） 定义了边 （ 或弧 ） （ v,w） 的信息 }
图的基本操作如下：
（ 1） creatgraph（ &g） 创建一个图的存储结构 。
（ 2） insertvertex（ &g,v） 在图 g中增加一个顶点 v。
（ 3） deletevertex（ &g,v） 在图 g中删除顶点 v及所有和顶点 v相关联的边或弧 。
（ 4） insertedge（ &g,v,u） 在图 g中增加一条从顶点 v到顶点 u的边或弧 。
（ 5） deleteedge（ &g,v,u） 在图 g中删除一条从顶点 v到顶点 u的边或弧 。
（ 6） trave（ g） 遍历图 g。
（ 7） locatevertex（ g,v） 求顶点 v在图 g中的位序 。
（ 8） fiirstvertex（ g,v） 求图 g中顶点 v的第一个邻接点 。
（ 9） degree（ g,v） 求图 g中顶点 v的度数 。
（ 10） nextvertex（ g,v,w） 求图 g中与顶点 v相邻接的顶点 w的下一个邻接点 。 即求图 g中顶点 v的某个邻接点,它的存储顺序排在邻接点 w的存储位置之后 。
} ADT Graph
8.3图的基本存储结构图的存储结构至少要保存两类信息：
1)顶点的数据
2)顶点间的关系约定,
G=<V,E>是图,V={v0,v1,v2,… v n-1 },设顶点的角标为它的编号如何表示顶点间的关系？
V0
V4V3
V1
V2
V0 V1
V2 V3
8.3.1邻接矩阵及其实现给定图 G=（ V,E），其中 V（ G） ={v0,…,
vi,…,vn-1},G的邻接矩阵（ Adacency Matrix）是具有如下性质的 n阶方阵：
,
),(,,][A
否则或者如果
0
><1 EjiEjiji,
无向图的邻接矩阵是对称的，有向图的邻接矩阵可能是不对称的。
一、非网络的邻接矩阵
v0
v1 v3
v2
v3
v1
v0 v2
图的邻接矩阵示例
0 1 1 1
1 0 1 0
1 1 0 1
1 0 1 0
0 1 0 0
1 0 1 0
1 1 0 0
0 1 0 0
A1= A2=
图 8.7 无向图 G9及有向图 G10的邻接矩阵表示用邻接矩阵表示图，很容易判定任意两个顶点之间是否有边相连，并求得各个顶点的度数。对于无向图，顶点 vi的度数是邻接矩阵中第 i行或第 i列值为 1的元素个数，即：
D（ vi） = = … （ 8-2）
1
0
],[
n
j
jiA?
1
0
],[
n
j
ijA
对于有向图，邻接矩阵中第 i行值为 1的元素个数为顶点 vi的出度，第 i列值为 1的元素的个数为顶点 vi的入度，即：
OD（ vi） = ; ID（ vi） = … （ 8-3）
1
0
],[
n
j
jiA?
1
0
],[
n
j
ijA
二、网络的邻接矩阵当 G=（ V,E）是一个网络时,G的邻接矩阵是具有如下性质的 n阶方阵：
Wij 当 （ vi,vj） 或 < vi,vj >?E（ G）
0 当 （ vi,vj） 或 < vi,vj >E（ G） 且 i=j
∞ 当 （ vi,vj） 或 < vi,vj > E（ G） 且 i≠j
A[i,j]=
其中 Wij表示边上的权值； ∞表示一个计算机允许的、大于所有边上权值的数。
V0
V1 V3
V234
56 78 25
V0
V2V1 45
5064
网络的邻接矩阵示例
0 56 34 78
56 0 ∞ ∞
34 ∞ 0 25
78 ∞ 25 0
0 ∞ 50
0 ∞ 45
64 ∞ 0
A3= A4=
（ a） G7的邻接矩阵 （ b） G8的邻接矩阵图 8.8 网络邻接矩阵示例邻接矩阵存储结构
#define FINITY 5000 /*此处用 5000代表无穷大 */
#define m 20 /*最大顶点数 */
typedef char vertextype; /*顶点值类型 */
typedef int edgetype; /*权值类型 */
typedef struct{
vertextype vexs[m]; /*顶点信息域 */
edgetype edges[m][m]; /*邻接矩阵 */
int n,e; /*图中顶点总数与边数 */
} mgraph; /*邻接矩阵表示的图类型 */
文件名,mgraph.h
/*********************************************************/
/* 图的邻接矩阵创建算法 */
/* 文件名,c_ljjz.c 函数名,creatmgraph1() */
/*********************************************************/
#include <stdio.h>
#include "mgraph.h"
void creatmgraph1(mgraph *g)
{int i,j,k,w; /*建立有向网络的邻接矩阵存储结构 */
printf("please input n and e:\n");
scanf("%d%d",&g->n,&g->e); /*输入图的顶点数与边数 */
getchar(); /*取消输入的换行符 */
printf("please input vexs:\n");
for(i=0;i<g->n;i++) /*输入图中的顶点值 */
g->vexs[i]=getchar();
for(i=0;i<g->n;i++) /*初始化邻接矩阵 */
for(j=0;j<g->n;j++)
if (i==j) g->edges[i][j]=0;
else g->edges[i][j]=FINITY;
printf("please input edges:\n");
for (k=0;k<g->e;k++) /*输入网络中的边 */
{ scanf("%d%d%d",&i,&j,&w);
g->edges[i][j]=w;
/*若是建立无向网,只需在此加入语句 g->edges[j][i]=w;即可 */
} }
说明,
当建立有向网时，边信息以三元组（ i,j,w）的形式输入,i,j分别表示两顶点的序号,w表示边上的权。
对于每一条输入的边信息（ i,j,w），只需将 g-
>edges[i][j]赋值为 w。
算法 8.5中用到的 creatmgraph2()是用于建立无向网络的函数，它与 creatmgraph1()的区别在于对每一条输入的边信息（ i,j,w），需同时将 g->edges[i][j] 和
g->edges[j][i]赋值为 w。
当建立非网络的存储结构时，所有的边信息只需按二元组（ i,j）的形式输入。
8.3.2邻接表及其实现用邻接矩阵表示法存储图，占用的存储单元个数只与图中顶点的个数有关，而与边的数目无关。
一个含有 n个顶点的图，如果其边数比 n2少得多，
那么它的邻接矩阵就会有很多空元素，浪费了存储空间。
无向图的邻接表对于图 G中的每个顶点 vi，该方法把所有邻接于 vi
的顶点 vj链成一个带头结点的单链表，这个单链表就称为顶点 vi的邻接表。单链表中的每个结点至少包含两个域，一个为 邻接点域 （ adjvex），它指示与顶点 vi
邻接的顶点在图中的位序，另一个为 链域 （ next），
它指示与顶点 vi邻接的下一个结点。
adjvex nextvertex firstdege
为了便于随机访问任一顶点的邻接表，可将所有头结点顺序存储在一个向量中就构成了图的邻接表存储。最后将图的顶点数及边数等信息与邻接表放在一起来描述图的存储结构。
v0
v1 v3
v2
图 8.7 无向图 G9
1 2 3 ^
0 2 ^
0 1 3 ^
0 2 ^
V0
V1
V2
V3
图 8.9 G9的邻接表表头结点结构边结点结构对于无向图,vi的邻接表中每个表结点都对应于与 vi相关联的一条边；对于有向图来说，如果每一顶点 vi的邻接表中每个表结点都存储以 vi的为始点射出的一条边，则称这种表为有向图的 出边表 （有向图的邻接表），反之，若每一顶点 vi的邻接表中每个表结点都对应于以 vi为终点的边（即射入 vi的边），则称这种表为有向图的 入边表 （又称逆邻接表）。
v0
v1
v2
v3
1 ^
0 2 ^
0 1 ^
1 ^
G10的出边表
0
1
2
3 ^
2 ^
0 2
1 ^
3 ^
G10的入边表
v3
v1
v0 v2
图 8.7(b)有向图 G10
在无向图的邻接表中，顶点 vi的度为第 i个链表中结点的个数；而在有向图的出边表中，第 i个链表中的结点个数是顶点 vi的出度；为了求入度，必须对整个邻接表扫描一遍，所有链表中其邻接点域的值为 i
的结点的个数是顶点 vi的入度。
1 2 3 ^
0 2 ^
0 1 3 ^
0 2 ^
V0
V1
V2
V3
V0的度为 3
v0
v1
v2
v3
1 ^
0 2 ^
0 1 ^
1 ^
G10的出边表
V0的出度为
1，入度为 2
邻接表的存储结构
/****************************************************/
/* 邻接表存储结构 文件名,adjgraph.h */
/****************************************************/
#define m 20 /*预定义图的最大顶点数 */
typedef char datatype; /*顶点信息数据类型 */
typedef struct node{ /*边表结点 */
int adjvex; /*邻接点 */
struct node *next;
}edgenode; adjvex next
边结点结构
typedef struct vnode{ /*头结点类型 */
datatype vertex; /*顶点信息 */
edgenode *firstedge; /*邻接链表头指针 */
}vertexnode;
typedef struct{ /*邻接表类型 */
vertexnode adjlist [m]; /*存放头结点的顺序表 */
int n,e; /*图的顶点数与边数 */
}adjgraph;
vertex firstdege
头结点结构
/********************************************************/
/* 无向图的邻接表创建算法 */
/* 文件名 c_ljb.c 函数名,createadjgraph() */
/********************************************************/
void createadjgraph(adjgraph *g)
{ int i,j,k;
edgenode *s;
printf("Please input n and e:\n");
scanf("%d%d",&g->n,&g->e); /*输入顶点数与边数 */
getchar();
printf("Please input %d vertex:",g->n);
for(i=0;i<g->n;i++)
{scanf(“%c”,&g->adjlist[i].vertex); /*读入顶点信息 */
g->adjlist[i].firstedge=NULL; /*边表置为空表 */
}
printf("Please input %d edges:",g->e);
for(k=0;k<g->e;k++) /*循环 e次建立边表 */
{ scanf("%d%d",&i,&j); /*输入无序对 （ i,j） */
s=(edgenode *)malloc(sizeof(edgenode));
s->adjvex=j; /*邻接点序号为 j*/
s->next=g->adjlist[i].firstedge;
g->adjlist[i].firstedge=s; /*将新结点 *s插入顶点 vi
的边表头部 */
s=(edgenode *)malloc(sizeof(edgenode));
s->adjvex=i; /*邻接点序号为 i*/
s->next=g->adjlist[j].firstedge;
g->adjlist[j].firstedge=s;
/*将新结点 *s插入顶点 vj的边表头部 */
}
}
算法 8.2 建立无向图的邻接表算法说明：一个图的邻接矩阵表示是唯一的，但其邻接表表示不唯一，这是因为在邻接表结构中，各边表结点的链接次序取决于建立邻接表的算法以及边的输入次序。
4 5
ABCD
0 1 0 2 0 3 1 2 2 3
A
B D
C
例,若需建立下图所示的无向图邻接表存储结构,则在执行程序 c_ljb.c时如果输入的信息为：
则将建立如下的邻接表存储结构。
A 3-->2-->1
B 2-->0
C 3-->1-->0
D 2-->0
8.3.3邻接多重表
在邻接多重表中，每一条边只有一个边结点。为有关边的处理提供了方便。
–边结点的结构
mark vexi linki vexj linkj
其中,mark 是记录是否处理过的标记； vexi和
vexj是依附于该边的两顶点位置。 lniki域是链接指针，
指向下一条依附于顶点 vexi的边； linkj也是链接指针，
指向下一条依附于顶点 vexj的边。需要时还可设置一个存放与该边相关的权值的域 cost。
–顶点结点的结构存储顶点信息的结点表以顺序表方式组织，每一个顶点结点有两个数据成员：其中,vertex 存放与该顶点相关的信息,firstedge 是指示第一条依附于该顶点的边的指针。
在邻接多重表中,所有依附于同一个顶点的边都链接在同一个单链表中。
从顶点 i 出发,可以循链找到所有依附于该顶点的边，也可以找到它的所有邻接顶点。
vertex Firstedge
V0
V1 V3
V234
56 78 25
V0
V1
V2
V3
56 0 1 ^
34 0 2
78 0 ^ 3
25 2 ^ 3 ^
0
1
2
3
无向网络的邻接多重表示例其中边表结点增加了一个存储权值的数据域 。
8.4 图的遍历图的遍历：从图的某顶点出发，访问图中所有顶点，
并且每个顶点仅访问一次。在图中，访问部分顶点后，
可能又沿着其他边回到已被访问过的顶点。为保证每一个顶点只被访问一次，必须对顶点进行标记，一般用一个辅助数组 visit[n]作为对顶点的标记，当顶点 vi未被访问,visit[i]值为 0；当 vi已被访问，则 visit[i]值为 1。
图的遍历与树的遍历有什么不同有两种遍历方法 （ 它们对无向图，有向图都适用）
深度优先遍历
广度优先遍历
8.4.1深度优先遍历从图中某顶点 v出发：
1）访问顶点 v；
2）依次从 v的未被访问的邻接点出发，继续对图进行深度优先遍历；
对于给定的图 G=（ V,E）,首先将 V中每一个顶点都标记为未被访问,然后,选取一个源点 v?V,将 v
标记为已被访问,再递归地用深度优先搜索方法,依次搜索 v的所有邻接点 w。 若 w未曾访问过,则以 w为新的出发点继续进行深度优先遍历,如果从 v出发有路的顶点都已被访问过,则从 v的搜索过程结束 。 此时,如果图中还有未被访问过的顶点 （ 该图有多个连通分量或强连通分量 ）,则再任选一个未被访问过的顶点,并从这个顶点开始做新的搜索 。 上述过程一直进行到 V中所有顶点都已被访问过为止 。
V0
V7
V6V5V4V3
V2V1
V0
V3
V2
V6V4
例序列 1：
V0,V1,V3,V7,V4,V2,V5,V6
深度优先遍历过程：
由于没有规定访问邻接点的顺序，
深度优先序列不是唯一的序列 2：
V0,V1,V4,V7,V3,V2,V5,V6
c0
c1
c3
c2
c4
c5
c0
c1
c3
c2
c4
c5
DFS序列,c0? c1? c3? c4? c5? c2
但是，当采用邻接表存储结构并且存储结构已确定的情况下，遍历的结果将是确定的。
采用邻接表存储结构的深度优先遍历算法实现：
/*********************************************************/
/* 图的深度优先遍历算法 */
/* 文件名,dfs.c 函数名,dfs(),dfstraverse() */
/*********************************************************/
int visited[m];
void dfs(adjgraph g,int i)
{ /*以 vi为出发点深度优先遍历顶点 vi所在的连通分量 */
edgenode *p;
printf("visit vertex,%c \n",g.adjlist[i].vertex); /*访问顶点 i*/
visited[i]=1;
p=g.adjlist[i].firstedge;
while (p) /*从 p的邻接点出发进行深度优先搜索 */
{ if (!visited[p->adjvex])
dfs(g,p->adjvex); /*递归 */
p=p->next;
}
}
void dfstraverse(adjgraph g)
{ /* 深度优先遍历图 g */
int i;
for (i=0;i<g.n;i++)
visited[i]=0; /*初始化标志数组 */
for (i=0;i<g.n;i++)
if (!visited[i]) /*vi未访问过 */
dfs(g,i);
}
算法 8.3 图的深度优先遍历算法（邻接表表示法）
算法分析：
对于具有 n个顶点和 e条边的无向图或有向图，遍历算法 dfstraverse对图中每个顶点至多调用一次 dfs。
从 dfstraverse中调用 dfs或 dfs内部递归调用自己的最大次数为 n。当访问某顶点 vi时,dfs的时间主要耗费在从该顶点出发搜索它的所有邻接点上。用邻接表表示图时，需搜索第 i个边表上的所有结点，因此，对所有 n个顶点访问，在邻接表上需将边表中所有 O（ e）
个结点检查一遍。所以,dfstraverse算法的时间复杂度为 O（ n+e）。
8.4.2广度优先遍历图中某未访问过的顶点 vi出发：
1）访问顶点 vi；
2）访问 vi 的所有未被访问的邻接点 w1,w2,…w k ；
3）依次从这些邻接点出发，访问它们的所有未被访问的邻接点 ; 依此类推，直到图中所有访问过的顶点的邻接点都被访问；
V0
V7
V6V5V4V3
V2V1
V7
求图 G 的以 V0起点的的广度优先序列
V0,V1,V2,V3,V4,V5,V6,V7
例
c0
c1
c3
c2
c4
c5
从 C0出发的 BFS序列为：
由于没有规定访问邻接点的顺序，
广度优先序列不是唯一的
c0? c1? c2? c3? c4? c5
从图中某顶点 vi出发：
1）访问顶点 vi ；（容易实现）
2）访问 vi 的所有未被访问的邻接点 w1,w2,…w k ；
3）依次从这些邻接点（在步骤 2）访问的顶点）出发，访问它们的所有未被访问的邻接点 ; 依此类推，
直到图中所有访问过的顶点的邻接点都被访问；
为实现 3），需要保存在步骤 (2）中访问的顶点，而且访问这些顶点邻接点的顺序为：先保存的顶点，
其邻接点先被访问。
广度优先算法：
在广度优先遍历算法中，
需设置一队列 Q，
保存已访问的顶点，
并控制遍历顶点的顺序。
QUEUE
V0 V1 V2 V3 V4 V5 V6 V7
V1 V2 V3V0 V4 V5 V6 V7
V0
V7
V6V5V4V3
V2V1
数据结构：
1）全局标志数组
int visited[m]; /*全局标志向量 */
2）邻接表存储结构
/******************************************************/
/* 图的广度优先遍历算法 */
/* 程序名 bfs.c 函数名 bfs(),bfstraverse() */
/******************************************************/
void bfs(adjgraph g,int i)
{ int j; /*从顶点 i出发广度优先遍历顶点 i所在的连通分量 */
edgenode *p;
int queue[20],head,tail; /*FIFO队列 */
head=-1; tail=-1; /*初始化空队列 */
printf("%c ",g.adjlist[i].vertex); /*访问源点 v*/
visited[i]=1;
queue[++tail]=i; /*被访问结点进队 */
while (tail>head) /*当队列非空时,执行下列循环体 */
{ j=queue[++head]; /*出队 */
p=g.adjlist[j].firstedge;
while (p) /*广度优先搜索邻接表 */
{ if (visited[p->adjvex]==0)
{ printf("%c ",g.adjlist[p->adjvex].vertex);
queue[++tail]=p->adjvex;
visited[p->adjvex]=1;
}
p=p->next;
}
} }
int bfstraverse(adjgraph g,datatype v)
{ int i,count=0; /*广度优先遍历图 g*/
for (i=0;i<g.n;i++) visited[i]=0; /*初始化标志数组 */
i=loc(g,v); /*寻找顶点 v在邻接表中的位序 */
if (i!=-1)
{ count++; /*连通分量个数加 1*/
bfs(g,i);
}
for (i=0;i<g.n;i++)
if (!visited[i]) /*vi未访问过 */
{ printf("\n");
count++; /*连通分量个数加 1*/
bfs(g,i); /*从顶点 i出发广度优先遍历图 g*/
}
return count; /*返回无向图 g中连通分量的个数 */
}
算法 8.4 图的广度优先遍历算法（邻接表表示法）
算法的时间复杂度与深度优先算法相同。
作业：
8.4 图 8.31是某个无向图的邻接表,请
（ 1） 画出此图；
（ 2） 写出从顶点 A开始的 DFS遍历结果 。
（ 3） 写出从顶点 A开始的 BFS遍历结果 。
8.5生成树与最小生成树对于一个无向的连通图 G=（ V,E），设 G'是它的一个子图，如果 G'中包含了 G中所有的顶点
（即 V（ G'） =V（ G））且 G'是无回路的连通图，
则称 G'为 G一棵的生成树。
深度优先生成树：按深度优先遍历生成的生成树广度优先生成树：按广度优先遍历生成的生成树
c0
c1
c3
c2
c4
c5
c0
c1
c3
c2
c4
c5
有向图的生成树
c0
c1 c3c2 c4
c5 c6
c0
c1 c3c2 c4
c5 c6
c0
c1 c3c2 c4
c5 c6
（ a）以 c0为根的有向图 （ b） DFS生成树 （ c） BFS生成树非连通图的生成森林
V0 V1
V3 V4
V2 V6
V8
V7
V5
V9
V0
V1
V3 V
4
V2
V6 V
8
V7V
5
V9
V0 V1
V3 V4
V2
V8
V7
V9V6
V5
（ a）不连通的无向图 G12 （ b）图 G12的一个 DFS生成森林
（ c）图 G12的一个 BFS生成森林
8.5.1最小生成树的定义若有一个连通的无向图 G,有 n 个顶点，并且它的边是有权值的。在 G 上构造生成树 G’,使这 n-1
条边的权值之和在所有的生成树中最小 。
例要在 n 个城市间建立交通网,要考虑的问题如何在保证 n 点连通的前题下最节省经费?
),(
)(
Evu
uvwTW
A
B
C D
E F
10
10
15 12
12 8
7 6
6
5
上述问题即要使得生成树各边权值之各最小，即：
构造最小生成树的准则：
必须只使用该网络中的边来构造最小生成树；
必须使用且仅使用 n-1条边来联接网络中的 n个顶点；
不能使用产生回路的边。
假设 G=（ V,E）是一个连通网,U是顶点集 V的一个非空真子集，若（ u,v）是满足 u?U,v?V-U的边（称这种边为两栖边）且（ u,v）在所有的两栖边中具有最小的权值（此时，称（ u,v）为最小两栖边），则必存在一棵包含边（ u,v）的最小生成树。
MST性质：
证明：
u v v’
u’
U V-U
设（ u,v）是连接 U与（ V-U）之间所有边中的最小代价边（最小两栖边）。反证时假设 G中的任何一棵最小生成树都不含此最小两栖边。设 T是连通网上的一棵最小生成树，当将（ u,v）加入到 T中时，由生成树的定义,T中必存在一条包含（ u,v
）的回路。另一方面，由于 T是生成树，则在 T上必存在另一条边（ u’,v’），其中 u’? U,v’? V-
U,且 u和 u’之间,v和 v’之间均有路径相通，删去边（ u’,v’），便可消除上述回路，同时得到另一棵生成树 T’。因为（ u,v）的代价不高于（ u’,v’
），则 T’的代价亦不高于 T,T’是包含（ u,v）的一棵最小生成树。由此和假设矛盾。
普里姆算法的基本思想：
8.5.2最小生成树的普里姆算法
(Prim)算法 和 (Kruskal)算法 是两个利用 MST性质构造最小生成树的算法。
从连通网络 G = { V,E }中的某一顶点 u0 出发，选择与它关联的具有最小权值的边 (u0,v)，将其顶点加入到生成树的顶点集合 U中。
以后每一步从一个顶点在 U中，而另一个顶点不在 U中的各条边中选择权值最小的边 (u,v),把它的顶点加入到 集合 U中。如此继续下去，直到网络中的所有顶点都加入到生成树顶点集合 U中为止。
Prim算法的基本步骤如下：
（ 1） 初始化,U={u0},TREE={};
（ 2） 如果 U=V（ G）,则输出最小生成树 T,并结束算法；
（ 3） 在所有两栖边中找一条权最小的边 （ u,v）
（ 若候选两栖边中的最小边不止一条,可任选其中的一条 ）,将边 （ u,v） 加入到边集 TREE中,并将顶点 v并入集合 U中 。
（ 4） 由于新顶点的加入,U的状态发生变化,需要对 U与 V-U之间的两栖边进行调整 。
（ 5） 转步骤 （ 2）
A
B
C D
E F
10
10
15 12
12 8
7 6
6
5
（ a）无向网
5
A
B
C D
E F
10
7 6
10
（ e）选取（ B,F）
A
B
C D
E F
10
15 12
∞
∞
（ b）初始状态
5
A
B
C D
E F
10
15 7 6
（ c）选取（ A,B）
5
A
B
C D
E F
10
15 7 6
（ d）选取（ B,D）
5
A
B
C D
E F
10
7 6
10
（ f）选取（ B,C）
5
A
B
C D
E F
10
7 6
10
（ g）选取（ E,F）
Prim算法实现：
1、连通图用邻接矩阵 net表示：
edges[i][j]=
Wij 当（ vi,vj）? E（ G）且权为 Wij
否则?
0 当 i==j
2、边 tree（生成树） edge tree[n-1]
typedef struct edgedata
{ int beg,en; /*beg,en是结点序号 */
int length; /*边长 */
} edge;
beg
en
length
tree 0 1 2 3 4
0 0 0 0 0
1 2 3 4 5
10 12 ∞ 15 ∞
(a)初始态 K=0 m=1
K=0
beg
en
length
tree 0 1 2 3 4
0 0 0 0 0
1 2 3 4 5
10 12 ∞ 15 ∞
(b)最小两栖边（ 0,1）
Prim算法构造最小生成树的过程
K=1
beg
en
length
tree 0 1 2 3 4
0 1 1 0 1
1 2 3 4 5
10 7 5 15 6
(c)最小两栖边（ 0,3）
K=2
beg
en
length
tree 0 1 2 3 4
0 1 1 0 1
1 3 2 4 5
10 5 7 15 6
(d)最小两栖边（ 1,5）
K=3
beg
en
length
tree 0 1 2 3 4
0 1 1 5 1
1 3 5 4 2
10 5 6 10 7
(e)最小两栖边（ 1,2）
beg
en
length
tree 0 1 2 3 4
0 1 1 1 5
1 3 5 2 4
10 5 6 7 10
(f) tree中存储了最小生成树的边算法关键一步,求第 k条轻边，将其加入 tree中
1）求当前最小两栖边及应添加的点 v
min=tree[k].length;
s=k;
for (j=k+1;j<=g.n-2;j++)
if (tree[j].length<min)
{min=tree[j].length;
s=j;
}
v=tree[s].en; /*入选顶点为 v*/
2）通过交换，将当前轻边加入 tree中
x=tree[s]; tree[s]=tree[k]; tree[k]=x;
3）调整各剩余点对应的最小两栖边（由 v加入引起）
for (j=k+1;j<=g.n-2;j++)
{ d=g.edges[v][tree[j].en];
if (d<tree[j].length)
{ tree[j].length=d;
tree[j].beg=v;
}
}
算法总体控制：
1）初始化：建立初始入选点，并初始化生成树边集 tree。
for (v=1;v<=g.n-1;v++)
{ tree[v-1].beg=0; /* 此处从顶点 v0开始求最小生成树 */
tree[v-1].en=v;
tree[v-1].length=g.edges[0][v];
}
2）依次求当前最小两栖边，并将其加入 tree
for (k=0;k<=g.n-3;k++) 执行关键一步一般来讲，
由于普里姆算法的 时间复杂度为 O(n2)，则适于稠密图。
程序演示,prim.c
8.5.3最小生成树的克鲁斯卡尔算法
Kruskal算法基本思想：
为使生成树上边的权值之和最小，显然，其中每一条边的权值应该尽可能地小。克鲁斯卡尔算法的做法就是：先构造一个只含 n个顶点的子图 SG，
然后从权值最小的边开始，若它的添加不使 SG中产生回路，则在 SG上加上这条边，如此重复，直至加上 n-1条边为止。
克鲁斯卡尔算法需对 e条边按权值进行排序，其时间复杂度为 O(eloge)，则适于稀疏图。
算法：
（ 1） 初始化,TV={v0,v1,…,vn},TE={}；
（ 2） 如果 TE具有 n-1条边,则输出最小生成树 T，
并结束算法 。
（ 3） 在有序的 E（ G） 边表序列中,从当前位置向后寻找满足下面条件的一条边 （ u,v）,使得 u在一个连通分量上,v在另一个连通分量上,即 （ u，
v） 是满足此条件权值最小的边,将其加入到 T中,
合并 u与 v所在的两个连通分量为一个连通分量 。
（ 4） 转 （ 2）
v0
v1
v2
v3
v4 v5
6 5
15 5
4 23 6
6
(a) 无向网络图
Kruskal算法动态演示：
15
4 23
v0
v1
v2
v3
v4 v5
(b) 最小生成树求解过程
5
A
B
C D
E F
(a)
5
A
B
C D
E F
6
(b)
5
A
B
C D
E F
67
(c)
5
A
B
C D
E F
67
10
(d)
5
A
B
C D
E F
67
10
10
(e)
Kruskal算法构造最小生成树的过程
/*********************************************/
/* kruskal求解最小生成树算法 */
/* 文件名 kruskal.c 函数名 kruskal() */
/*********************************************/
void kruskal(edge adjlist[],edge tree[],int cnvx[],int n)
{ int v=0,j,k;
for (j=0;j<n;j++)
cnvx[j]=j; /* 设置每一个顶点的连通分量 */
for (k=0;k<n-1;k++) /*树中共有 n-1条边 */
{ while (cnvx[adjlist[v].beg]==cnvx[adjlist[v].en] ) v++;
/*找到属于两个连通分量权最小的边 */
tree[k]=adjlist[v]; /*将边 v加入到生成树中 */
for (j=0;j<n;j++) /*两个连通分量合并为一个连通分量 */
if (cnvx[j]==cnvx[adjlist[v].en])
cnvx[j]=cnvx[adjlist[v].beg];
v++;
}
printf("最小生成树是,\n");
for (j=0;j<n-1;j++)
printf("%3d%3d%6d\n",tree[j].beg,tree[j].en,tree[j].length);
}
算法 8.6 Kruskal求解最小生成树
8.6最短路径问题的提出：
交通咨询系统,通讯网,计算机网络常要寻找两结点间最短路径；
交通咨询系统,A到 B 最短路径；
计算机网络,发送 Email节省费用 A到 B沿最短路径传送；
路径长度：路径上边数路径上边的权值之和最短路径：两结点间权值之和最小的路径；
A
B
D
CF
E 2
4
1528
8
18
10
13
始点 终点 最短路径 路径长度
A B （ A,C,B） 19
C （ A,C） 4
D （ A,C,F,D） 25
E （ A,C,B,E） 29
F （ A,C,F） 12
4
如何求从某源点到其余各点的最短路径？
本节介绍求最短路径的两个算法
求从某个源点到其他各顶点的最短路径 （ 单源最短路径 ） 。
求每一对顶点之间的最短路径 。
8.6.1单源最短路径单源最短路径问题是指：对于给定的有向网 G=（ V，
E）,求源点 v0到其它顶点的最短路径 。
Dijkstra提出了一个按路径长度递增的顺序逐步产生最短路径的方法，称为 Dijkstra算法。
Dijkstra算法的基本思想：
把图中所有顶点分成两组,第一组 包括已确定最短路径的顶点,初始时只含有一个源点,记为集合 S；
第二组 包括尚未确定最短路径的顶点,记为 V-S。 按最短路径长度递增的顺序逐个把 V-S中的顶点加到 S中去,直至从 v0出发可以到达的所有顶点都包括到 S中 。
在这个过程中,总保持从 v0到第一组 （ S） 各顶点的最短路径都不大于从 v0到第二组 （ V-S） 的任何顶点的最短路径长度,第二组的顶点对应的距离值是从 v0到此顶点的只包括第一组 （ S） 的顶点为中间顶点的最短路径长度 。 对于 S中任意一点 j,v0到 j的路径长度皆小于 v0到 （ V-S） 中任意一点的路径长度 。
引入一个辅助数组 d[]。它的每一个分量 d[i]表示当前找到的从 源点 v0到 顶点 vi 的最短路径的长度。初始状态：
–若从源点 v0到顶点 vi有边，则 d[i]为该边上的权值
–若从源点 v0到顶点 vi 没有边，则 d[i]为 +? 。
一般情况下，假设 S 是已求得的最短路径的终点的集合，则可证明：下一条最短路径必然是从 v0 出发，中间只经过 S中的顶点便可到达的那些顶点 vx (vx?V-S
)的路径中的一条。
每次求得一条最短路径之后，其终点 vk 加入集合 S，
然后 对所有的 vi?V-S，修改其 d[i]值。
Dijkstra算法可描述如下：
１） 初始化：把图中的所有顶点分成两组；初始化源点到各点的距离向量。
S：已确定最短路径的点集，初始 S ← { v0 };
S：尚未确定最短路径的点集，初始 S ← V（ G） -V0 ;
d[j] ← g.edges[v0][j],j = 1,2,…,n-1;
// n为图中顶点个数
２） 求出 S与 S间的最短路径，及相应的点 v
d[v] ← min{ d[i] },i? V（ G） - S ;
S ← S U { v };
v0
s
vmin
s
v0
s
v
s
i
v0
s
v
min
s
３）由于 v的加入，修改 S中各结点与 S中各点的最短距离：
d[i] ← min{ d[i],d[v] + edges[v][i] },
对于每一个 i? V- S ;
４）判断,若 S = V,则算法结束，否则转２）。
iedges[v][i]
Dijkstra算法中各辅助数组的变化如何从表中读取源点 0到终点 v
的最短路径？例如顶点 A到 D的最短距离是 d[3]=25,根据 p[3] =5
→ p[5] =2 → p[2]=0，反过来排列，得到路径 0,2,5,3（即 A,C
,F,D）。
A
B
D
CF
E 2
4
1528
8
18
10
13
4
算法实现如下：
/***************************************************/
/* 单源最短路径算法 文件名,dijkstra.c */
/* 函数名,spath_dij(),print_gpd() */
/***************************************************/
#include "c_ljjz.c" /*引入邻接矩阵创建程序 */
typedef enum{FALSE,TRUE} boolean; /*false为 0,true为 1*/
typedef int dist[m]; /* 距离向量类型 */
typedef int path[m]; /* 路径向量类型 */
void spath_dij(mgraph g,int v0,path p,dist d)
{ boolean final[m];
int i,k,j,v,min,x;
/* 第 1步 初始化集合 S与距离向量 d */
for (v=0;v<g.n;v++)
{ final[v]=FALSE;
d[v]=g.edges[v0][v];
if (d[v]<FINITY && d[v]!=0) p[v]=v0; else p[v]=-1;
/* v无前驱 */
}
final[v0]=TRUE; d[v0]=0; /*初始时 s中只有 v0一个顶点 */
/* 第 2步 依次找出 n-1个结点加入 S中 */
for (i=1;i<g.n;i++)
{ min=FINITY;
for (k=0;k<g.n;++k) /*找最小边及对应的入选顶点 */
if (!final[k] && d[k]<min) {v=k;min=d[k];} /* !final[k] 表示 k还在 V-S中 */
printf("\n%c---%d\n",g.vexs[v],min); /*输出本次入选的顶点及距离 */
if (min==FINITY) return;
final[v]=TRUE; /* V加入 S*/
/*第 3步 修改 S与 V-S中各结点的距离 */
for (k=0;k<g.n;++k)
if ( !final[k] && (min+g.edges[v][k]< d[k]) )
{ d[k]=min+g.edges[v][k];
p[k]=v; }
} /* end for */
}
void print_gpd(mgraph g,path p,dist d)
{ /*输出有向图的最短路径 */
int st[20],i,pre,top=-1; /*定义栈 st并初始化空栈 */
for (i=0;i<g.n;i++)
{ printf("\nDistancd,%7d,path:",d[i]);
st[++top]=i;
pre=p[i]; /*从第 i个顶点开始向前搜索最短路径上的顶点 */
while (pre!=-1)
{ st[++top]=pre;
pre=p[pre]; }
while (top>0)
printf("%2d",st[top--]); } }
void main() /*主程序 */
{ mgraph g; /* 有向图 */
path p; /* 路径向量 */
dist d; /* 最短路径向量 */
int v0;
creatmgraph1(&g); /*创建有向网的邻接矩阵 */
print(g); /*输出图的邻接矩阵 */
printf("please input the source point v0:");
scanf("%d",&v0); /*输入源点 */
spath_dij(g,v0,p,d); /*求 v0到其他各点的最短距离 */
print_gpd(g,p,d); /*输出 V0到其它各点的路径信息及距离 */
}
8.6.2所有顶点对的最短路径
问题的提法：已知一个各边权值均大于 0的带权有向图，对每一对顶点 vi? vj，要求求出 vi 与 vj之间的最短路径和最短路径长度。
解决这个问题显然可以利用单源最短路径算法,
具体做法是依次把有向网 G中的每个顶点作为源点
,重复执行 Dijkstra算法 n次,即执行循环体,总的时间复杂度为 O(n3)。
for （ v=0； v<g.n； v++）
{ spath_dij（ g,v,p,d） ；
print_gpd（ g,p,d） ；
}
下面将介绍用弗洛伊德 (Floyd)算法来实现此功能,时间复杂度仍为 O(n3),但该方法比调用 n次迪杰斯特拉方法更直观一些。
2,弗洛伊德算法的基本思想弗洛伊德算法仍然使用前面定义的图的邻接矩阵
edges[N][N]来存储带权有向图。算法的基本思想是,
设置一个 NxN的矩阵 A[N][N]，其中除对角线的元素都等于 0外，其它元素 A[i][j]的值表示顶点 i到顶点 j的最短路径长度，运算步骤为：
开始时，以任意两个顶点之间的有向边的权值作为路径长度，没有有向边时，路径长度为 ∞，此时,A
[i][j]=edges[i][j],
以后逐步尝试在原路径中加入其它顶点作为中间顶点,如果增加中间顶点后,得到的路径比原来的路径长度减少了,则以此新路径代替原路径,修改矩阵元素 。 具体做法为：
第一步,让所有边上加入中间顶点 0,取 A[i][j]与
A[i][0]+A[0][j]中较小的值作 A[i][j]的值,
第二步,让所有边上加入中间顶点 1,取 A[i][j]与
A[i][1]+A[1][j]中较小的值,完成后得到 A[i][j] …,如此进行下去,当第 n步完成后,得到 A[i][j],即为我们所求结果,A[i][j]表示顶点 i到顶点 j的最短距离 。
因此,弗洛伊德算法可以描述为,
A(-1)[i][j]=edges[i][j]; /*edges为图的邻接矩阵 */
A(k+1)[i][j]=min{Ak [i][j],Ak [i][k+1]+Ak [k+1][j]}
其中 k=-1,1,2,…,n-2
下面给出 Floyd的算法实现 。
/*************************************************/
/* Floyd 所有顶点对最短路径算法 */
/* 文件名,floyd.c 函数名,floyd1() */
/*************************************************/
typedef int dist[m][m]; /* 距离向量 */
typedef int path[m][m]; /* 路径向量 */
void floyd1(mgraph g,path p,dist d)
{ int i,j,k;
for (i=0;i<g.n;i++) /*初始化 */
for (j=0;j<g.n;j++)
{ d[i][j]=g.edges[i][j];
if (i!=j && d[i][j]<FINITY ) p[i][j]=i; else p[i][j]=-1;
}
for (k=0;k<g.n;k++) /*递推求解每一对顶点间的最短距离 */
{ for (i=0;i<g.n;i++)
for (j=0;j<g.n;j++)
if (d[i][j]>(d[i][k]+d[k][j]))
{ d[i][j]=d[i][k]+d[k][j];
p[i][j]=k;
}
}
}
算法 8.8 求网络中每一对顶点之间的最短路径
2
0
3
1
6
8
3 5 9
1
4
2
0 1 ∞ 4
∞ 0 9 2
3 5 0 8
∞ ∞ 6 0
例求下图中所在顶点对之间的最短路径。
D D-1 D0 D1 D2 D3
0 1 2 3 0 1 2 3 0 1 2 3 0 1 2 3 0 1 2 3
0 0 1 ∞ 4 0 1 ∞ 4 0 1 10 3 0 1 10 3 0 1 9 3
1 ∞ 0 9 2 ∞ 0 9 2 ∞ 0 9 2 12 0 9 2 11 0 8 2
2 3 5 0 8 3 4 0 7 3 4 0 6 3 4 0 6 3 4 0 6
3 ∞ ∞ 6 0 ∞ ∞ 6 0 ∞ ∞ 6 0 9 10 6 0 9 10 6 0
P P-1 P0 P1 P2 P30 1 2 3 0 1 2 3 0 1 2 3 0 1 2 3 0 1 2 3
0 1 0 -1 0 -1 0 -1 0 -1 0 1 1 -1 0 1 1 -1 0 3 1
1 -1 -1 1 1 -1 -1 1 1 -1 -1 1 1 2 -1 1 1 3 -1 3 1
2 2 2 -1 2 2 0 -1 0 2 0 -1 1 2 0 -1 1 2 0 -1 1
3 -1 -1 3 -1 -1 -1 3 -1 -1 -1 3 -1 2 2 3 -1 2 2 3 -1
8.7 拓扑排序有向无环图：没有回路的有向图某工程可分为 7个子工程，若用顶点表示子工程（
也称活动）,用弧表示子工程间的顺序关系。工程流程可用如下 AOV网表示
AOV网 ( activity on vertex net )
用顶点表示活动，边表示活动的顺序关系的有向图称为 AOV网。
应用,工程流程、生产过程中各道工序的流程、程序流程、课程的流程。
一 AOV网对工程问题，人们至少关心如下两类问题：
1）工程能否顺序进行，即工程流程是否“合理”？
2）完成整项工程至少需要多少时间，哪些子工程是影响工程进度的关键子工程？
二 AOV网与拓扑排序
拓扑排序
V5V3
V2
V0
V1 V4 V6
例 1 某工程可分为 V0,V1,V2,V3,V4,V5,V6 7
个子工程,工程流程可用如下 AOV网表示。其中顶点
：表示子工程（也称活动）,弧：表示子工程间的顺序关系。
为求解工程流程是否“合理”，通常用 AOV网的有向图表示工程流程。
V5V3
V2
V0
V1 V4 V6
例 课程流程图某校计算机专业课程流程可 AOV网表示。其中顶点：
表示课程（也称活动）,弧：表示课程间的先修关系；
课程代号 课程名称先修课程
C0
C1
C2
C3
C4
C5
C6
C7
C8
高等数学信息技术基础离散数学数据结构程序设计语言编译原理操作系统电子线路基础计算机组成原理无无
C0,C1
C2,C4
C1
C3,C4
C3,C8
C0
C7
C0
C2
C1
C7 C8 C6
C3
C4 C5
如何安排施工计划？
如何安排教学计划？
两个可行的学习计划为：
C0?C1?C2?C4?C7?C8?C3?C6?C5
和
C1?C0?C7?C8?C2?C4?C3?C5?C6
可行的计划的特点：若在流程图中顶点 v是顶点
u 的前趋，则在计划序列中顶点 v 也是 u的前趋。
拓扑序列,有向图 D的一个顶点序列称作一个拓扑序列，如果该序列中任两顶点 v,u,若在 D中 v是 u前趋，则在序列中 v也是 u前趋。
拓扑排序,就是将有向图中顶点排成拓扑序列。
拓扑排序的应用
安排施工计划
判断工程流程的是否合理如何判断 AOV网（有向图）
是否存在有向回路？ AOV网（有向图）
不存在有向回路当且仅当能对 AOV网进行拓扑排序
1) 输入 AOV网络。令 n 为顶点个数。
2) 在 AOV网络中选一个没有直接前驱（入度为 0）
的顶点,并输出之 ;
3) 从图中删去该顶点,同时删去所有它发出的有向边 ;
4) 重复以上 (2),(3)步,直到
–全部顶点均已输出，拓扑有序序列形成，拓扑排序完成；或
–图中还有未输出的顶点，但已跳出处理循环。
这说明图中还剩下一些顶点，它们都有直接前驱，再也找不到没有前驱的顶点了。这时 AOV
网络中必定存在有向环。
拓扑排序过程拓扑排序的过程
C0 C1 C2
C3 C4 C5
(a) 有向无环图
C1 C2
C5C3
(c) 输出顶点 C0
C0 C2
C5
C1
C3
(d) 输出顶点 C3
C0 C1 C2
C3 C4 C5
(b) 输出 C4
C1 C2
C5
(e) 输出顶点 C2
C5
C1
(f) 输出顶点 C1
C5
(g) 输出顶点 C5
最后得到的拓扑有序序列为 C4,C0,C3,C2,
C1,C5 。它满足图中给出的所有前驱和后继关系，
对于本来没有这种关系的顶点，如 C4和 C2，也排出了先后次序关系。
(h) 拓扑排序完成
AOV网络及其邻接表表示
C0
C1
C2
C3 0
C4
C5 0
0
1
2
3
4
5
id data firstedge
1
3
0
1
0
3
1
adjvex nxet
3 0
5
1 5 0
0 1 5 0
C0 C1 C2
C3 C4 C5
这种带入度的邻接表存储结构定义如下：
#define m 20
typedef char vertextype;
typedef struct node{ /*边结点类型定义 */
int adjvex;
struct node *next;
}edgenode;
typedef struct de /*带顶点入度的头结点定义 */
{ edgenode* firstedge;
vertextype vertex;
int id; /*顶点的入度域 */
}vertexnode;
typedef struct{ /*AOV网络的邻接表结构 */
vertexnode adjlist[m];
int n,e;
}aovgraph;
基于这种存储结构,拓扑排序算法可描述为算法 8.9。
/*************************************************/
/* 拓扑排序算法 */
/* 文件名,topsort.c 函数名,topsort() */
/*************************************************/
int topsort(aovgraph g) /*函数返回拓扑排序输出的顶点个数 */
{int k=0,i,j,v,flag[m];
int queue[m]; /*队列 */
int h=0,t=0;
edgenode* p;
for (i=0;i<g.n;i++) flag[i]=0; /*访问标记初始化 */
for(i=0;i<g.n;i++) /*先将所有入度为 0的顶点进队 */
if( g.adjlist[i].id==0 && flag[i]==0)
{ queue[++t]=i;flag[i]=1; }
while (h<t) /*当队列不空时 */
{ v=queue[++h]; /*队首元出队 */
printf("%c----->",g.adjlist[v].vertex);
k++; /*计数器加 1*/
p=g.adjlist[v].firstedge;
while(p) /*将所有与 v邻接的顶点的入度减 1*/
{ j=p->adjvex;
if (--g.adjlist[j].id==0 && flag[j]==0)
/*若入度为 0则将其进队 */
{queue[++t]=j; flag[j]=1;}
p=p->next;
}
}
return k;
}
算法 8.9 拓扑排序
8.8 关键路径
如果在无有向环的带权有向图中
– 用有向边表示一个工程中的活动 (Activity)
– 用边上权值表示活动持续时间 (Duration)
– 用顶点表示事件 (Event)
则这样的有向图叫做用边表示活动的网络，简称
AOE (Activity On Edges) 网络。
AOE网络在某些工程估算方面非常有用。例如，
可以使人们了解：
(1) 完成整个工程至少需要多少时间 (假设网络中没有环 )?
(2) 为缩短完成工程所需的时间,应当加快哪些活动?
在 AOE网络中,有些活动顺序进行，有些活动并行进行。
从源点到各个顶点，以至从源点到汇点的有向路径可能不止一条。这些路径的长度也可能不同。完成不同路径的活动所需的时间虽然不同，但只有各条路径上所有活动都完成了，整个工程才算完成。
因此，完成整个工程所需的时间取决于从源点到汇点的最长路径长度，即在这条路径上所有活动的持续时间之和。 这条路径长度最长的路径就叫做关键路径 (Critical Path)。
要找出关键路径，必须找出关键活动，即不按期完成就会影响整个工程完成的活动。
关键路径上的所有活动都是关键活动。因此，只要找到了关键活动，就可以找到关键路径,
例如，下图就是一个 AOE网 。
V3
V1
a4=3
a1=3
a2=2 a6=3a5=4
a3=2 a7=2
a8=1
顶点表示事件边表示活动事件 Vj发生表示
akj已结束ak
VjVi
事件 Vi发生表示
ak可以开始
AOE网
V2
V4
V5
V6
v0
v1
v2
v4
v3
v6
v7
v8
v5
v9
a0=8
a1=6
a2=7
a3=3
a4=10
a5=9
a6=9
a7=13
a11=2
a10=8
a9=19
a8=4
a13=14
a12=6
a14=10
关键路径求解方法：
在 AOE网中从源点 v0到事件 vi的最长路径长度是事件 vi的最早发生时间。这个时间决定了所有以 vi
为尾的弧表示的活动的最早开始时间。
定义以下几个量：
e（ i）：表示活动 ai的最早开始时间。
l（ i）：表示活动最迟开始时间的向量。
关键活动特征,e（ i） =l（ i）
l（ j） -e（ j）的值表示完成活动 aj的时间余量，提前完成非关键活动并不能提高整个工程的进度。
事件可能的最早开始时间 ve（ i）：对于某一事件
vi，它可能的最早发生时间 ve（ i）是从源点到顶点
vi的最大路径长度。
事件允许的最晚发生时间 vl（ i）：对于某一事件 vi，
它允许的最晚发生时间是在保证按时完成整个工程的前提下，该事件最晚必须发生的时间
ve（ 0） =0；
ve（ i） =
)(
)11}(,)(m a x {
ipj
nivvjve ij
持续的时间活动
vi
集合 p（ i）
对于图 8.25所示的 AOE网络,可按其中的一个拓扑序列 （ v0、
v1,v2,v4,v3,v6,v7,v5,v8,v9） 求解每个事件的最早开始时间：
ve（ 0） =0
ve（ 1） = 8,ve（ 2） =6,ve（ 4） =7；
ve（ 3） =max{ve（ 1） +len（ a3）,ve（ 2） +len（ a4） }=16；
ve（ 6） =max{ve（ 2） +len（ a5）,ve（ 4） +len（ a6） }=16；
ve（ 7） =max{ve（ 6） +len（ a11）,ve（ 4） +len（ a7） }=20；
ve（ 5） = ve（ 3） +len（ a8） =20；
ve（ 8） =max{ve（ 3） +len（ a9）,ve（ 6） +len（ a10）,ve（ 7）
+len（ a12） }=35；
ve（ 9） =max{ve（ 5） +len（ a13）,ve（ 8） +len（ a14） }=45；
e（ k） =ve（ i） ；
l（ k） =vl（ j） -len（ <vi,vj>）；
求每一个顶点 i的最晚允许发生时间 vl（ i） 可以沿图中的汇点开始,按图中的逆拓扑序逐个递推出每个顶点的 vl（ i） 。
vl（ n-1） =ve（ n-1） ；
vl（ i） =
)(
)20) } (,()(m i n {
isj
nivvl e njv jil
vi
集合 s（ i）
对于图 8.25所示的 AOE网,按照 （ 8-7） 式求得的各个事件允许的最晚发生时间如下：
vl（ 9） =ve（ 9） =45
vl（ 8） =vl（ 9） -len（ <v8,v9>） =45-10=35
vl（ 5） =vl（ 9） -len（ <v5,v9>） =45-14=31
vl（ 7） =vl（ 8） -len（ <v7,v8>） =35-6=29
vl（ 6） =min{vl（ 7） -len（ <v6,v7>）,vl（ 8） -len（ <v6，
v8>） }=min{27,27}=27
vl（ 3） =min{vl（ 5） -len（ <v3,v5>）,vl（ 8） -len（ <v3，
v8>） }=min{27,16}=16
vl（ 4） =min{vl（ 6） -len（ <v4,v6>）,vl（ 7） -len（ <v4，
v7>） }=min{18,16}=16
vl（ 2） =min{vl（ 3） -len（ <v2,v3>）,vl（ 6） -len（ <v2，
v6>） }=min{6,18}=6
vl（ 1） =vl（ 3） -len（ <v1,v3>） =13
vl（ 0） =min{vl（ 1） -8,vl（ 2） -6,vl（ 4） -7}=min{5,0，
9}=0
顶点 ve vl 活动 e l l-e 关键活动
v0
v1
v2
v3
v4
v5
v6
v7
v8
v9
0
8
6
16
7
20
16
20
35
45
0
13
6
16
16
31
27
29
35
45
a0
a1
a2
a3
a4
a5
a6
a7
a8
a9
a10
a11
a12
a13
a14
0
0
0
8
6
6
7
7
16
16
16
16
20
20
35
5
0
9
13
6
18
18
16
27
16
27
27
29
31
35
5
0
9
5
0
12
11
9
11
0
11
11
9
11
0
√
√
√
√
作业：
8-9
8-10
8-11
