山东大学《数据结构》实验指导05图

实验五图

一实验任务

1)图的邻接表存储与遍历

2)图的最短路径求解

二实验目的

1)图的基本存储方法。

2)掌握图的两种搜索路径的遍历方法。

3)掌握图的有关应用(最短路径)。

三实验原理

1.图

图G由两个集合组成：顶点(结点)集合V和连接顶点的边的集合E,集合

E由集合V中的不同的顶点对组成，通常记为6=(V,E)o图是一种较线性表

和树更为复杂的数据结构。在图形结构中，结点之间的关系可以是任意的，图中

任意两个数据元素之间都可能有关。

图的抽象数据类型定义如下：

ADTGraph/Digraph{

数据对象V：V是具有相同特性的数据元素的集合，称为顶点集。

数据关系R：R={VR}

对于有向图VR={<V<span>,w>|v,wiv且P(v,w),<V<span>,

w>表示从v到w的弧，

谓词P(v,w)定义了弧<V<span>，w>的意义或

信息)

对于无向图VR={(v,w)|v,wiv且P(v,w),(v,w)表示从v到w

的边，谓词P(v,w)定义了边(v,w)

的意义或信息)

基本操作P：

CreateGraph(&G,V,VR)

返回结果：V是图的顶点集，VR是图中边或弧集合。按V和VR的定

义构造图G。

DestoryGraph(&G)

初始条件：G是已经存在的一个图。

操作结果：销毁图G。

Exist(G,v,w)

初始条件：G是已经存在的一个图，v、w是两个顶点。

操作结果：如果存在边(v,w)或弧<V<span>，w>,则返回TRUE,

否则返回FALSEo

Edges(G)

初始条件：G是已经存在的一个图。

操作结果：返回图中边的数目。

Vertices(G)

初始条件：G是已经存在的一个图。

操作结果：返回图中顶点的数目。

Add(&G,v,w)

初始条件：图G已存在，v,w是两个顶点。

操作结果：如果G是有向图，则在G中添加一条弧<V<span>，w>；

如果G是无向图，则在G中添加一条边(v,w)o

Delete(&G,v,w)

初始条件：图G已存在，v,w是两个顶点。

操作结果：如果G是有向图，则在G中删除一条弧<V<span>,w>；

如果G是无向图，则在G中删除一条边(v,w)o

Degree(G,v)

初始条件：图G及顶点v已存在。

操作结果：返回图G中顶点v的度。

Indegree(G,v)

初始条件：图G及顶点v已存在。

操作结果：如果G是有向图，则返回顶点v的入度；如果G是无向图，

则返回图G中顶点v的度。

Outdegree(G,v)

初始条件：图G及顶点v已存在。

操作结果：如果G是有向图，则返回顶点v的出度；如果G是无向图，

则返回图G中顶点v的度。

DFSTraverse(G,v,visit())

初始条件：图G已存在，v是G中的某个顶点，visit是顶点的应用函

数。

操作结果：从顶点v起深度优先遍历图G,并对顶点调用函数visit一

次且仅一次。一旦visit失败，则操作失败。

BFSTraverse(G,v,visit())

初始条件：图G已存在，v是G中的某个顶点，visit是顶点的应用函

数。

操作结果：从顶点v起广度优先遍历图G,并对顶点调用函数visit一

次且仅一次。一旦visit失败，则操作失败。

}ADTGraph/Digraph

2.图的存储结构

(1)邻接矩阵

一个n个顶点的图G=(V,E)的邻接矩阵(AdjacencyMatrix)是一个nxn

矩阵AdjMatrix,AdjMatrix中的每个元素是0或1。假设图G中顶点集合:V={1,

2,n},那么AdjMatrix中的元素定义如下：

AdjMatrix[i][j]=<i-[jf!vml]-><!--[endif]->

<!-[if!vml]-->

<!-[endif]->

图的邻接矩阵存储结构的C语言描述形式如下：

#defineINFINITYINT_MAX

#defineMAX_VERTEX_NUM20

