实验五 图一 实验任务1）图的邻接表存储与遍历2）图的最短路径求解二 实验目的1）图的基本存储方法。2）掌握图的两种搜索路径的遍历方法。3）掌握图的有关应用（最短路径）。三 实验原理1图图G由两个集合组成：顶点（结点）集合V和连接顶点的边的集合E，集合E由集合V中的不同的顶点对组成，通常记为G=（V，E）。图是一种较线性表和树更为复杂的数据结构。在图形结构中，结点之间的关系可以是任意的，图中任意两个数据元素之间都可能有关。图的抽象数据类型定义如下： ADT Graph/Digraph 数据对象V：V是具有相同特性的数据元素的集合，称为顶点集。 数据关系R：R= VR 对于有向图VR= V，w| v， wV且P(v，w), V，w表示从v到w的弧， 谓词 P(v， w)定义了弧V， w的意义或信息 对于无向图VR= (v，w)| v， wV且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，w，则返回TRUE，否则返回FALSE。 Edges（G） 初始条件：G是已经存在的一个图。 操作结果：返回图中边的数目。 Vertices（G） 初始条件：G是已经存在的一个图。 操作结果：返回图中顶点的数目。 Add（G，v，w） 初始条件：图G已存在，v，w是两个顶点。 操作结果：如果G是有向图，则在G中添加一条弧V，w；如果G是无向图，则在G中添加一条边（v，w）。 Delete（G，v，w） 初始条件：图G已存在，v，w是两个顶点。 操作结果：如果G是有向图，则在G中删除一条弧V，w；如果G是无向图，则在G中删除一条边（v，w）。 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失败，则操作失败。 ADT Graph/Digraph2图的存储结构（1）邻接矩阵一个n个顶点的图G=（V，E）的邻接矩阵（Adjacency Matrix）是一个nn矩阵AdjMatrix， AdjMatrix中的每个元素是0或1。假设图G中顶点集合：V=1，2，n，那么AdjMatrix中的元素定义如下： AdjMatrix ij= 图的邻接矩阵存储结构的C语言描述形式如下：#define INFINITY INT_MAX#define MAX_VERTEX_NUM 20typedef enum DG=1, AG, DN, AN GraphKind； /有向图、无向图；有向网、无向网 typedef struct node VertexType vextex；/顶点信息Node；typedef struct arcs int adj；/ 顶点邻接关系 /该边或弧的相关信息指针 Arcs;typedef struct Node nodesMAX_VERTEX_NUM；/顶点集合 Arcs arcsMAX_VERTEX_NUMMAX_VERTEX_NUM； /邻接矩阵 int vexnum, arcnum； /顶点数和弧数 GraphKind kind;/kind取值1、2、3、4分别表示有向图、无向图、有向网、无向网Graph;（2）邻接表邻接表（Adjacency List）是一种顺序存储与链式存储相结合的存储结构，顺序存储部分用来保存图中顶点信息，链式存储部分保存图中边或弧的信息。具体做法是：图G被表示为一个数组或向量v1，v2，vn，每个元素对应图中一个顶点。每个vi存储顶点vi的信息，以及一个指向包含所有依附于顶点vi的边组成的单链表的指针，vi称之为头结点。头结点结构如下图所示：其中data存放与顶点相关的信息，firstarc是指针；邻接单链表中每个结点表示依附于该顶点的一条边（对于有向图则是以顶点vi为尾的弧），称为边（弧）结点，其结构如下图所示：其中adjvex存放依附于该边的另一个顶点在一维数组中的序号，对于有向图，存放的是该弧结点所表示的弧的弧头顶点在一维数组中的序号；nextarc为指向下一条边（或弧）结点的指针；info存储和边或弧相关的信息，如权值等。图的邻接表存储结构的C语言描述形式如下：#define MAXLEN 10typedef struct node /*边结点结构*/int adjvex; /*存放与头结点相邻接的顶点在数组中的序号*/int info; /*权值等信息*/struct node *nextarc; /*指向与头结点相邻接下一个顶点的表结点*/ EdgeNode;typedef struct /*头结点结构*/int id; /*顶点入度*/char data; /*顶点信息*/EdgeNode *firstarc; /*指向头结点对应的单链表中的表结点*/ VexNode;typedef struct /*邻接表结构*/VexNode adjsMAXLEN; /*邻接表的头结点集合*/int vexnum,arcnum; /*顶点数,边数*/int kind; /*图的种类*/ AdjList;3图的遍历图有两种搜索路径的遍历方法：深度优先搜索遍历和广度优先搜索遍历。图的深度优先搜索（Depth-First Search，DFS）策略是从给定顶点v出发，在回溯之前，沿着从v出发的一条路径尽可能深入前进。其遍历规则为：从v出发，访问v的一个未被访问的邻接顶点w1，再从w1出发，访问w1的一个未被访问的邻接顶点w2，然后从w2出发，访问w2的一个未被访问的邻接顶点w3，如此下去，直到一个所有邻接点都被访问过的顶点为止。然后回溯到尚有邻接点未被访问的顶点，重复上述过程，直到图中所有与v有路径相通的顶点都被访问过；此时，若图中还存在未被访问过的顶点，则从其中一个未被访问过的顶点出发，重复上述过程，直到图中所有顶点都被访问为止。图的广度优先搜索（Broad-First Search，BFS）策略是在访问给定顶点v之后，先访问与v邻接的所有顶点w1、w2、wk，然后再依次从w1、w2、wk出发，访问它们的未被访问过的邻接顶点，重复上述操作，直到图中所有被访问过的顶点的邻接顶点都被访问为止。若此时图中还有未被访问过的顶点，则从一个未被访问过的顶点出发，重复上述过程，直到图中所有的顶点都被访问过为止。4最短路径图的最短路径问题有：一是求从一个顶点（源点）到其它各顶点的最短路径；二是求每对顶点之间的最短路径。第一种情况采用迪杰斯特拉算法解决，这是一个按路径长度递增的顺序逐步产生最短路径的算法。第二种情况采用Floyd算法求解。（1）Dijkstra算法的实现设有向网G =（V，E），它采用邻接矩阵作为存储结构。若邻接矩阵为Cost，并规定：设立两个一维数组S和Distance，其中S存放已经找到最短路径的顶点，它的初始状态为：集合S中只含有起始顶点（源点）。并规定： Distance的每个分量Distancei表示当前所找到的从起始顶点v到每个目的顶点vi的最短路径长度。它的初始状态为：若从v到vi有弧，则Distancei为弧上的权值，否则置Distancei为，即Distancei = CostLocateVex（v）i，LocateVex用于确定顶点v在G中的位序。 利用Distance的各个分量的值，选取当前具有的最短路径的顶点vj，使得 Distancej = minDistancei viVS然后将顶点vj加入集合S中，即令Sj=1，同时对于所有Si=0的顶点vi，修改源点到它们可达的最短路径为 Distancei = minDistancei，Distancej+ Costji上述过程重复执行n-1次，就可以得到源点到其它顶点的最短路径值。（2）Floyd算法的思想假设求从顶点vi到顶点vj的最短路径。如果从顶点vi到顶点vj有弧，则从顶点vi到顶点vj存在一条长度为Costij的路径，该路径不一定是最短路径，尚需进行n次试探。首先考虑路径（vi，v0，vj）是否存在（即判断弧（vi，v0）和（v0，vj）是否存在）。如果