武汉理工大学华夏学院 -信息工程系图状结构是一种比树形结构更复杂的非线性结构，其特点是图中的每一个结点可以有任意个前驱和任意个后继。通常使用的图状结构有四种形式：有向图、无向图、有向网络图和无向网络图。
6.１ 基本术语
１,图的定义数据结构 B=(K,R)称为图是指,K是结点的有限集合,R是结点偶对的有限集合。 (习惯上，
将图中的结点又称为顶点,结点偶对又称为边 )
第六章 图结构武汉理工大学华夏学院 -信息工程系对于一个图，若图中的顶点偶对是有序的，
则这样的边称为有向边，由有向边构成的图称为有向图。
２,有向边与有向图例如,G1=(V,E)中,V={A,B,C,D}组成，
E={<A,B>,<A,C>,<C,B>,<B,D>,<A,D>,<D,C>}
组成，就构成了一个有向图。其中边用 <X,Y>形式表示，在图示法中用带箭头的线绘出，其逻辑结构的图形表示如图 6-1 (a)所示。
武汉理工大学华夏学院 -信息工程系图 6－１（ｂ）无向图图 6－１图的逻辑结构示意图
A
B
A
D
C
图 6－１（ a） 有向图
B D
C
武汉理工大学华夏学院 -信息工程系对于一个图，若图中的顶点偶对是无序的，
则这样的边称为无向边，由无向边构成的图称为无向图。
例如,G２ =(V２,E２ )中,V２ ={A,B,C,D}组成，
E２ ={(A,B),(A,C),(B,C),(A,D),(D,C),(D,B)}
组成，就构成了一个无向图。其中边用（ X,Y）
形式表示，在图示法中用不带箭头的线绘出。
其逻辑结构的图形表示如图 6-1（ｂ）所示。
３,无向边与无向图武汉理工大学华夏学院 -信息工程系若在一个有ｎ个顶点的图中，每一个顶点都与其余的ｎ－１个顶点有边相连，则这种结构的图称为完全图。显然，有向完全图应有 n(n-1)条边，无向完全图有ｎ (ｎ－１ )/２条边。
４,完全图
５,无向图的顶点的度在无向图中，若 (ａ，ｂ )为图中的一条边，
则称ａ与ｂ是相邻顶点，边（ａ，ｂ）与顶点ａ
和ｂ是相关联的。顶点ａ相关联的边的条数称为顶点ａ的度。例如图 6－１（ｂ）的无向图中每一个顶点的度都是３（它是一个无向完全图）。
武汉理工大学华夏学院 -信息工程系在有向图中,若 <ａ,ｂ >为图中的一条边,则称顶点ａ邻接到顶点ｂ,顶点ｂ邻接于顶点ａ，
边 <ａ,ｂ >与顶点ａ和ｂ是相关联的。
邻接于ａ的顶点个数称为ａ顶点的出度；邻接到ｂ的顶点个数称为顶点 b的入度；顶点ａ的出度与入度之和称为顶点ａ的度。
简单地说：某个顶点的入度就是进入该顶点的边的条数 (前驱数）某个顶点的出度就是离开该顶点的边的条数（后继数）
６,有向图的顶点的出度、入度和度武汉理工大学华夏学院 -信息工程系顶点 出度 入度 度
A 3 1 4
B 2 1 3
C 0 3 3
D 1 1 2
例如图 6－１（ａ）的有向图中各顶点的出度、入度和度为,
７,子图设有两个图 G=(V,E) 和 G1=(V1,E1) 如果图 G1
中的所有边 E1都包含在图 G的边的集合 E中，且图
G1中的所有顶点 V1都包含在图 G的顶点的集合 V中，
则称图 G1为图 G的子图。图 6-2中 G为一个图的逻辑结构，而图 G1,G2为 G的子图，显然任何一个图的子图可以子图可以有多个。
武汉理工大学华夏学院 -信息工程系
A
D B
C
A
D B
C图 6－２（ａ）无向图 G 图 6－２（ｂ）子图１
图 6－２（ｃ）子图２
图 6－２（ｄ）子图３图 6－２无向图的部分子图
A
D
C
武汉理工大学华夏学院 -信息工程系
８,路径与路径长度对于一个图来说，从图中的某一个顶点ｘ
到任意一个顶点ｙ的路径是一个顶点序列ｘ,
ｘ 1,ｘ ２,…,ｙ,但对于无向图而言，该序列应满足,（ XI-1,XI）应包含在 E集合中 ;而对于有向图,该序列应满足：
（ｘ i－ 1，ｘ ｊ ）应包含在 E集合中。
在路径上的边的条数称为路径长度。路径上的第一个顶点与最后一个顶点相同时，称为该图有回路。
武汉理工大学华夏学院 -信息工程系
９,连通图与连通分量在无向图中若顶点ｘ到顶点ｙ有路径，则称
ｘ与ｙ是连通的；图中的任意两个顶点都是连通的无向图称为连通图。在无向图中的最大的连通子图称为无向图的连通分量。
如图 6-3 所示。
武汉理工大学华夏学院 -信息工程系
2
1
4
1
3
6
2 5
2 51
3 4
图 6－３（ａ）连通图 图 6－３（ｂ）非连通图图 6－３（ｃ）非连通图的连通分量图 6－３无向图的连通性示意
3 4
6
武汉理工大学华夏学院 -信息工程系
10,有根图 在有向图中，若存在一个顶点 G，
从该顶点出发，可以沿着有向路径到达图中其余的所有顶点，则称该图为有根图，顶点 G为有根图的根。例如：图 6-4为一个有根图。
11.权与网络 当图中的每一条边都对应着一个数值，这个数值称为该边的权，在实际应用中可以用权来表示距离、造价等；对这种每条边上都带有权值的图称为网络。
例如：图 6-5表示了一个网络图 。
武汉理工大学华夏学院 -信息工程系
A
D B
C
树根图 6－４有根图
A
D B
C 72
84
9
图 6－ 5网络图武汉理工大学华夏学院 -信息工程系
6.2 图的存储表示图的存储表示方法有很多，例如用存储树的方法可以存储图，这里只介绍两种常用方法。
6.２,１ 邻接矩阵邻接矩阵是用来表示图中顶点之间的邻接关系的矩阵。
一、定义：对于有 N个顶点的图的邻接矩阵是一个 N× N的方阵 C,其中 C[I,J]（ 0<I,J<=N)的值是这样确定的：
当顶点 I对顶点 J有边相连时 C[I,J]的值为１，
当顶点 I对顶点 J无边相连时 C[I,J]的值为０。
武汉理工大学华夏学院 -信息工程系上图的邻接矩阵为
A B C D 出度
A 0 1 1 1 ３
B 1 0 1 0 ２
C 0 0 0 0 ０
D 0 0 1 0 １
１ １ ３ １ 入度
A
D
C
B
例如,图 6-1（ａ） 所示的有向图的邻接矩阵为：
武汉理工大学华夏学院 -信息工程系上图所示的无向图的邻接矩阵为：
A B C D
A 0 1 1 1
B 1 0 1 1
C 1 1 0 1
D 1 1 1 0
很显然，这是一个对称阵。
A
BD
C
武汉理工大学华夏学院 -信息工程系二、特点,从上例中可以看出：无向图的邻接矩阵是一个对称阵。有向图的邻接矩阵中，
各行的和代表了该行表示的顶点的出度，各列的和代表了该列表示的顶点的入度。
三、带权的邻接矩阵（耗费矩阵） 对于网络图来说，其邻接矩阵定义为,对于有 N个顶点的图的邻接矩阵是一个 N× N的方阵 C,其中
C[I,J]的值是这样确定的：当顶点 I对顶点 J
有边相连时 C[I,J]等于该边上的权值ｗ ｉｊ,
当顶点 I对顶点 J无边相连时，若 I等于 J,则
C[I,J]的值为０；若 I不等于 J,则 C[I,J]的值为无穷大。
武汉理工大学华夏学院 -信息工程系上图所示的网络图的耗费矩阵为：
A B C D
A 0 8 9 4
B ～ 0 7 ～
C ～ ～ 0 ～
D ～ ～ 2 0
A
D B
C 72
84
9
武汉理工大学华夏学院 -信息工程系
6.２,２ 邻接表邻接表是表示顶点之间的相邻关系的ｎ个单向链表。（ｎ为图中顶点的个数）邻接表由两部分组成：
其一 为表头部分，用来存放各顶点的数据值，
又称为顶点表；
其二 为链表部分，用来存放相邻顶点的地址。
又称边表武汉理工大学华夏学院 -信息工程系在 邻接表中，采用顶点的编号表示顶点表头部分包括两部分内容：用来存放顶点的名称和相关数据（ data） 和指向表结点的指针
(* firstarc)
链表部分包括三部分内容：邻接顶点编号
(adjvex)； 指向下一个边的指针 (*nextarc)；
数据域或权 (weight)；
表结点 头结点
adjvex nextarc weight data firstarc
武汉理工大学华夏学院 -信息工程系邻接表的特点一、无向图的邻接表表示对于第ｉ个链表中的每一个结点表示一条与顶点
ｉ相关联的边，结点中包含有两个字段其一为为相邻顶点的地址，其二为下一条与ｉ相关联的边。
二、有向图的邻接表表示有向图的邻接表分为只保存“出边”的邻接表和只保存“入边”的邻接表（也称为逆邻接表）两种。
邻接表是：对于第ｉ个链表中的每一个结点表示邻接于顶点ｉ的某个顶点在顶点表中的存放位置。
逆邻接表是：对于第ｉ个链表中的每一个结点表示邻接到顶点ｉ的某个顶点在顶点表中的存放位置。
武汉理工大学华夏学院 -信息工程系邻接表的性质
1、图的邻接表表示不唯一；
2、无向图的邻接表中第 I个边表中结点的个数为第 I个顶点的度；
3,有向图的邻接表中第 I个边表中结点的个数为第 I个顶点的出度；
有向图的逆邻接表中第 I个边表中结点的个数为第 I个顶点的入度；
4、无向图的边数等于无向图的邻接表中边表结点的个数的一半、有向图的弧数等于有向图的邻接表中边表结点的 数目；（或逆邻接表中入边表结点的 数目）
武汉理工大学华夏学院 -信息工程系
6.２,３建立图的存储结构图的存储结构是用算法来实现的。下面给出建立网络图的邻接矩阵和邻接表的算法。
一、算法中的变量单元分配二维数组ａｄｊｍ表示邻接矩阵；
一维数组ａｄｊｌ表示邻接表中的顶点表；
整型变量ｎ表示网络图中的顶点个数；
常量 n0是数组的最大下标。
在邻接表存储结构中：
顶点表中的每个元素包含有两个字段：
ｄｅｇｒｅｅ 字段：表示无向网络图中的顶点的度或有向网络图中的顶点的入度。
Ｆｉｒｓｔ 字段：表示指针，指向链表中的第一个结点 。
武汉理工大学华夏学院 -信息工程系二、算法思想通过输入一系列表示边的三元组（ｉ，ｊ，ｗ）来建立网络的存储结构。其中ｉ，ｊ为顶点的序号，ｗ
为ｉ，ｊ边上的权值。
每输入一个三元组，就建一个结点，链接到链表中，
当输入的两个顶点序号超出顶点个数ｎ时，输入结束。
链表中的每个结点包含三个字段：
ｖｅｒｔｅｘ 字段表示相邻顶点的序号；
ｗｅｉｇｈｔ 字段表示边上的权值；
next字段表示指针，指向链表中的下一个结点的地址。
武汉理工大学华夏学院 -信息工程系三、邻接矩阵的建立算法
const int n0=100;
// 定义一个大数表示无穷 //
const int infinity=32767;
int adjm[n0+1][n0+1];
int n ;
void set()
{
int I,j,k,w ;
cout<<“顶点数：,
cin >> n;
// 邻接矩阵初始化 //
for ( I=1 ; I<=n ; I++)
{
for j=1 ; j<=n ; j++ )
adjm[I][j] = infinity ;
adjm[I][I] = 0 ;
}
cout<<“请输入边的集合,\n” ;
cout<<“（ 始点 终点 权值） \n” ;
//读入第一条边
cin >>I>>j>>w ;
while (( I>=1)&&(I<=n)&&(j>=1)&&(j<=n))
{
adjm[I][j]=w;
//读入下一条边
cin >>I>>j>>w ;
｝
｝
武汉理工大学华夏学院 -信息工程系四、邻接表的建立算法
const int n0=100; // 定义一个大数表示无穷 //
const int infinity=32767;
struct arcnode{ /*表结点的定义 */
int adjvex; /*邻接点编号 */
struct arcnode *nextarc;
int weighx;
} ; ARCNODE,*ARCNODEPTR;
struct vnode{ /*头结点的类型 */
int data ;
ARCNODE *firstarc;
}VNODE,ADJLIST[N] ;
（ 详见教材 187页 ）?
武汉理工大学华夏学院 -信息工程系
scanf(“%d“,&(*g ).net;
printf(“1:无向网或图 (0) 2:有向网或图 (1)\n” )
scanf(“%d“,&(*g ).digraph;
void set(ALGRAPH *g)
{
int i,j,k,weight;
ARCNODE *p ;
printf(“请输入图的顶点数和边数 \n” )；
scanf(“%d,%d”,&(*g).vexnum,&(*g).arcnum);
for ( i=0 ; i< (*g).vexnum; i++)
{(*g).vertices[i].data=i;
(*g).vertices[i].firstarc=NULL;}
printf(“选择 1:图 (0) 2,网 (1)\n” )
武汉理工大学华夏学院 -信息工程系
p=(ARCNODEPTR)malloc(LEN) ;
P->adjvex=j;
p->nextarc= (*g).vertices[i].firstarc;
(*g).vertices[i].firstarc= p ;
if(!( (*g).net)) p-> weight=0;
else p-> weight= weight;
for(k=0;k< (*g).arcnum;k++)
{ if (!( (*g).net))
{ printf(“请输入边的端点的顶点编号 ) ;
scanf(“%d,%d”,&i,&j);
}
else
{ printf(“请输入边的端点的顶点编号及权 ) ;
scanf(“%d,%d”,&i,&j,&weight);
}
武汉理工大学华夏学院 -信息工程系
if(!( (*g).digraph))
p=(ARCNODEPTR)malloc(LEN) ;
P->adjvex=i;
p->nextarc= (*g).vertices[j].firstarc;
(*g).vertices[j].firstarc= p ;
if(!( (*g).net)) p-> weight=0;
else
p-> weight= weight;
}
}
}
武汉理工大学华夏学院 -信息工程系
6.3 图的遍历和生成树
6.３,１ 图的遍历的概念一、定义,从图中的任意一个顶点出发，对图中的所有顶点访问一次并仅访问一次的操作过程，
称为图的遍历二、遍历方法,通常有两种，即深度优先搜索法遍历图和宽（广）度先搜索法遍历图，简称深度遍历和宽（广）度遍历。
武汉理工大学华夏学院 -信息工程系三、与二叉树的遍历的异同二叉树的遍历有三种方法：前序、中序和后序遍历法，图的遍历只有两种方法：深度优先和广度优先遍历法；
二叉树的遍历必须从树根入手进行，而图的遍历可以从图中任一点开始；
二叉树的遍历结果是形成一个唯一的结点序列，而图的遍历结果是可以形成多个结点序 。
武汉理工大学华夏学院 -信息工程系
6.３,２ 深度优先搜索遍历一、深度遍历的思想
1,任选一个顶点 Vｉ 作为起始点进行访；
2,访问完起始点后，依次从邻接于 Vi的未被访问的顶点中选出一个顶点进行深度遍历，
直到 Vi的所有可能达到的顶点都访问完为止；
3,若图中还有未被访问的顶点，则从中又任选一个作起始点,重复上述过程,直到所有顶点被访问完为止。
武汉理工大学华夏学院 -信息工程系二、实例如图 6-6（ A） 所示的无向图，作深度遍历后形成的序列为：
A,B,C,F,E,D,H,G,I
或者 A,G,I,F,H,C,B,D,E
图 6-6（ A） 无向图的遍历实例
A
B G
DC H I
E
F
武汉理工大学华夏学院 -信息工程系如图 6-6（ B） 所示的有向图，作深度遍历后形成的序列为：
A,B,C,D 或者 A,C,B,D 或者
A,C,D,B
图 6-6（ B） 有向图的遍历实例
CB
A D
武汉理工大学华夏学院 -信息工程系三、深度遍历非递归算法思想
1,设置一个标志数组 MARK,用来表示顶点是否被访问过，当 MARK[I]=0时，表示 VI未被访问；当 MARK[I]=1时，
表示 VI已被访问过。
2,用邻接表存储图。
3,选定起始点，输出并将起始点置已访问标志。
4,将起始点进栈。
5,当栈不空时，重复进行：
取栈顶元素；判取栈顶元素有否未被访问的相邻顶点；
有，则选取一个输出、置标志、进栈； 若无，则退栈
6,直至栈空结束。
武汉理工大学华夏学院 -信息工程系
6.３,3 广度遍历一、广度遍历的思想
1,任选一个顶点 Vｉ 作为起始点进行访问；
2,访问完起始点后，依次访问邻接于 Vi的所有未被访问的顶点；
3,再从邻接于这些顶点中选出一个未被访问的顶点进行广度遍历,直到 Vi的所有可能达到的顶点都访问完为止；
4,若图中还有未被访问的顶点，则从中又任选一个作起始点，重复上述过程,直到所有顶点被访问完为止。
武汉理工大学华夏学院 -信息工程系二、实例如图 6-6（ A） 所示的无向图，作深度遍历后形成的序列为：
A,B,G,C,D,H,I,F,E
或者 A,G,B,I,H,D,C,F,E
如图 6-6（ B） 所示的有向图，作深度遍历后形成的序列为：
A,B,C,D 或者 A,C,B,D
武汉理工大学华夏学院 -信息工程系三、广度遍历非递归算法思想
1,设置一个标志数组 MARK,用来表示顶点是否被访问过,MARK[I]=0时，表示 V 被访问；当 MARK[I]=1时，
表示 VI已被访问过。
2,用邻接表存储图。
3,选定起始点，输出并将起始点置已访问标志。
4,将起始点进队。
5,当队不空时，重复进行：
取队首元素 输出、置标志、将未被访问的相邻顶点进队；队首元素出队；
6,直至队空结束。
武汉理工大学华夏学院 -信息工程系
6.3.3 图的遍历算法一、算法中的变量单元分配
ｎ 顶点个数
ｍ 图中边的条数
ｓ 数组，用作栈区
ｔ 栈指针
ｑ 数组，用作队列，
ｆ 和 ｒ 分别表示队首指针和队尾指针
ｍａｒｋ 为标志位数组
x 起始点序号武汉理工大学华夏学院 -信息工程系二,深度遍历算法设：要遍历的图已经用邻接表存储好，其深度遍历算法如下：
void dfs( int x) {
int mark[n0+1],k ;
int s[n0+1],t ;
arcnode *p ;
for (k=1 ; k<=n ; k++ ) mark[k] = 0 ;
printf(“\n%d”,x) ;
mark[x] = 1 ; t=1 ; s[1] = x ;
do { k= s[t] ; p=g.vetices[k],firstarc ;
武汉理工大学华夏学院 -信息工程系
while (p && mark[ p->vertex] )
p=p->next ;
if (p==NULL ) t -- ;
else
{
x= p ->adjvex ;
printf(“%d”,x) ;
mark[x] = 1 ;
s[++ t ] = x ;
}
} while (t ) ; }
武汉理工大学华夏学院 -信息工程系三、广度遍历算法设：要遍历的图已经用邻接表存储好，
其深度遍历算法如下,
void bfs( int x)
{ int mark[n0+1],k ;
int q[n0+1],f,r ; arcnode *p ;
for (k=1 ; k<=n ; k++ ) mark[k] = 0 ;
printf(“%d”,x) ;
mark[x] = 1 ;
f=1 ; r = 2 ; q[1] = x ;
武汉理工大学华夏学院 -信息工程系
do {
k= q [ f++ ] ;
p=adjl[k],First ;
while (p )
x=p->vertex ;
if ( mark [ x ] ==0)
{printf(“%d”,x) ;
mark [ x ] = 1 ;
q [ r++ ] = x ;
} p= p ->next ; }
} while (f !=r ) ; }
武汉理工大学华夏学院 -信息工程系
6.3.4 生成树和生成森林一、图的生成树的定义对于无向连通图，可以从任意一个顶点出发进行深度或广度遍历,将图中的所有顶点访问到；或对于有根有向图，可以从根出发进行深度或广度遍历将图中的所有顶点访问到。这时将遍历图时经过的边与图中所有顶点构成了一个原图的子图，这个子图称为图的生成树。
通常，把按深度遍历得到的树称为图的深度优先生成树；把按广度遍历得到的树称为图的广度优先生成树。
武汉理工大学华夏学院 -信息工程系例如 图 6-6（ A）所示的无向图的生成树为图
6-７所示。
二、图的生成树的特点
1.图的生成树是一个顶点数为最多（与图的顶点数ｎ相等 ),边数为最少 (仅有ｎ－１ )的原图的子图。
2.生成树是一个连通但无回路的子图，任意连接生成树中的两个顶点就会形成回路。
武汉理工大学华夏学院 -信息工程系
A
B G
DC H I
E
F
A
B G
DC H I
E
F
H
A
B G
DC I
E
F
深度优先生成树 广度优先生成树图 6－７无向图的生成树示意给定的一个无向图武汉理工大学华夏学院 -信息工程系三、非连通图的生成森林由于从非连通图的任意一点出发，不能把图中的所有顶点访问到，因此整个遍历过程结束时，将得到以各起始顶点为树根的多个树，
称其为生成森林。
四、深度优先生成树算法
１．变量存储单元分配同 6.３,３算法说明
２．算法武汉理工大学华夏学院 -信息工程系
void dfstree ( int x)
{
int mark[n0+1],k ;
int s[n0+1],t ;
arcnode *p ;
for (k=1 ; k<=n ; k++ ) mark[k] = 0 ;
mark[x] = 1 ;
t=1 ; s[1] = x ;
武汉理工大学华夏学院 -信息工程系
do { k= s[t] ;
p=adjl[k],First ;
while (p&& mark[ p->vertex] )
p=p->next ;
if (p==NULL ) t -- ;
else
{ x= p ->vertex ;
printf(“%d”,x) ;
mark[x] = 1 ; s[++ t ] = x ;
} } while (t ) ; }
武汉理工大学华夏学院 -信息工程系
6.4最小生成树
6．４．１ 概念一、最小生成树的定义对于一个连通无向网络图来说，从不同的顶点出发，可以形成多棵形状各异的生成树，
这些树中，各边的权值之和为最小的生成树，
称之为最小价值生成树亦称最小生成树。
图 6-7表示了一个连通网络图及其生成树和最小生成树。
武汉理工大学华夏学院 -信息工程系
５
６ ３
５
６
１６
６
１８
１９
１１
１４
２１
３３
连通无向网络图
１
５ ４
６ ３
５
１６
６
１８
１１
价值为５６的最小生成树
６ ３
５
６
１６
１８
１１
价值为５６的最小生成树
５
２
４
６ ３
５
６
１１
１４
２１
３３
价值为８７的生成树图 6－７无向网络图及其生成树
１ ２
４
２
１
５
２
４
１
武汉理工大学华夏学院 -信息工程系二、最小生成树的用途具有ｎ个顶点的无向网络图可以表示表示规划中的公路网或者局域网、城域网，顶点代表城市或站点，边上的权值表示了修公路或架电缆所需的造价，
这样，要将整个网络连通如何使造价最低？这就是用最小生成树来解决的问题。
武汉理工大学华夏学院 -信息工程系三、连通无向网络图的最小生成树的构造如何构造连通无向网络图的最小生成树，ｐｒｉｍ（普里姆）于１９５７年提出了一个简便方法。
１,原理 按权值长度不减原则，将顶点和边加到不断扩充的顶点和边的集合中
２,做法 首先从ｎ个顶点中任选一个顶点ｖ ｘ 加入到原来为空的生成树的集合中；当生成树的集合中的顶点数少于ｎ个时，重复以下步骤：
选取一条权值最小的边，使其一个顶点在生成树的顶点集合内，而另一个顶点不再生成树的顶点集合内；
将选取的这条边及其相关联的未在生成树的集合中的顶点添加到生成树的集合中直到生成树中的顶点数有
ｎ个时为止。
具体操作过程见图 6－８ 所示。
武汉理工大学华夏学院 -信息工程系
１
６ ３
５
６
１６
６
１８
１９
１１
１４
２１
３３
连通无向网络图
１ 选取一个结点添加到树中
１ １６
１
３
５
１６
重复执行选点过程
１ ２
４
３
５
６
１
４
３
５
６６
１１
４
３
５
６６
１１
１８
图 6－８构造最小生成树的过程
５
１
５
２
４
２
２
２
２
武汉理工大学华夏学院 -信息工程系四、算法步骤
１．辅助变量单元说明两个辅助数组,lowcost和 closest，其中 lowcost数组记录各顶点到生成树的最近距离：若顶点ｖ ｉ 已进入生成树的顶点集合中则 lowcost[I]=0,否则 lowcost[I]等于边（ｖ ｊ,ｖ ｉ ）的权值，其中ｊ＝ closest [ｉ ]。
２．具体做法先 将 closest数组中的各元素值都置为０,lowcost数组中的各元素按下列规则赋值：若（ｖ ｘ,ｖ ｉ ）是边，
则 lowcost [ｉ ] 的值为这条边的权值；若（ｖ ｊ,ｖ ｉ ）
不是边，且ｖ ｊ 不等于ｖ ｉ 则给 lowcost[ｉ ] 赋值为一个充分大的数，并令 lowcost [ｘ ]＝０；
武汉理工大学华夏学院 -信息工程系再做,每次从 lowcost数组中选取一个大于０的最小数，
例如 lowcost[ｉ ]，将 lowcost[ｉ ]置为０（即将ｉ顶点放入生成树中），然后检查 lowcost 数组中所有值都大于
０的元素 lowcost ［ｋ］,若 lowcost［ｋ］的值大于边（ｖ ｉ,ｖ ｋ ）的权值ｗ，则将 lowcost［ｋ］的值改为ｗ，并将 closest［ｋ］的值改为ｉ；
最后,当ｎ 个顶点全部进入生成树后，构造过程就结束，此时 lowcost 数组的各元素的值均为０，生成树的
ｎ－１条边都记录在 closest数组中了。
图 6－９记录了图 6－８形成的生成树的 lowcost与
closest数组的ｂｉａｎｈｕａ情况。
武汉理工大学华夏学院 -信息工程系
Ｌｏｗｃｏｓｔ数组的每一步变化
０
１６
～
～
１９
２１
０
０
５
６
１９
１１
０
０
０
６
１９
１１
０
０
０
０
１８
１１
０
０
０
０
１８
０
１
１
１
１
１
１
Ｃｌｏｓｅｓｔ数组的每一步变化
１
１
２
２
１
２
１
１
２
２
１
２
１
１
２
２
４
２
０
０
０
０
０
０
１
１
２
２
４
２
１
１
２
２
４
２
图 6－９最小生成树生成过程
１ ２ ３ ４ ５ ６
X=1为始点武汉理工大学华夏学院 -信息工程系五、具体算法
１．用邻接矩阵存储连通无向网络图，并已存储好
const int n0=100;
const int infinity=1.0e20 ; // 定义一个大数表示无穷 //
float adjm[n0+1][n0+1];
int n ;
void set()
{
int I,j,k,w ;
cout<<“顶点数：,
cin >> n; // 邻接矩阵初始化 //
武汉理工大学华夏学院 -信息工程系
for ( I=1 ; I<=n ; I++)
{
for j=1 ; j<=n ; j++ )
adjm[I][j] = infinity ;
adjm[I][I] = 0 ;
}
cout<<“请输入边的集合,\n” ;
cout<<“（ 始点 终点 权值） \n” ;
cin >>I>>j>>w ; //读入第一条边 //
while (( I>=1)&&(I<=n)&&(j>=1)&&(j<=n))
{
adjm[I][j]=w;
cin >>I>>j>>w ; //读入下一条边 //
｝
｝
武汉理工大学华夏学院 -信息工程系
２．Ｐｒｉｍ算法描述为
void prim( int x)
{
int I,j,k,closest[n0+1] ;
float min,lowcost[n0+1] ;
for ( j=1 ; j <= n ; j++ )
{
lowcost [ j ] = adjm [x ] [j] ;
closest [ j ] = x ;
}
for ( j=2 ; j<= n ; j++ )
{
min=infinity ;
for ( k=1 ; k <= n ; k++ )
if (( lowcost [ k ] < min ) && (lowcost [k ]!= 0 ))
{
min = lowcost [ k ] ;
I = k ;
}
武汉理工大学华夏学院 -信息工程系
lowcost [ I ] = 0 ;
for ( k=1 ; k <= n ; k++ )
if ( lowcost [ k ] > adjm [ k ][ I ]
{
lowcost [ k ]= adjm [ k ][ I ] ;
closest [ k ] = I ;
}
}
for ( j=1 ; j<= n ; j++ )
if ( j != closest [ j ] )
cout <<“(,<< j <<“,”<< closest [ j ] <<“)” ;
}
武汉理工大学华夏学院 -信息工程系
6.5最短路径一、最短路径的概念在网络图中从图中某个顶点ｖ ｘ 出发到达图中另一个顶点ｖ ｉ,一般有很多条路径（直接的或间接的），其中路径中各条边的权值之和为最小的路径,称为最短路径。
Ｖ ｘ 称为该条路径的源点，ｖ ｉ 称为路径的终点。例如：
下图中，从点１到点３有两条路：
一条为直接路径是从１到３，
另一条间接路径是从１经过２
到３，而最短路径为第二条，
路径长度为５。３２
２ ６
３
１
武汉理工大学华夏学院 -信息工程系二,单源最短路径
１．定义 在网络图中，求从指定源点到其余各顶点的最短路径问题，称为单源最短路径问题。
２．作用 将一个网络图看成一个城市间的交通运输网，每一个顶点代表一个城市，每一条边代表两城市之间的公路，边上的权值代表了公路的里程数，这样单源最短路径就可以解决：从某一个城市出发，能否到达另一个指定城市？若有多条路径，走哪一条路最近？
３．求法 Dijkstra 提出了一个解决此问题的简单方法，即：按最短路径长度值由小到大的次序，逐步求得每一条最短路径。
图 6－ 10 给出了求最短路径的实例。
武汉理工大学华夏学院 -信息工程系
２
６
８
１２
４５
１０
４０
１２
１５
３０
２５
１５
７ １７
３０
２０
３５
以ｖ１为源点，依次求,
第一步：ｖ１到ｖ４，长度为１２；
第二步：ｖ１到ｖ５，长度为２５；
第三步：ｖ１经ｖ４到ｖ７，长度为３２ ；
第四步：ｖ１经ｖ５到ｖ２，长度为４０；
第五步：ｖ１经ｖ４到ｖ６，长度为４２；
第六步：ｖ１经ｖ４经ｖ７到ｖ３，长度为５０；
图 6－１０最短路径解题示意
１
４ ３
５
武汉理工大学华夏学院 -信息工程系
4,算法设计
A,变量单元分配有向网络图用耗费矩阵 adjm存储；
ｖ ｘ 表示源点，则 １＜＝ｘ＜＝ｎ
辅助数组,dist,path和 mark，其中：
Dist 记录从源点到顶点ｉ的,当前最短路径”的路径长度值；
Path 记录从源点到顶点ｉ的“当前最短的”路径上倒数第 2个顶点的序号；
Mark 记录从源点到顶点ｉ 的最短路径是否确定,若
mark［ ｉ］＝１表示已确定，若 mark[i]=０表示尚未确定。
武汉理工大学华夏学院 -信息工程系
B,实施步骤首先，对三个数组赋值,令 m a r k［ ｘ］＝１；
mark［ｉ］＝０（ｉ＜＞ｘ） ；对所有的ｉ，令 dist［ｉ］
＝ｗ ｘｉ ； path［ｉ］＝ｘ
然后，重复执行下列过程：
从 mark［ｉ］＝ 0的顶点中选取一个距离源点ｖ ｘ
最近的顶点ｖ ｋ,将 mark［ｋ］置为１；
检查 mark［ｉ］＝ ０ 中的所有顶点距离源点ｖ ｘ
的路径长度，是否是通过ｖ ｋ 后使其路径缩短，若是，
则用短路径对原路径进行修正；
直到所有的顶点的 mark［ｉ］＝１为止。
C,具体算法 见实验 5
武汉理工大学华夏学院 -信息工程系
6.6 拓扑排序一、有关概念
1,拓扑序列 设图 G为一个有 n个顶点的有向图,G中 n
个顶点可以构成多个线性序列；若线性序列中的各顶点满足在原图中有序（如边 <x,y>表示 x在前,y在后）时，
在线性序列中仍然有序（即序列中 x一定在 y的前面），
对于满足这种条件的序列就称为拓扑序列。
2,拓扑排序 形成拓扑序列的过程称为拓扑排序。
3,AOV网 对于一个无回路的有向图，可以用来表示一个有多项活动的工程计划，每一个顶点表示一项活动，
活动之间有一种先后关系（用有向边表示），当所有活动完成后，工程就全部完成。这种顶点代表活动的网，
称为 AOV网。
武汉理工大学华夏学院 -信息工程系例如：某专业学生学习该专业的课程，
结业后方能获得毕业文凭，这就是一项工程。学习一门课程，就是一项活动，活动有先后次序（如：学完高等数学才能学工程数学），则制定教学计划时就要将所学各课程构成一个
AOV网，再进行拓扑排序，最后分学期实施。
武汉理工大学华夏学院 -信息工程系二,拓扑排序的步骤设有向图中顶点的个数为 n，
当 n>1时，重复进行：
1,任选一个入度为零（无前件）的顶点 x；
2,输出并从图中删除该顶点 x；
3,将与顶点 x相邻接的顶点的入度减一例如：图 6-11说明对 AOV网进行拓扑排序的过程注意,当在进行拓扑排序过程中，若找不到入度为零的顶点且拓扑序列中结点的个数少于 n
时，说明图中存在有回路，拓扑排序不能进行。
武汉理工大学华夏学院 -信息工程系
2
3 4
5 6
2
3 4
6
AOV网 输出 5后
2
3 4
6
输出 1后
2
4
6
输出 3后
2
6
输出 4后
6
选 2 输出形成的拓扑序列为,5,1,3,4,2,6
图 6-11AOV网及拓扑排序过程
11
武汉理工大学华夏学院 -信息工程系三、拓扑排序算法设计
１,辅助变量单元说明设置一个栈区 S[N0+1]用来将检测入度为零的顶点送入栈中，避免重复检测，
栈指针为 T=0。 用邻接表来存储 AOV网，并在顶点表 adjlist中的每一个元素，增设一个存放入度的字段 degree,初始时存放各顶点的入度，并检测其值为零时,将该顶点送入栈 s中。
武汉理工大学华夏学院 -信息工程系
２．具体算法
void toposort ()
{
int s[n0+1],t=0 ;
int I,j ;
arcnode *p ;
for (I=1 ; I <= n ; I++)
if (adjlist [I].degree==0)
s[++t] =I;
//*查找入度为零的顶点，进栈 *//
while (t )
{
I=s [t--] ;
//* 出栈输出并处理相邻顶点的入度 *//
printf(“%d”,I);
while (p )
{
j=p->vertex ;
adjlist[j ].degree -- ;
if ( adjlist [j ].degree ==0 )
s [++t] = j ;
p = p->next ;
}
}
}
武汉理工大学华夏学院 -信息工程系
6.7 关键路径一、有关概念
1,源点、汇点 在一个无回路的有向网络中，仅存在着一个入度为零的顶点，该顶点称为源点（又称为始点）；也仅存在着一个出度为零的顶点，该顶点称为汇点（又称为收点）。
2,关键路径 从源点开始到汇点结束的多条路径中的最长的一条路，称为关键路径。
3,AOE网 对于一个无回路的有向网络图，可以用来表示一个有多项活动的工程计划，每一个顶点表示一个事件，每一条边代表一项活动，边上的权值代表完成该活动所需的时间，当所有活动完成后，工程就全部完成。这种边表示活动的网，称为 AOE网。
武汉理工大学华夏学院 -信息工程系例如：要建造一栋楼房，从奠基（源点）
开始到交付使用（汇点）需要打地基、
砌墙、粉刷、按门窗、装水电煤气管道等活动，且每一项活动都要有一定时间才能做完，但有些活动可以同时进行，
而有些活动必须有先后次序，例如打地基时可以备砖，但砌墙开始时一定是地基全部打好。将该工程可以用 AOE网表示出来。见图 6-12 显然，该网中从源点到汇点共有五条路，但只有一条路径最长的，它是 1-3-4-7-9-10，长度为 21。
武汉理工大学华夏学院 -信息工程系
1
3
2 4
7 9 10
5 8
6
a2=6
a3=3
a4=6
a5=3 A10=4
a8=4
a6=2
a7=1
a9=5
a12=4
a11=2
a13=2
a1=5
图 6-12 AOE网武汉理工大学华夏学院 -信息工程系二,AOE网研究的问题确定完成整个工程需要多少时间；哪些活动是影响工程进度的关键，如何提前完成整项工程，很明显，从理论上讲，这是求关键路径和关键活动问题。
4,关键活动和非关键活动 在 AOE网中，组成关键路径的边称为关键活动，不在关键路径上的边称为非关键活动。
武汉理工大学华夏学院 -信息工程系三、求关键路径引入的相关量
1,对事件 Vi 而言
（ 1) 事件 Vi 的可能的最早发生时间 VE(i）
它是从源点 V1开始到顶点 Vi的最长路径。
(2) 事件 Vi 的可能的最晚发生时间 VL(i）
它是从源点 Vn开始到顶点 Vi的反向最长路径，
即 VL（ I)＝ VE ( n ）－ 汇点 Vn到顶点 Vi的最长路径。对图 6-12 而言，各顶点的最早发生时间和最晚发生时间见下表。
武汉理工大学华夏学院 -信息工程系
1 0 0 0
2 5 21-16=9 4
3 6 21-15=6 0
4 12 21-9=12 0
5 9 21-8=13 4
6 16 21-4=17 1
7 14 21-7=14 0
8 13 21-4=17 4
9 19 21-2=19 0
10 21 21-0=21 0
顶点 I VE（ I) VL(I) | VE(I)-VL(I) |
显然,VE(I)与 VL(I)相等的事件就是关键事件武汉理工大学华夏学院 -信息工程系
2,对活动 ai 而言设 活动 ai 的起点是 vj,终点是 vk,表示为 <VJ,Vk>,权值为 wjk
（ 1) 活动 ai 的最早发生时间 E(i） 它是活动的起点 Vj 的可能的最早发生时间 VE(J),即
E(I)=VE(J)。
(2) 活动 ai 的最晚发生时间 L(i） 它是活动的终点 Vk 的可能的最晚开始时间减该活动边上的权值 wjk,即 L（ I)＝ VL(K)-wjk 。
武汉理工大学华夏学院 -信息工程系
1 < 1,2 > 5 0 9 -5 = 4
2 < 1,3 > 6 0 6 -6 = 0
3 < 2,4 > 3 5 12-3 =9
4 < 3,4 > 6 6 12-6 =6
5 < 3,5 > 3 6 13-3=10
6 < 4,7 > 2 12 14-2=12
7 < 5,7 > 1 9 14-1=13
8 < 4,6 > 4 12 17-4=13
9 < 7,9 > 5 14 19-5=14
10 < 5,8 > 4 9 17-4=13
11 < 8,9 > 2 13 19-2=17
12 < 6,10 > 4 16 21-4=17
13 < 9,10 > 2 19 21-2=19
对图 6-12而言，各事件的最早开始时间和最晚开始时间见下表。
活动 ai 边 <VJ,Vk> 权值 wjk E(I) L(I)
武汉理工大学华夏学院 -信息工程系显然,E(I)=L(I)的活动为关键活动，本例的关键活动为
a2,a4,a6,a9,a13 。
对于 E(I)<>L(I)的活动称为非关键活动,L(I)-E(I)的值称为松弛时间（即可以略为延时一点而不影响工期的时间）。
三、关键路径计算算法设计
１．辅助变量单元说明设置数组 E[1..N]和 L[1..N]用来各顶点的可能的最早发生时间和最晚发生时间，用数组 S 表示两个迎面增长的栈，入度为零的顶点的序号构成第一个栈，栈指针为
T1； 每次输出的顶点的序号构成第二个栈,栈指针为 T2，
用邻接表来存储 AOE网。
武汉理工大学华夏学院 -信息工程系
２．具体算法
void criticalpath()
{
flot E[n0+1],L[n0+1] ;
int s[n0+1],t1=-1,t2=n0+1 ;
int I,j ;
arcnode *p ;
for (I=1 ; I <= n ; I++) E[I] =0 ;
s[++t] =I; / /*查找入度为零的顶点，进栈 *//
while (t 1 > -1 )
{
I=s [t--] ;
s[--t2]=I ;
p= adjlist[I].first ;
while (p )
武汉理工大学华夏学院 -信息工程系
{
j=p->vertex ;
adjlist[j ].degree -- ;
if ( adjlist [j ].degree ==0 )
s [++t1] = j ;
if ( E[j]< E[I] + p ->weight )
E[j]=E[I]+p->weight ;
p = p->next ;
}
}
for ( I=1 ; I <= n ; I++ ) L[I]=E[n] ;
while (t2< n0+1)
{
I=s[t2++] ;
p= adjlist[I].first ;
while (p )
武汉理工大学华夏学院 -信息工程系
{
j=p->vertex ;
if ( L[i]> L[j] - p ->weight )
L[i]=L[j]-p->weight ;
p = p->next ;
}
}
for ( I=1 ; I <= n ; I++)
{
p= adjlist[I].first ;
while (p )
{
j=p->vertex ;
if ( L[j]== E[i] + p ->weight )
cout <<“<“I<<“,”<<j<<“>” ;
p = p->next ;
}
}
}
武汉理工大学华夏学院 -信息工程系作业讲解（ P215）
6.5题对下图给出邻接矩阵、邻接表、逆邻接表
邻接矩阵为,0 1 1 1
0 0 1 0
1 0 0 1
0 1 0 0
邻接表为,逆邻接表为：
2 a
b
c
d
4 ^3
3 ^
4 ^1
2 ^
3 ^a
b
c
d
1
2 ^1
1
4 ^
3 ^
a
c
b d
武汉理工大学华夏学院 -信息工程系作业讲解（ P215）
6.7题对下图给出邻接矩阵、邻接表、
邻接矩阵为,0 1 1 1 0 0
1 0 0 0 1 0
1 0 0 1 1 0
0 0 1 0 1 1
0 1 1 1 0 1
0 0 0 1 1 0
邻接表为：
2 v1
v2
v3
v4
4 ^3
1
41
3
v1 v2
v3
v4 v5
v6
v5
v6
42
5
5 ^
5 ^
5 6 ^
3 6 ^
4 ^
武汉理工大学华夏学院 -信息工程系
6.15 对于下图求最小生成树
1
3
2 4
5
6
40
50
30
100
5
90
80
15
32
45
1
3
2 4
5
6
4
2
1
3
Kruskai方法
6
prim方法
4
6
4
6
5
2 4
5
6
1
4
2
3
5
3
2 4
5
6
6
3
2 4
5
61
武汉理工大学华夏学院 -信息工程系
6.16 求最短路径求 1号点到其余各点的最短路径?
4
6
5
3
2
1
154
28
15
10 20
10
10
4
选点 路径 中转点
3 15 1
2 15+4 3
5 19+10＝ 19 2
6 19+4＝ 23 2
4 23+8 6
顶点 直达路径
2 20
3 15
4 9999
5 9999
6 9999
武汉理工大学华夏学院 -信息工程系
6.17 对于给定的 AOE网求关键路径?
1
5
3
2
8
7
4
9
6
10
A1＝ 8
A2＝ 6
A3＝ 7
A4＝ 3
A5＝ 10
A6＝ 9
A7＝ 9
A8＝ 13
A9＝ 4
A10＝ 19
A11＝ 8
A12＝ 2
A13＝ 6
A14＝ 14
A15＝ 10
vi Ve(i) Vl(i)1 0 0
2 8 13
3 6 6
4 16 16
5 7 16
6 20 31
7 16 27
8 20 29
9 35 35
10 45 45
Ve(i) － Vl(i)0
5
0
0
9
31
27
29
35
45
11
11
9
0
0
1 0 0
2 8 13
3 6 6
4 16 16
5 7 16
6 20 31
7 16 27
8 20 29
9 35 35
10 45 45
－
0
5
0
0
9
31
27
29
35
45
11
11
9
0
0
1 3
4
A2＝ 6
A5＝ 10
9
10
关键路径为
A10＝ 19
A15＝ 10
注意：
ve(i)=源点到 I点的最长路径
vl(i)=ve(汇点 )-汇点到 I点的最长路径武汉理工大学华夏学院 -信息工程系
vi Ve(i) Vl(i)
1 0 0
2 8 13
3 6 6
4 16 16
5 7 16
6 20 31
7 16 27
8 20 29
9 35 35
10 45 45
Ve(i) － Vl(i)
0
5
0
0
9
31
27
29
35
45
11
11
9
0
0
按事件分析 按事件分析 按活动分析
ai e(i) l(i)
1 0 5
2 0 0
3 0 9
4 8 13
5 6 6
6 6 7
7 7 18
8 7 16
9 16 27
10 16 16
e(i) － l(i)
5
0
9
5
0
31
27
29
35
45
1
11
9
13
0
<VJ,VK> WJK
1,2 8
1,3 6
1,5 7
2,4 3
3,4 10
3,7 9
5,7 9
5,8 13
4,6 4
4,9 19
11 16 17
12 16 27
13 20 29
14 20 25
15 35 35
1
31
27
29
35
11
9
5
0
7,9 8
7,8 2
8,9 6
6,10 14
9,10 10
注意：
e(i)=ve(j)
l(i)=vl(k)-wjk
6.１ 基本术语
１,图的定义数据结构 B=(K,R)称为图是指,K是结点的有限集合,R是结点偶对的有限集合。 (习惯上，
将图中的结点又称为顶点,结点偶对又称为边 )
第六章 图结构武汉理工大学华夏学院 -信息工程系对于一个图，若图中的顶点偶对是有序的，
则这样的边称为有向边，由有向边构成的图称为有向图。
２,有向边与有向图例如,G1=(V,E)中,V={A,B,C,D}组成，
E={<A,B>,<A,C>,<C,B>,<B,D>,<A,D>,<D,C>}
组成，就构成了一个有向图。其中边用 <X,Y>形式表示，在图示法中用带箭头的线绘出，其逻辑结构的图形表示如图 6-1 (a)所示。
武汉理工大学华夏学院 -信息工程系图 6－１（ｂ）无向图图 6－１图的逻辑结构示意图
A
B
A
D
C
图 6－１（ a） 有向图
B D
C
武汉理工大学华夏学院 -信息工程系对于一个图，若图中的顶点偶对是无序的，
则这样的边称为无向边，由无向边构成的图称为无向图。
例如,G２ =(V２,E２ )中,V２ ={A,B,C,D}组成，
E２ ={(A,B),(A,C),(B,C),(A,D),(D,C),(D,B)}
组成，就构成了一个无向图。其中边用（ X,Y）
形式表示，在图示法中用不带箭头的线绘出。
其逻辑结构的图形表示如图 6-1（ｂ）所示。
３,无向边与无向图武汉理工大学华夏学院 -信息工程系若在一个有ｎ个顶点的图中，每一个顶点都与其余的ｎ－１个顶点有边相连，则这种结构的图称为完全图。显然，有向完全图应有 n(n-1)条边，无向完全图有ｎ (ｎ－１ )/２条边。
４,完全图
５,无向图的顶点的度在无向图中，若 (ａ，ｂ )为图中的一条边，
则称ａ与ｂ是相邻顶点，边（ａ，ｂ）与顶点ａ
和ｂ是相关联的。顶点ａ相关联的边的条数称为顶点ａ的度。例如图 6－１（ｂ）的无向图中每一个顶点的度都是３（它是一个无向完全图）。
武汉理工大学华夏学院 -信息工程系在有向图中,若 <ａ,ｂ >为图中的一条边,则称顶点ａ邻接到顶点ｂ,顶点ｂ邻接于顶点ａ，
边 <ａ,ｂ >与顶点ａ和ｂ是相关联的。
邻接于ａ的顶点个数称为ａ顶点的出度；邻接到ｂ的顶点个数称为顶点 b的入度；顶点ａ的出度与入度之和称为顶点ａ的度。
简单地说：某个顶点的入度就是进入该顶点的边的条数 (前驱数）某个顶点的出度就是离开该顶点的边的条数（后继数）
６,有向图的顶点的出度、入度和度武汉理工大学华夏学院 -信息工程系顶点 出度 入度 度
A 3 1 4
B 2 1 3
C 0 3 3
D 1 1 2
例如图 6－１（ａ）的有向图中各顶点的出度、入度和度为,
７,子图设有两个图 G=(V,E) 和 G1=(V1,E1) 如果图 G1
中的所有边 E1都包含在图 G的边的集合 E中，且图
G1中的所有顶点 V1都包含在图 G的顶点的集合 V中，
则称图 G1为图 G的子图。图 6-2中 G为一个图的逻辑结构，而图 G1,G2为 G的子图，显然任何一个图的子图可以子图可以有多个。
武汉理工大学华夏学院 -信息工程系
A
D B
C
A
D B
C图 6－２（ａ）无向图 G 图 6－２（ｂ）子图１
图 6－２（ｃ）子图２
图 6－２（ｄ）子图３图 6－２无向图的部分子图
A
D
C
武汉理工大学华夏学院 -信息工程系
８,路径与路径长度对于一个图来说，从图中的某一个顶点ｘ
到任意一个顶点ｙ的路径是一个顶点序列ｘ,
ｘ 1,ｘ ２,…,ｙ,但对于无向图而言，该序列应满足,（ XI-1,XI）应包含在 E集合中 ;而对于有向图,该序列应满足：
（ｘ i－ 1，ｘ ｊ ）应包含在 E集合中。
在路径上的边的条数称为路径长度。路径上的第一个顶点与最后一个顶点相同时，称为该图有回路。
武汉理工大学华夏学院 -信息工程系
９,连通图与连通分量在无向图中若顶点ｘ到顶点ｙ有路径，则称
ｘ与ｙ是连通的；图中的任意两个顶点都是连通的无向图称为连通图。在无向图中的最大的连通子图称为无向图的连通分量。
如图 6-3 所示。
武汉理工大学华夏学院 -信息工程系
2
1
4
1
3
6
2 5
2 51
3 4
图 6－３（ａ）连通图 图 6－３（ｂ）非连通图图 6－３（ｃ）非连通图的连通分量图 6－３无向图的连通性示意
3 4
6
武汉理工大学华夏学院 -信息工程系
10,有根图 在有向图中，若存在一个顶点 G，
从该顶点出发，可以沿着有向路径到达图中其余的所有顶点，则称该图为有根图，顶点 G为有根图的根。例如：图 6-4为一个有根图。
11.权与网络 当图中的每一条边都对应着一个数值，这个数值称为该边的权，在实际应用中可以用权来表示距离、造价等；对这种每条边上都带有权值的图称为网络。
例如：图 6-5表示了一个网络图 。
武汉理工大学华夏学院 -信息工程系
A
D B
C
树根图 6－４有根图
A
D B
C 72
84
9
图 6－ 5网络图武汉理工大学华夏学院 -信息工程系
6.2 图的存储表示图的存储表示方法有很多，例如用存储树的方法可以存储图，这里只介绍两种常用方法。
6.２,１ 邻接矩阵邻接矩阵是用来表示图中顶点之间的邻接关系的矩阵。
一、定义：对于有 N个顶点的图的邻接矩阵是一个 N× N的方阵 C,其中 C[I,J]（ 0<I,J<=N)的值是这样确定的：
当顶点 I对顶点 J有边相连时 C[I,J]的值为１，
当顶点 I对顶点 J无边相连时 C[I,J]的值为０。
武汉理工大学华夏学院 -信息工程系上图的邻接矩阵为
A B C D 出度
A 0 1 1 1 ３
B 1 0 1 0 ２
C 0 0 0 0 ０
D 0 0 1 0 １
１ １ ３ １ 入度
A
D
C
B
例如,图 6-1（ａ） 所示的有向图的邻接矩阵为：
武汉理工大学华夏学院 -信息工程系上图所示的无向图的邻接矩阵为：
A B C D
A 0 1 1 1
B 1 0 1 1
C 1 1 0 1
D 1 1 1 0
很显然，这是一个对称阵。
A
BD
C
武汉理工大学华夏学院 -信息工程系二、特点,从上例中可以看出：无向图的邻接矩阵是一个对称阵。有向图的邻接矩阵中，
各行的和代表了该行表示的顶点的出度，各列的和代表了该列表示的顶点的入度。
三、带权的邻接矩阵（耗费矩阵） 对于网络图来说，其邻接矩阵定义为,对于有 N个顶点的图的邻接矩阵是一个 N× N的方阵 C,其中
C[I,J]的值是这样确定的：当顶点 I对顶点 J
有边相连时 C[I,J]等于该边上的权值ｗ ｉｊ,
当顶点 I对顶点 J无边相连时，若 I等于 J,则
C[I,J]的值为０；若 I不等于 J,则 C[I,J]的值为无穷大。
武汉理工大学华夏学院 -信息工程系上图所示的网络图的耗费矩阵为：
A B C D
A 0 8 9 4
B ～ 0 7 ～
C ～ ～ 0 ～
D ～ ～ 2 0
A
D B
C 72
84
9
武汉理工大学华夏学院 -信息工程系
6.２,２ 邻接表邻接表是表示顶点之间的相邻关系的ｎ个单向链表。（ｎ为图中顶点的个数）邻接表由两部分组成：
其一 为表头部分，用来存放各顶点的数据值，
又称为顶点表；
其二 为链表部分，用来存放相邻顶点的地址。
又称边表武汉理工大学华夏学院 -信息工程系在 邻接表中，采用顶点的编号表示顶点表头部分包括两部分内容：用来存放顶点的名称和相关数据（ data） 和指向表结点的指针
(* firstarc)
链表部分包括三部分内容：邻接顶点编号
(adjvex)； 指向下一个边的指针 (*nextarc)；
数据域或权 (weight)；
表结点 头结点
adjvex nextarc weight data firstarc
武汉理工大学华夏学院 -信息工程系邻接表的特点一、无向图的邻接表表示对于第ｉ个链表中的每一个结点表示一条与顶点
ｉ相关联的边，结点中包含有两个字段其一为为相邻顶点的地址，其二为下一条与ｉ相关联的边。
二、有向图的邻接表表示有向图的邻接表分为只保存“出边”的邻接表和只保存“入边”的邻接表（也称为逆邻接表）两种。
邻接表是：对于第ｉ个链表中的每一个结点表示邻接于顶点ｉ的某个顶点在顶点表中的存放位置。
逆邻接表是：对于第ｉ个链表中的每一个结点表示邻接到顶点ｉ的某个顶点在顶点表中的存放位置。
武汉理工大学华夏学院 -信息工程系邻接表的性质
1、图的邻接表表示不唯一；
2、无向图的邻接表中第 I个边表中结点的个数为第 I个顶点的度；
3,有向图的邻接表中第 I个边表中结点的个数为第 I个顶点的出度；
有向图的逆邻接表中第 I个边表中结点的个数为第 I个顶点的入度；
4、无向图的边数等于无向图的邻接表中边表结点的个数的一半、有向图的弧数等于有向图的邻接表中边表结点的 数目；（或逆邻接表中入边表结点的 数目）
武汉理工大学华夏学院 -信息工程系
6.２,３建立图的存储结构图的存储结构是用算法来实现的。下面给出建立网络图的邻接矩阵和邻接表的算法。
一、算法中的变量单元分配二维数组ａｄｊｍ表示邻接矩阵；
一维数组ａｄｊｌ表示邻接表中的顶点表；
整型变量ｎ表示网络图中的顶点个数；
常量 n0是数组的最大下标。
在邻接表存储结构中：
顶点表中的每个元素包含有两个字段：
ｄｅｇｒｅｅ 字段：表示无向网络图中的顶点的度或有向网络图中的顶点的入度。
Ｆｉｒｓｔ 字段：表示指针，指向链表中的第一个结点 。
武汉理工大学华夏学院 -信息工程系二、算法思想通过输入一系列表示边的三元组（ｉ，ｊ，ｗ）来建立网络的存储结构。其中ｉ，ｊ为顶点的序号，ｗ
为ｉ，ｊ边上的权值。
每输入一个三元组，就建一个结点，链接到链表中，
当输入的两个顶点序号超出顶点个数ｎ时，输入结束。
链表中的每个结点包含三个字段：
ｖｅｒｔｅｘ 字段表示相邻顶点的序号；
ｗｅｉｇｈｔ 字段表示边上的权值；
next字段表示指针，指向链表中的下一个结点的地址。
武汉理工大学华夏学院 -信息工程系三、邻接矩阵的建立算法
const int n0=100;
// 定义一个大数表示无穷 //
const int infinity=32767;
int adjm[n0+1][n0+1];
int n ;
void set()
{
int I,j,k,w ;
cout<<“顶点数：,
cin >> n;
// 邻接矩阵初始化 //
for ( I=1 ; I<=n ; I++)
{
for j=1 ; j<=n ; j++ )
adjm[I][j] = infinity ;
adjm[I][I] = 0 ;
}
cout<<“请输入边的集合,\n” ;
cout<<“（ 始点 终点 权值） \n” ;
//读入第一条边
cin >>I>>j>>w ;
while (( I>=1)&&(I<=n)&&(j>=1)&&(j<=n))
{
adjm[I][j]=w;
//读入下一条边
cin >>I>>j>>w ;
｝
｝
武汉理工大学华夏学院 -信息工程系四、邻接表的建立算法
const int n0=100; // 定义一个大数表示无穷 //
const int infinity=32767;
struct arcnode{ /*表结点的定义 */
int adjvex; /*邻接点编号 */
struct arcnode *nextarc;
int weighx;
} ; ARCNODE,*ARCNODEPTR;
struct vnode{ /*头结点的类型 */
int data ;
ARCNODE *firstarc;
}VNODE,ADJLIST[N] ;
（ 详见教材 187页 ）?
武汉理工大学华夏学院 -信息工程系
scanf(“%d“,&(*g ).net;
printf(“1:无向网或图 (0) 2:有向网或图 (1)\n” )
scanf(“%d“,&(*g ).digraph;
void set(ALGRAPH *g)
{
int i,j,k,weight;
ARCNODE *p ;
printf(“请输入图的顶点数和边数 \n” )；
scanf(“%d,%d”,&(*g).vexnum,&(*g).arcnum);
for ( i=0 ; i< (*g).vexnum; i++)
{(*g).vertices[i].data=i;
(*g).vertices[i].firstarc=NULL;}
printf(“选择 1:图 (0) 2,网 (1)\n” )
武汉理工大学华夏学院 -信息工程系
p=(ARCNODEPTR)malloc(LEN) ;
P->adjvex=j;
p->nextarc= (*g).vertices[i].firstarc;
(*g).vertices[i].firstarc= p ;
if(!( (*g).net)) p-> weight=0;
else p-> weight= weight;
for(k=0;k< (*g).arcnum;k++)
{ if (!( (*g).net))
{ printf(“请输入边的端点的顶点编号 ) ;
scanf(“%d,%d”,&i,&j);
}
else
{ printf(“请输入边的端点的顶点编号及权 ) ;
scanf(“%d,%d”,&i,&j,&weight);
}
武汉理工大学华夏学院 -信息工程系
if(!( (*g).digraph))
p=(ARCNODEPTR)malloc(LEN) ;
P->adjvex=i;
p->nextarc= (*g).vertices[j].firstarc;
(*g).vertices[j].firstarc= p ;
if(!( (*g).net)) p-> weight=0;
else
p-> weight= weight;
}
}
}
武汉理工大学华夏学院 -信息工程系
6.3 图的遍历和生成树
6.３,１ 图的遍历的概念一、定义,从图中的任意一个顶点出发，对图中的所有顶点访问一次并仅访问一次的操作过程，
称为图的遍历二、遍历方法,通常有两种，即深度优先搜索法遍历图和宽（广）度先搜索法遍历图，简称深度遍历和宽（广）度遍历。
武汉理工大学华夏学院 -信息工程系三、与二叉树的遍历的异同二叉树的遍历有三种方法：前序、中序和后序遍历法，图的遍历只有两种方法：深度优先和广度优先遍历法；
二叉树的遍历必须从树根入手进行，而图的遍历可以从图中任一点开始；
二叉树的遍历结果是形成一个唯一的结点序列，而图的遍历结果是可以形成多个结点序 。
武汉理工大学华夏学院 -信息工程系
6.３,２ 深度优先搜索遍历一、深度遍历的思想
1,任选一个顶点 Vｉ 作为起始点进行访；
2,访问完起始点后，依次从邻接于 Vi的未被访问的顶点中选出一个顶点进行深度遍历，
直到 Vi的所有可能达到的顶点都访问完为止；
3,若图中还有未被访问的顶点，则从中又任选一个作起始点,重复上述过程,直到所有顶点被访问完为止。
武汉理工大学华夏学院 -信息工程系二、实例如图 6-6（ A） 所示的无向图，作深度遍历后形成的序列为：
A,B,C,F,E,D,H,G,I
或者 A,G,I,F,H,C,B,D,E
图 6-6（ A） 无向图的遍历实例
A
B G
DC H I
E
F
武汉理工大学华夏学院 -信息工程系如图 6-6（ B） 所示的有向图，作深度遍历后形成的序列为：
A,B,C,D 或者 A,C,B,D 或者
A,C,D,B
图 6-6（ B） 有向图的遍历实例
CB
A D
武汉理工大学华夏学院 -信息工程系三、深度遍历非递归算法思想
1,设置一个标志数组 MARK,用来表示顶点是否被访问过，当 MARK[I]=0时，表示 VI未被访问；当 MARK[I]=1时，
表示 VI已被访问过。
2,用邻接表存储图。
3,选定起始点，输出并将起始点置已访问标志。
4,将起始点进栈。
5,当栈不空时，重复进行：
取栈顶元素；判取栈顶元素有否未被访问的相邻顶点；
有，则选取一个输出、置标志、进栈； 若无，则退栈
6,直至栈空结束。
武汉理工大学华夏学院 -信息工程系
6.３,3 广度遍历一、广度遍历的思想
1,任选一个顶点 Vｉ 作为起始点进行访问；
2,访问完起始点后，依次访问邻接于 Vi的所有未被访问的顶点；
3,再从邻接于这些顶点中选出一个未被访问的顶点进行广度遍历,直到 Vi的所有可能达到的顶点都访问完为止；
4,若图中还有未被访问的顶点，则从中又任选一个作起始点，重复上述过程,直到所有顶点被访问完为止。
武汉理工大学华夏学院 -信息工程系二、实例如图 6-6（ A） 所示的无向图，作深度遍历后形成的序列为：
A,B,G,C,D,H,I,F,E
或者 A,G,B,I,H,D,C,F,E
如图 6-6（ B） 所示的有向图，作深度遍历后形成的序列为：
A,B,C,D 或者 A,C,B,D
武汉理工大学华夏学院 -信息工程系三、广度遍历非递归算法思想
1,设置一个标志数组 MARK,用来表示顶点是否被访问过,MARK[I]=0时，表示 V 被访问；当 MARK[I]=1时，
表示 VI已被访问过。
2,用邻接表存储图。
3,选定起始点，输出并将起始点置已访问标志。
4,将起始点进队。
5,当队不空时，重复进行：
取队首元素 输出、置标志、将未被访问的相邻顶点进队；队首元素出队；
6,直至队空结束。
武汉理工大学华夏学院 -信息工程系
6.3.3 图的遍历算法一、算法中的变量单元分配
ｎ 顶点个数
ｍ 图中边的条数
ｓ 数组，用作栈区
ｔ 栈指针
ｑ 数组，用作队列，
ｆ 和 ｒ 分别表示队首指针和队尾指针
ｍａｒｋ 为标志位数组
x 起始点序号武汉理工大学华夏学院 -信息工程系二,深度遍历算法设：要遍历的图已经用邻接表存储好，其深度遍历算法如下：
void dfs( int x) {
int mark[n0+1],k ;
int s[n0+1],t ;
arcnode *p ;
for (k=1 ; k<=n ; k++ ) mark[k] = 0 ;
printf(“\n%d”,x) ;
mark[x] = 1 ; t=1 ; s[1] = x ;
do { k= s[t] ; p=g.vetices[k],firstarc ;
武汉理工大学华夏学院 -信息工程系
while (p && mark[ p->vertex] )
p=p->next ;
if (p==NULL ) t -- ;
else
{
x= p ->adjvex ;
printf(“%d”,x) ;
mark[x] = 1 ;
s[++ t ] = x ;
}
} while (t ) ; }
武汉理工大学华夏学院 -信息工程系三、广度遍历算法设：要遍历的图已经用邻接表存储好，
其深度遍历算法如下,
void bfs( int x)
{ int mark[n0+1],k ;
int q[n0+1],f,r ; arcnode *p ;
for (k=1 ; k<=n ; k++ ) mark[k] = 0 ;
printf(“%d”,x) ;
mark[x] = 1 ;
f=1 ; r = 2 ; q[1] = x ;
武汉理工大学华夏学院 -信息工程系
do {
k= q [ f++ ] ;
p=adjl[k],First ;
while (p )
x=p->vertex ;
if ( mark [ x ] ==0)
{printf(“%d”,x) ;
mark [ x ] = 1 ;
q [ r++ ] = x ;
} p= p ->next ; }
} while (f !=r ) ; }
武汉理工大学华夏学院 -信息工程系
6.3.4 生成树和生成森林一、图的生成树的定义对于无向连通图，可以从任意一个顶点出发进行深度或广度遍历,将图中的所有顶点访问到；或对于有根有向图，可以从根出发进行深度或广度遍历将图中的所有顶点访问到。这时将遍历图时经过的边与图中所有顶点构成了一个原图的子图，这个子图称为图的生成树。
通常，把按深度遍历得到的树称为图的深度优先生成树；把按广度遍历得到的树称为图的广度优先生成树。
武汉理工大学华夏学院 -信息工程系例如 图 6-6（ A）所示的无向图的生成树为图
6-７所示。
二、图的生成树的特点
1.图的生成树是一个顶点数为最多（与图的顶点数ｎ相等 ),边数为最少 (仅有ｎ－１ )的原图的子图。
2.生成树是一个连通但无回路的子图，任意连接生成树中的两个顶点就会形成回路。
武汉理工大学华夏学院 -信息工程系
A
B G
DC H I
E
F
A
B G
DC H I
E
F
H
A
B G
DC I
E
F
深度优先生成树 广度优先生成树图 6－７无向图的生成树示意给定的一个无向图武汉理工大学华夏学院 -信息工程系三、非连通图的生成森林由于从非连通图的任意一点出发，不能把图中的所有顶点访问到，因此整个遍历过程结束时，将得到以各起始顶点为树根的多个树，
称其为生成森林。
四、深度优先生成树算法
１．变量存储单元分配同 6.３,３算法说明
２．算法武汉理工大学华夏学院 -信息工程系
void dfstree ( int x)
{
int mark[n0+1],k ;
int s[n0+1],t ;
arcnode *p ;
for (k=1 ; k<=n ; k++ ) mark[k] = 0 ;
mark[x] = 1 ;
t=1 ; s[1] = x ;
武汉理工大学华夏学院 -信息工程系
do { k= s[t] ;
p=adjl[k],First ;
while (p&& mark[ p->vertex] )
p=p->next ;
if (p==NULL ) t -- ;
else
{ x= p ->vertex ;
printf(“%d”,x) ;
mark[x] = 1 ; s[++ t ] = x ;
} } while (t ) ; }
武汉理工大学华夏学院 -信息工程系
6.4最小生成树
6．４．１ 概念一、最小生成树的定义对于一个连通无向网络图来说，从不同的顶点出发，可以形成多棵形状各异的生成树，
这些树中，各边的权值之和为最小的生成树，
称之为最小价值生成树亦称最小生成树。
图 6-7表示了一个连通网络图及其生成树和最小生成树。
武汉理工大学华夏学院 -信息工程系
５
６ ３
５
６
１６
６
１８
１９
１１
１４
２１
３３
连通无向网络图
１
５ ４
６ ３
５
１６
６
１８
１１
价值为５６的最小生成树
６ ３
５
６
１６
１８
１１
价值为５６的最小生成树
５
２
４
６ ３
５
６
１１
１４
２１
３３
价值为８７的生成树图 6－７无向网络图及其生成树
１ ２
４
２
１
５
２
４
１
武汉理工大学华夏学院 -信息工程系二、最小生成树的用途具有ｎ个顶点的无向网络图可以表示表示规划中的公路网或者局域网、城域网，顶点代表城市或站点，边上的权值表示了修公路或架电缆所需的造价，
这样，要将整个网络连通如何使造价最低？这就是用最小生成树来解决的问题。
武汉理工大学华夏学院 -信息工程系三、连通无向网络图的最小生成树的构造如何构造连通无向网络图的最小生成树，ｐｒｉｍ（普里姆）于１９５７年提出了一个简便方法。
１,原理 按权值长度不减原则，将顶点和边加到不断扩充的顶点和边的集合中
２,做法 首先从ｎ个顶点中任选一个顶点ｖ ｘ 加入到原来为空的生成树的集合中；当生成树的集合中的顶点数少于ｎ个时，重复以下步骤：
选取一条权值最小的边，使其一个顶点在生成树的顶点集合内，而另一个顶点不再生成树的顶点集合内；
将选取的这条边及其相关联的未在生成树的集合中的顶点添加到生成树的集合中直到生成树中的顶点数有
ｎ个时为止。
具体操作过程见图 6－８ 所示。
武汉理工大学华夏学院 -信息工程系
１
６ ３
５
６
１６
６
１８
１９
１１
１４
２１
３３
连通无向网络图
１ 选取一个结点添加到树中
１ １６
１
３
５
１６
重复执行选点过程
１ ２
４
３
５
６
１
４
３
５
６６
１１
４
３
５
６６
１１
１８
图 6－８构造最小生成树的过程
５
１
５
２
４
２
２
２
２
武汉理工大学华夏学院 -信息工程系四、算法步骤
１．辅助变量单元说明两个辅助数组,lowcost和 closest，其中 lowcost数组记录各顶点到生成树的最近距离：若顶点ｖ ｉ 已进入生成树的顶点集合中则 lowcost[I]=0,否则 lowcost[I]等于边（ｖ ｊ,ｖ ｉ ）的权值，其中ｊ＝ closest [ｉ ]。
２．具体做法先 将 closest数组中的各元素值都置为０,lowcost数组中的各元素按下列规则赋值：若（ｖ ｘ,ｖ ｉ ）是边，
则 lowcost [ｉ ] 的值为这条边的权值；若（ｖ ｊ,ｖ ｉ ）
不是边，且ｖ ｊ 不等于ｖ ｉ 则给 lowcost[ｉ ] 赋值为一个充分大的数，并令 lowcost [ｘ ]＝０；
武汉理工大学华夏学院 -信息工程系再做,每次从 lowcost数组中选取一个大于０的最小数，
例如 lowcost[ｉ ]，将 lowcost[ｉ ]置为０（即将ｉ顶点放入生成树中），然后检查 lowcost 数组中所有值都大于
０的元素 lowcost ［ｋ］,若 lowcost［ｋ］的值大于边（ｖ ｉ,ｖ ｋ ）的权值ｗ，则将 lowcost［ｋ］的值改为ｗ，并将 closest［ｋ］的值改为ｉ；
最后,当ｎ 个顶点全部进入生成树后，构造过程就结束，此时 lowcost 数组的各元素的值均为０，生成树的
ｎ－１条边都记录在 closest数组中了。
图 6－９记录了图 6－８形成的生成树的 lowcost与
closest数组的ｂｉａｎｈｕａ情况。
武汉理工大学华夏学院 -信息工程系
Ｌｏｗｃｏｓｔ数组的每一步变化
０
１６
～
～
１９
２１
０
０
５
６
１９
１１
０
０
０
６
１９
１１
０
０
０
０
１８
１１
０
０
０
０
１８
０
１
１
１
１
１
１
Ｃｌｏｓｅｓｔ数组的每一步变化
１
１
２
２
１
２
１
１
２
２
１
２
１
１
２
２
４
２
０
０
０
０
０
０
１
１
２
２
４
２
１
１
２
２
４
２
图 6－９最小生成树生成过程
１ ２ ３ ４ ５ ６
X=1为始点武汉理工大学华夏学院 -信息工程系五、具体算法
１．用邻接矩阵存储连通无向网络图，并已存储好
const int n0=100;
const int infinity=1.0e20 ; // 定义一个大数表示无穷 //
float adjm[n0+1][n0+1];
int n ;
void set()
{
int I,j,k,w ;
cout<<“顶点数：,
cin >> n; // 邻接矩阵初始化 //
武汉理工大学华夏学院 -信息工程系
for ( I=1 ; I<=n ; I++)
{
for j=1 ; j<=n ; j++ )
adjm[I][j] = infinity ;
adjm[I][I] = 0 ;
}
cout<<“请输入边的集合,\n” ;
cout<<“（ 始点 终点 权值） \n” ;
cin >>I>>j>>w ; //读入第一条边 //
while (( I>=1)&&(I<=n)&&(j>=1)&&(j<=n))
{
adjm[I][j]=w;
cin >>I>>j>>w ; //读入下一条边 //
｝
｝
武汉理工大学华夏学院 -信息工程系
２．Ｐｒｉｍ算法描述为
void prim( int x)
{
int I,j,k,closest[n0+1] ;
float min,lowcost[n0+1] ;
for ( j=1 ; j <= n ; j++ )
{
lowcost [ j ] = adjm [x ] [j] ;
closest [ j ] = x ;
}
for ( j=2 ; j<= n ; j++ )
{
min=infinity ;
for ( k=1 ; k <= n ; k++ )
if (( lowcost [ k ] < min ) && (lowcost [k ]!= 0 ))
{
min = lowcost [ k ] ;
I = k ;
}
武汉理工大学华夏学院 -信息工程系
lowcost [ I ] = 0 ;
for ( k=1 ; k <= n ; k++ )
if ( lowcost [ k ] > adjm [ k ][ I ]
{
lowcost [ k ]= adjm [ k ][ I ] ;
closest [ k ] = I ;
}
}
for ( j=1 ; j<= n ; j++ )
if ( j != closest [ j ] )
cout <<“(,<< j <<“,”<< closest [ j ] <<“)” ;
}
武汉理工大学华夏学院 -信息工程系
6.5最短路径一、最短路径的概念在网络图中从图中某个顶点ｖ ｘ 出发到达图中另一个顶点ｖ ｉ,一般有很多条路径（直接的或间接的），其中路径中各条边的权值之和为最小的路径,称为最短路径。
Ｖ ｘ 称为该条路径的源点，ｖ ｉ 称为路径的终点。例如：
下图中，从点１到点３有两条路：
一条为直接路径是从１到３，
另一条间接路径是从１经过２
到３，而最短路径为第二条，
路径长度为５。３２
２ ６
３
１
武汉理工大学华夏学院 -信息工程系二,单源最短路径
１．定义 在网络图中，求从指定源点到其余各顶点的最短路径问题，称为单源最短路径问题。
２．作用 将一个网络图看成一个城市间的交通运输网，每一个顶点代表一个城市，每一条边代表两城市之间的公路，边上的权值代表了公路的里程数，这样单源最短路径就可以解决：从某一个城市出发，能否到达另一个指定城市？若有多条路径，走哪一条路最近？
３．求法 Dijkstra 提出了一个解决此问题的简单方法，即：按最短路径长度值由小到大的次序，逐步求得每一条最短路径。
图 6－ 10 给出了求最短路径的实例。
武汉理工大学华夏学院 -信息工程系
２
６
８
１２
４５
１０
４０
１２
１５
３０
２５
１５
７ １７
３０
２０
３５
以ｖ１为源点，依次求,
第一步：ｖ１到ｖ４，长度为１２；
第二步：ｖ１到ｖ５，长度为２５；
第三步：ｖ１经ｖ４到ｖ７，长度为３２ ；
第四步：ｖ１经ｖ５到ｖ２，长度为４０；
第五步：ｖ１经ｖ４到ｖ６，长度为４２；
第六步：ｖ１经ｖ４经ｖ７到ｖ３，长度为５０；
图 6－１０最短路径解题示意
１
４ ３
５
武汉理工大学华夏学院 -信息工程系
4,算法设计
A,变量单元分配有向网络图用耗费矩阵 adjm存储；
ｖ ｘ 表示源点，则 １＜＝ｘ＜＝ｎ
辅助数组,dist,path和 mark，其中：
Dist 记录从源点到顶点ｉ的,当前最短路径”的路径长度值；
Path 记录从源点到顶点ｉ的“当前最短的”路径上倒数第 2个顶点的序号；
Mark 记录从源点到顶点ｉ 的最短路径是否确定,若
mark［ ｉ］＝１表示已确定，若 mark[i]=０表示尚未确定。
武汉理工大学华夏学院 -信息工程系
B,实施步骤首先，对三个数组赋值,令 m a r k［ ｘ］＝１；
mark［ｉ］＝０（ｉ＜＞ｘ） ；对所有的ｉ，令 dist［ｉ］
＝ｗ ｘｉ ； path［ｉ］＝ｘ
然后，重复执行下列过程：
从 mark［ｉ］＝ 0的顶点中选取一个距离源点ｖ ｘ
最近的顶点ｖ ｋ,将 mark［ｋ］置为１；
检查 mark［ｉ］＝ ０ 中的所有顶点距离源点ｖ ｘ
的路径长度，是否是通过ｖ ｋ 后使其路径缩短，若是，
则用短路径对原路径进行修正；
直到所有的顶点的 mark［ｉ］＝１为止。
C,具体算法 见实验 5
武汉理工大学华夏学院 -信息工程系
6.6 拓扑排序一、有关概念
1,拓扑序列 设图 G为一个有 n个顶点的有向图,G中 n
个顶点可以构成多个线性序列；若线性序列中的各顶点满足在原图中有序（如边 <x,y>表示 x在前,y在后）时，
在线性序列中仍然有序（即序列中 x一定在 y的前面），
对于满足这种条件的序列就称为拓扑序列。
2,拓扑排序 形成拓扑序列的过程称为拓扑排序。
3,AOV网 对于一个无回路的有向图，可以用来表示一个有多项活动的工程计划，每一个顶点表示一项活动，
活动之间有一种先后关系（用有向边表示），当所有活动完成后，工程就全部完成。这种顶点代表活动的网，
称为 AOV网。
武汉理工大学华夏学院 -信息工程系例如：某专业学生学习该专业的课程，
结业后方能获得毕业文凭，这就是一项工程。学习一门课程，就是一项活动，活动有先后次序（如：学完高等数学才能学工程数学），则制定教学计划时就要将所学各课程构成一个
AOV网，再进行拓扑排序，最后分学期实施。
武汉理工大学华夏学院 -信息工程系二,拓扑排序的步骤设有向图中顶点的个数为 n，
当 n>1时，重复进行：
1,任选一个入度为零（无前件）的顶点 x；
2,输出并从图中删除该顶点 x；
3,将与顶点 x相邻接的顶点的入度减一例如：图 6-11说明对 AOV网进行拓扑排序的过程注意,当在进行拓扑排序过程中，若找不到入度为零的顶点且拓扑序列中结点的个数少于 n
时，说明图中存在有回路，拓扑排序不能进行。
武汉理工大学华夏学院 -信息工程系
2
3 4
5 6
2
3 4
6
AOV网 输出 5后
2
3 4
6
输出 1后
2
4
6
输出 3后
2
6
输出 4后
6
选 2 输出形成的拓扑序列为,5,1,3,4,2,6
图 6-11AOV网及拓扑排序过程
11
武汉理工大学华夏学院 -信息工程系三、拓扑排序算法设计
１,辅助变量单元说明设置一个栈区 S[N0+1]用来将检测入度为零的顶点送入栈中，避免重复检测，
栈指针为 T=0。 用邻接表来存储 AOV网，并在顶点表 adjlist中的每一个元素，增设一个存放入度的字段 degree,初始时存放各顶点的入度，并检测其值为零时,将该顶点送入栈 s中。
武汉理工大学华夏学院 -信息工程系
２．具体算法
void toposort ()
{
int s[n0+1],t=0 ;
int I,j ;
arcnode *p ;
for (I=1 ; I <= n ; I++)
if (adjlist [I].degree==0)
s[++t] =I;
//*查找入度为零的顶点，进栈 *//
while (t )
{
I=s [t--] ;
//* 出栈输出并处理相邻顶点的入度 *//
printf(“%d”,I);
while (p )
{
j=p->vertex ;
adjlist[j ].degree -- ;
if ( adjlist [j ].degree ==0 )
s [++t] = j ;
p = p->next ;
}
}
}
武汉理工大学华夏学院 -信息工程系
6.7 关键路径一、有关概念
1,源点、汇点 在一个无回路的有向网络中，仅存在着一个入度为零的顶点，该顶点称为源点（又称为始点）；也仅存在着一个出度为零的顶点，该顶点称为汇点（又称为收点）。
2,关键路径 从源点开始到汇点结束的多条路径中的最长的一条路，称为关键路径。
3,AOE网 对于一个无回路的有向网络图，可以用来表示一个有多项活动的工程计划，每一个顶点表示一个事件，每一条边代表一项活动，边上的权值代表完成该活动所需的时间，当所有活动完成后，工程就全部完成。这种边表示活动的网，称为 AOE网。
武汉理工大学华夏学院 -信息工程系例如：要建造一栋楼房，从奠基（源点）
开始到交付使用（汇点）需要打地基、
砌墙、粉刷、按门窗、装水电煤气管道等活动，且每一项活动都要有一定时间才能做完，但有些活动可以同时进行，
而有些活动必须有先后次序，例如打地基时可以备砖，但砌墙开始时一定是地基全部打好。将该工程可以用 AOE网表示出来。见图 6-12 显然，该网中从源点到汇点共有五条路，但只有一条路径最长的，它是 1-3-4-7-9-10，长度为 21。
武汉理工大学华夏学院 -信息工程系
1
3
2 4
7 9 10
5 8
6
a2=6
a3=3
a4=6
a5=3 A10=4
a8=4
a6=2
a7=1
a9=5
a12=4
a11=2
a13=2
a1=5
图 6-12 AOE网武汉理工大学华夏学院 -信息工程系二,AOE网研究的问题确定完成整个工程需要多少时间；哪些活动是影响工程进度的关键，如何提前完成整项工程，很明显，从理论上讲，这是求关键路径和关键活动问题。
4,关键活动和非关键活动 在 AOE网中，组成关键路径的边称为关键活动，不在关键路径上的边称为非关键活动。
武汉理工大学华夏学院 -信息工程系三、求关键路径引入的相关量
1,对事件 Vi 而言
（ 1) 事件 Vi 的可能的最早发生时间 VE(i）
它是从源点 V1开始到顶点 Vi的最长路径。
(2) 事件 Vi 的可能的最晚发生时间 VL(i）
它是从源点 Vn开始到顶点 Vi的反向最长路径，
即 VL（ I)＝ VE ( n ）－ 汇点 Vn到顶点 Vi的最长路径。对图 6-12 而言，各顶点的最早发生时间和最晚发生时间见下表。
武汉理工大学华夏学院 -信息工程系
1 0 0 0
2 5 21-16=9 4
3 6 21-15=6 0
4 12 21-9=12 0
5 9 21-8=13 4
6 16 21-4=17 1
7 14 21-7=14 0
8 13 21-4=17 4
9 19 21-2=19 0
10 21 21-0=21 0
顶点 I VE（ I) VL(I) | VE(I)-VL(I) |
显然,VE(I)与 VL(I)相等的事件就是关键事件武汉理工大学华夏学院 -信息工程系
2,对活动 ai 而言设 活动 ai 的起点是 vj,终点是 vk,表示为 <VJ,Vk>,权值为 wjk
（ 1) 活动 ai 的最早发生时间 E(i） 它是活动的起点 Vj 的可能的最早发生时间 VE(J),即
E(I)=VE(J)。
(2) 活动 ai 的最晚发生时间 L(i） 它是活动的终点 Vk 的可能的最晚开始时间减该活动边上的权值 wjk,即 L（ I)＝ VL(K)-wjk 。
武汉理工大学华夏学院 -信息工程系
1 < 1,2 > 5 0 9 -5 = 4
2 < 1,3 > 6 0 6 -6 = 0
3 < 2,4 > 3 5 12-3 =9
4 < 3,4 > 6 6 12-6 =6
5 < 3,5 > 3 6 13-3=10
6 < 4,7 > 2 12 14-2=12
7 < 5,7 > 1 9 14-1=13
8 < 4,6 > 4 12 17-4=13
9 < 7,9 > 5 14 19-5=14
10 < 5,8 > 4 9 17-4=13
11 < 8,9 > 2 13 19-2=17
12 < 6,10 > 4 16 21-4=17
13 < 9,10 > 2 19 21-2=19
对图 6-12而言，各事件的最早开始时间和最晚开始时间见下表。
活动 ai 边 <VJ,Vk> 权值 wjk E(I) L(I)
武汉理工大学华夏学院 -信息工程系显然,E(I)=L(I)的活动为关键活动，本例的关键活动为
a2,a4,a6,a9,a13 。
对于 E(I)<>L(I)的活动称为非关键活动,L(I)-E(I)的值称为松弛时间（即可以略为延时一点而不影响工期的时间）。
三、关键路径计算算法设计
１．辅助变量单元说明设置数组 E[1..N]和 L[1..N]用来各顶点的可能的最早发生时间和最晚发生时间，用数组 S 表示两个迎面增长的栈，入度为零的顶点的序号构成第一个栈，栈指针为
T1； 每次输出的顶点的序号构成第二个栈,栈指针为 T2，
用邻接表来存储 AOE网。
武汉理工大学华夏学院 -信息工程系
２．具体算法
void criticalpath()
{
flot E[n0+1],L[n0+1] ;
int s[n0+1],t1=-1,t2=n0+1 ;
int I,j ;
arcnode *p ;
for (I=1 ; I <= n ; I++) E[I] =0 ;
s[++t] =I; / /*查找入度为零的顶点，进栈 *//
while (t 1 > -1 )
{
I=s [t--] ;
s[--t2]=I ;
p= adjlist[I].first ;
while (p )
武汉理工大学华夏学院 -信息工程系
{
j=p->vertex ;
adjlist[j ].degree -- ;
if ( adjlist [j ].degree ==0 )
s [++t1] = j ;
if ( E[j]< E[I] + p ->weight )
E[j]=E[I]+p->weight ;
p = p->next ;
}
}
for ( I=1 ; I <= n ; I++ ) L[I]=E[n] ;
while (t2< n0+1)
{
I=s[t2++] ;
p= adjlist[I].first ;
while (p )
武汉理工大学华夏学院 -信息工程系
{
j=p->vertex ;
if ( L[i]> L[j] - p ->weight )
L[i]=L[j]-p->weight ;
p = p->next ;
}
}
for ( I=1 ; I <= n ; I++)
{
p= adjlist[I].first ;
while (p )
{
j=p->vertex ;
if ( L[j]== E[i] + p ->weight )
cout <<“<“I<<“,”<<j<<“>” ;
p = p->next ;
}
}
}
武汉理工大学华夏学院 -信息工程系作业讲解（ P215）
6.5题对下图给出邻接矩阵、邻接表、逆邻接表
邻接矩阵为,0 1 1 1
0 0 1 0
1 0 0 1
0 1 0 0
邻接表为,逆邻接表为：
2 a
b
c
d
4 ^3
3 ^
4 ^1
2 ^
3 ^a
b
c
d
1
2 ^1
1
4 ^
3 ^
a
c
b d
武汉理工大学华夏学院 -信息工程系作业讲解（ P215）
6.7题对下图给出邻接矩阵、邻接表、
邻接矩阵为,0 1 1 1 0 0
1 0 0 0 1 0
1 0 0 1 1 0
0 0 1 0 1 1
0 1 1 1 0 1
0 0 0 1 1 0
邻接表为：
2 v1
v2
v3
v4
4 ^3
1
41
3
v1 v2
v3
v4 v5
v6
v5
v6
42
5
5 ^
5 ^
5 6 ^
3 6 ^
4 ^
武汉理工大学华夏学院 -信息工程系
6.15 对于下图求最小生成树
1
3
2 4
5
6
40
50
30
100
5
90
80
15
32
45
1
3
2 4
5
6
4
2
1
3
Kruskai方法
6
prim方法
4
6
4
6
5
2 4
5
6
1
4
2
3
5
3
2 4
5
6
6
3
2 4
5
61
武汉理工大学华夏学院 -信息工程系
6.16 求最短路径求 1号点到其余各点的最短路径?
4
6
5
3
2
1
154
28
15
10 20
10
10
4
选点 路径 中转点
3 15 1
2 15+4 3
5 19+10＝ 19 2
6 19+4＝ 23 2
4 23+8 6
顶点 直达路径
2 20
3 15
4 9999
5 9999
6 9999
武汉理工大学华夏学院 -信息工程系
6.17 对于给定的 AOE网求关键路径?
1
5
3
2
8
7
4
9
6
10
A1＝ 8
A2＝ 6
A3＝ 7
A4＝ 3
A5＝ 10
A6＝ 9
A7＝ 9
A8＝ 13
A9＝ 4
A10＝ 19
A11＝ 8
A12＝ 2
A13＝ 6
A14＝ 14
A15＝ 10
vi Ve(i) Vl(i)1 0 0
2 8 13
3 6 6
4 16 16
5 7 16
6 20 31
7 16 27
8 20 29
9 35 35
10 45 45
Ve(i) － Vl(i)0
5
0
0
9
31
27
29
35
45
11
11
9
0
0
1 0 0
2 8 13
3 6 6
4 16 16
5 7 16
6 20 31
7 16 27
8 20 29
9 35 35
10 45 45
－
0
5
0
0
9
31
27
29
35
45
11
11
9
0
0
1 3
4
A2＝ 6
A5＝ 10
9
10
关键路径为
A10＝ 19
A15＝ 10
注意：
ve(i)=源点到 I点的最长路径
vl(i)=ve(汇点 )-汇点到 I点的最长路径武汉理工大学华夏学院 -信息工程系
vi Ve(i) Vl(i)
1 0 0
2 8 13
3 6 6
4 16 16
5 7 16
6 20 31
7 16 27
8 20 29
9 35 35
10 45 45
Ve(i) － Vl(i)
0
5
0
0
9
31
27
29
35
45
11
11
9
0
0
按事件分析 按事件分析 按活动分析
ai e(i) l(i)
1 0 5
2 0 0
3 0 9
4 8 13
5 6 6
6 6 7
7 7 18
8 7 16
9 16 27
10 16 16
e(i) － l(i)
5
0
9
5
0
31
27
29
35
45
1
11
9
13
0
<VJ,VK> WJK
1,2 8
1,3 6
1,5 7
2,4 3
3,4 10
3,7 9
5,7 9
5,8 13
4,6 4
4,9 19
11 16 17
12 16 27
13 20 29
14 20 25
15 35 35
1
31
27
29
35
11
9
5
0
7,9 8
7,8 2
8,9 6
6,10 14
9,10 10
注意：
e(i)=ve(j)
l(i)=vl(k)-wjk