typedefenum{DG=1,AG,DN,AN}GraphKind；〃{有向图、无向图;

有向网、无向

网}

typedefstructnode{

VertexTypevextex；〃顶点信息

}Node；

typedefstructarcs{

intadj；//顶点邻接关系

...〃该边或弧的相关信息指针

}Arcs;

typedefstruct{

Nodenodes[MAX_VERTEX_NUM]；〃顶点集合

Arcsarcs[MAX_VERTEX_NUM][MAX_VERTEX_NUM];〃邻接矩阵

intvexnum,arcnum；〃顶点数和弧数

GraphKindkind;

〃kind取值1、2、3、4分别表示有向图、无向图、有向网、无向

网

}Graph;

（2）邻接表

邻接表（AdjacencyList）是一种顺序存储与链式存储相结合的存储结构，

顺序存储部分用来保存图中顶点信息，链式存储部分保存图中边或弧的信息。具

体做法是：图G被表示为一个数组或向量v[l],v[2],v[n],每个元素对应

图中一个顶点。每个v[□存储顶点%的信息，以及一个指向包含所有依附于顶点

W的边组成的单链表的指针，v[□称之为头结点。头结点结构如下图所示：

其中data存放与顶点相关的信息，firstarc是指针；邻接单链表中每个结点表示

依附于该顶点的一条边（对于有向图则是以顶点w为尾的弧），称为边（弧）结

点，其结构如下图所示：

其中adjvex存放依附于该边的另一个顶点在一维数组中的序号，对于有向

图，存放的是该弧结点所表示的弧的弧头顶点在一维数组中的序号；nextarc为

指向下一条边（或弧）结点的指针；inf。存储和边或弧相关的信息，如权值等。

图的邻接表存储结构的C语言描述形式如下：

#defineMAXLEN10

typedefstructnode{/*边结点结构*/

intadjvex;/*存放与头结点相邻接的顶点在数组中的

序号*/

intinfo;/*权值等信息*/

structnode*nextarc;/*指向与头结点相邻接下一个顶点的

表结点*/

}EdgeNode;

typedefstruct{/*头结点结构*/

intid;/*顶点入度*/

chardata;/*顶点信息*/

EdgeNode*firstarc;/*指向头结点对应的单链表中的表结

点*/

}VexNode;

typedefstruct{/*邻接表结构*/

VexNodeadjs[MAXLEN];/*邻接表的头结点集合*/

intvexnum,arcnum;/*顶点数，边数*/

intkind;/*图的种类*/

}AdjList;

3.图的遍历

图有两种搜索路径的遍历方法：深度优先搜索遍历和广度优先搜索遍历。

图的深度优先搜索(Depth-FirstSearch,DFS)策略是从给定顶点v出发，

在回溯之前，沿着从v出发的一条路径尽可能深入前进。其遍历规则为：从v出

发，访问v的一个未被访问的邻接顶点wl,再从wl出发，访问wl的一个未被

访问的邻接顶点w2,然后从w2出发，访问w2的一个未被访问的邻接顶点w3,...,

如此下去，直到一个所有邻接点都被访问过的顶点为止。然后回溯到尚有邻接点

未被访问的顶点，重复上述过程，直到图中所有与v有路径相通的顶点都被访问

过；此时，若图中还存在未被访问过的顶点，则从其中一个未被访问过的顶点出

发，重复上述过程，直到图中所有顶点都被访问为止。

图的广度优先搜索(Broad-FirstSearch,BFS)策略是在访问给定顶点v之

后，先访问与V邻接的所有顶点Wl、W2、…、Wk，然后再依次从Wl、W2、…、

Wk出发，访问它们的未被访问过的邻接顶点，重复上述操作，直到图中所有被

访问过的顶点的邻接顶点都被访问为止。若此时图中还有未被访问过的顶点，则

从一个未被访问过的顶点出发，重复上述过程，直到图中所有的顶点都被访问过

为止。

4.最短路径

图的最短路径问题有：一是求从一个顶点(源点)到其它各顶点的最短路径；

二是求每对顶点之间的最短路径。第一种情况采用迪杰斯特拉算法解决，这是一

个按路径长度递增的顺序逐步产生最短路径的算法。第二种情况采用Floyd算法

求解。

(1)Dijkstra算法的实现

设有向网G=(V,E),它采用邻接矩阵作为存储结构。若邻接矩阵为Cost,

并规定：

'Wjj顶去点到顶点之间有直接边，且权值为Wjj

Cost[i][j]=<0i=j,顶点i与顶点j是同一个顶点

8顶点i和顶点j之间没有边

设立两个一维数组S和Distance,其中S存放已经找到最短路径的顶点，它的初

始状态为：集合S中只含有起始顶点(源点)。并规定：

.未找到源点到顶点看的最短路径

SC，]=|1已经找到源点到顶点v的最短路径

Distance的每个分量Distance[口表示当前所找到的从起始顶点v到每个目的顶点

W的最短路径长度。它的初始表态为：若从v到％有弧，则Distance。]为弧上的

权值，否则置Distance。]为8,即Distance。]=Cost[LocateVex（v）][i],LocateVex

用于确定顶点v在G中的位序。

利用Distance的各个分量的值，选取当前具有的最短路径的顶点垮，使得

Distance[j]=min{Distance[i]|vieV-S}

然后将顶点Vj加入集合S中，即令SU]=1,同时对于所有S[i]=0的顶点Vi,修

改源点到它们可达的最短路径为

Distance[i]=min{Distance[i],Distance[j]+Cost[j][i]}

上述过程重复执行n-1次，就可以得到源点到其它顶点的最短路径值。

（2）Floyd算法的思想

假设求从顶点W到顶点垮的最短路径。如果从顶点Vi到顶点Vj有弧，则从顶

点坐到顶点埼存在一条长度为Cost[i][j]的路径，该路径不一定是最短路径，尚

需进行n次试探。首先考虑路径（w,vo,vj）是否存在（即判断弧（w,vo）和

（Vo，Vj）是否存在）。如果存在，则比较（Vi，Vo，Vj）和（Vi，Vj）的路径长度，

然后取长度较短者为顶点Vi到顶点Vj的中间顶点的序号不大于0的最短路径。

假如在路径上再增加一个顶点V1,也就是说，如果（Vi,…，VI）和（VI,...»

Vj）分别是当前找到的中间顶点的序号不大于0的最短路径，那么V1，

Vj）就有可能是从Vi到顶点Vj的中间顶点的序号不大于I的最短路径。将它和已

经得到的从Vi到顶点Vj的中间顶点序号不大于0的最短路径相比较，从中选出

中间顶点的序号不大于1的最短路径之后，再增加一个顶点V2,继续进行试探。

依次类推。在一般情况下，若（Vi,…，Vk）和（Vk,…，Vj）分别是从Vi到顶点

Vk和从Vk到顶点Vj的中间顶点的序号不大于k-l的最短路径，则将（Vi,...,Vk,...,

Vj）和已经得到的从vi到Vj且中间顶点序号不大于k-l的最短路径相比较，其长

度较短者便是从顶点Vi到顶点Vj的中间序号不大于k的最短路径。这样，在经过

n次比较后，最后求得的必是从顶点％到顶点垮的最短路径。按此方法，可以同

时求得各对顶点的最短路径。

四实验设备、仪器、工具与资料

微机、VC

五实验内容

（1）实验任务1：图的遍历

针对下图所示的有向图，编写C程序完成如下功能：

1）建立有向图的邻接表

2）并在邻接表存储基础上完成深度优先遍历和广度优先遍历。

V2

图5-1有向图

（2）实验任务2：求解图的最短路径

给出五个城市的交通图如图5-2所示，弧上数字表示城市之间的道路长度。

现要在五个城市中选择一个城市建造一个物流配送中心。问这个物流配送中心应

设在哪个城市到其他城市的路程之和最短？请编程解决这个问题。