解决图的编程问题

《解决图的编程问题》由会员分享，可在线阅读，更多相关《解决图的编程问题（48页珍藏版）》请在装配图网上搜索。

1、单击此处编辑母版标题样式,单击此处编辑母版文本样式,第二级,第三级,第四级,第五级,*,解决图的编程问题,数据结构,(C#,语言版,),解决图的编程问题,数据结构,(C#,语言版,),目标,在本章中,你将学到,:,在图中存储数据,图的深度优先搜索和广度优先搜索算法,最小生成树,图的最短路径,学习情境,用图高速公路交通网的编程,问题描述,一个地区由许多城市组成，为实现城市间的高速运输，需要在这些城市间铺设高速公路，以达到任意两个城市间高速运输的目的。经过考察和预算，铺设的高速公路交通网如图,9.1,所示。其中每个顶点代表一个城市，顶点间的连线代表两个城市间铺设的高速公路，而线上的数字表示两个城市

2、间的距离（单位：公理）。如图所示。,请根据上面的描述，解决下面的问题：,用,C#,编写一程序来存储该高速公路交通网的信息。,从任何一个城市出发，访问所有的城市，给出访问城市的顺序。,如果想从一个城市到另一个城市旅行，给出最短的旅行路线。,图是一系列顶点（结点）和描述顶点之间的关系边（弧）组成。图是数据元素的集合，这些数据元素被相互连接以形成网络。其形式化定义为：,G=,（,V,，,E,）,V=V,i,|V,i,某个数据元素集合,E=(,V,i,V,j,)|,V,i,V,j,VP(V,i,V,j,),认识图,图的定义和术语,1.,图的定义,其中，,G,表示图，,V,是顶点的集合，,E,是边或弧的

3、集合。在集合,E,中，,P(V,i,V,j,),表示顶点,V,i,和顶点,V,j,之间有边或弧相连。,认识图,图的定义和术语,2.,图的术语,顶点集：图中具有相同特性的数据元素的集合称为顶点集,边（弧）：边是一对顶点间的路径，通常带箭头的边称为弧,弧头：每条箭头线的头顶点表示构成弧的有序对中的后一个,弧尾：每条箭头线的尾顶点表示构成弧的有序对中的前一个顶点，称为弧尾或始点。,度：在无向图中的顶点的度是指连那个顶点的边的数量。在有向图中，每个顶点有两种类的的度：出度和入度。,入度：顶点的入度是指向那个顶点的边的数量。,出度：顶点的出度是由那个顶点出发的边的数量。,权：有些图的边（或弧）附带有一些

4、数据信息，这些数据信息称为边（或弧）的权（,weigh,）,.,认识图,图的定义和术语,3.,图的分类,有向图：在一个图中，如果任意两顶点构成的偶对（,Vi,Vj,）是有序的，那么称该图为有向图。这里,Vi,是弧尾，,Vj,是弧头。这表示有一个从顶点,Vi,到顶点,Vj,的路径。但是从,Vj,到,Vi,是不可能的,无向图：在一个图中，如果有任意两顶点构成的边（,Vi,Vj,），（,Vi,Vj,）和（,Vj,，,Vi,）是相同的,在一个无向图中，如果任意两个顶点之间都有边相连，则称该图为无向完全图。无向完全图又称完全图,在一个有向图，如果任意两个顶点之间都是弧相连，则称该图为有向完全图。,有很少

5、条边或弧的图称为稀疏图，反之称为稠密图。,SetNode,(),：在图中增加一个新的顶点,GetNode,(),：获取图中指定顶点,SetEdge,(),：在两个顶点之间添加指定权值的边或弧,GetEdge,(),：获取两个顶点之间的边,DelEdge,(),：删除两个顶点之间的边或弧,GetNumOfVertex,(),：获取邻接矩阵顶点数,GetNumOfEdge,(),：获取邻接矩阵边或弧的数目,GetIndex,(),：获取指定顶点在数组中的索引,IsEdge,(),：判断两个顶点之间是否存在边或弧,IsNode,(),：判断指定结点是否是图的顶点,认识图,识别图的基本操作,图的基本操

6、作有以下几种：,邻接矩阵,(,Adjacentcy,Matrix),是用两个数组来表示图，一个数组是一维数组，存储图中的顶点信息，一个数组是二维数组，即矩阵，存储顶点之间相邻的信息，也就是边（或弧）的信息。如果图中有,n,个顶点，你需要大小为,nn,的二维数组来表示图。,用,C#,语言表示邻接矩阵的代码 参见,P190,页,用邻接矩阵解决图的编程问题,用邻接矩阵表示图,对邻接矩阵进行操作参见,P191,页代码。,邻接表的存储方法是一种顺序存储与链式存储相结合的存储方法，顺序存储部分用来保存图中顶点的信息，链式存储部分用来保存图中边（或弧）的信息。具体的做法是：使用一个一维数组，其中每个数组元素

7、包含两个域，其结构如右图所示。,其中,顶点域（,data,）：存放与顶点有关的信息；,头指针域（,firstadj,）：存放与该顶点相邻接的所有顶点组成的单链表的头指针,用邻接表解决图的编程问题,用邻接表表示图,邻接单链表中每个结点表示依附于该顶点的一条边，称作边结点，边结点的结构如右图所示。,其中,邻接点域,(,adjvex,),：指示与顶点邻接点在图中的位置，对应着一维,数组中的序号，对于有向图，存放的是该边结点所表示的弧的弧头,顶点在一维数组中的序号；,数据域,(info),：存储边或弧相关的信息，如权值等，当图中边（或弧）,不含有信息时，该域可以省略。,链域,(,nextadj,),：

8、指向依附于该顶点的下一个边结点的指针。,无向图邻接表的邻接表结点类的代码参见,P197,页。,用邻接表解决图的编程问题,用邻接表表示图（举例）,对邻接表进行操作的代码参见,P199,页。,9.4,解决图的遍历问题,深度优先搜索,1.,理解深度优先搜索算法,从图的某一顶点,x,出发，访问,x,，然后遍历任何一个与,x,相邻的未被访问的顶点,y,，再遍历任何一个与,y,相邻的未被访问的顶点,z,，如此下去，直到到达一个所有邻接点都被访问的顶点为止。然后依次回退到尚有邻接点未被访问过的顶点，重复上述过程，直到图中的全部顶点都被访问过为止。,对图进行深度优先遍历。深度优先遍历背后基于堆栈，有,2,种形

9、式,:,第一种是程序中显示构造堆栈，利用压栈出栈操作实现,;,第二种是利用递归函数调用，基于递归程序栈实现。本章介绍压栈和出栈的操作,。,v1,将起始顶点,v1,压入栈。,9.4,解决图的遍历问题,深度优先搜索,v1,将顶点,v1,弹出栈,访问,v1,在栈中压入所有与,v1,相邻接的未访问顶点,v1,Visited:,9.4,解决图的遍历问题,深度优先搜索,v4,从栈中弹出顶点,v1,访问,v1,在栈中压入所有与,v1,相邻接的未访问顶点,v1,Visited:,v2,9.4,解决图的遍历问题,深度优先搜索,Visited:,从栈中弹出顶点,v2,访问,v2,在栈中压入所有与,v2,相邻接的未

10、访问顶点,v1,v2,v4,v2,9.4,解决图的遍历问题,深度优先搜索,Visited:,从栈中弹出顶点,v2,访问,v2,在栈中压入所有与,v2,相邻接的未访问顶点,v1,v2,v3,v6,v4,9.4,解决图的遍历问题,深度优先搜索,Visited:,从栈中弹出顶点,v3,访问,v3,在栈中压入所有与,v3,相邻接的未访问顶点,v1,v2,v3,有与,v3,相邻接的未访问顶点,v6,v3,v4,9.4,解决图的遍历问题,深度优先搜索,Visited:,从栈中弹出顶点,v3,访问,v3,在栈中压入所有与,v3,相邻接的未访问顶点,v1,v2,v3,有与,v3,相邻接的未访问顶点,v6,v5

11、,v4,9.4,解决图的遍历问题,深度优先搜索,Visited:,从栈中弹出顶点,v5,访问,v5,在栈中压入所有与,v5,相邻接的未访问顶点,v1,v2,v3,v5,v6,v4,9.4,解决图的遍历问题,深度优先搜索,v5,Visited:,从栈中弹出顶点,v6,访问,v6,在栈中压入所有与,v6,相邻接的未访问顶点,v1,v2,v3,v5,v6,v6,v4,9.4,解决图的遍历问题,深度优先搜索,Visited:,从栈中弹出顶点,v4,访问,v4,在栈中压入所有与,v4,相邻接的未访问顶点,v1,v2,v3,v5,v6,v4,v4,9.4,解决图的遍历问题,深度优先搜索,Visited:,

12、栈现在是空的,因此，遍历完成,v1,v2,v3,v5,v6,v4,9.4,解决图的遍历问题,深度优先搜索,尽管上述算法提供了一个简单和常用的方法来遍历图，但是，如果图不是连接的，算法将不能正确工作。,在这样的情况下，你将不能够从单个起始顶点开始遍历所有顶点。,9.4,解决图的遍历问题,深度优先搜索,为了解决这个问题，你需要对图中所有未访问顶点重复执行上述算法。,对图中每个顶点,v,重复步骤,2,如果,v,未被访问：,a.,调用,DFS(v),9.4,解决图的遍历问题,深度优先搜索,9.4,解决图的遍历问题,广度优先搜索,2.,理解广度优先搜索算法,图的广度优先搜索是从图的某个顶点,x,出发，访

13、问,x,。然后访问与,x,相邻接的所有未被访问的顶点,x1,x2,.,xn,；接着再依次访问与,x1,x2,.,xn,相邻接的未被访问过的所有顶点。依此类推，直至图的每个顶点都被访问。,访问,v1,将,v1,插入队列,v1,v1,9.4,解决图的遍历问题,广度优先搜索,从队列中删除顶点,v1,访问与,v1,相邻接的所有未访问顶点并将它们插入队列,v1,v1,Visited:,9.4,解决图的遍历问题,广度优先搜索,从队列中删除顶点,v1,访问与,v1,相邻接的所有未访问顶点并将它们插入队列,v2,v1,v2,v4,v4,9.4,解决图的遍历问题,广度优先搜索,从队列中删除顶点,v2,访问与,v

14、2,相邻接的所有未访问顶点并将它们插入队列,v2,v1,v2,v4,v4,9.4,解决图的遍历问题,广度优先搜索,从队列中删除顶点,v4,访问与,v4,相邻接的所有未访问顶点并将它们插入队列,v1,v2,v4,v4,v3,v3,v6,v6,v5,v5,9.4,解决图的遍历问题,广度优先搜索,从队列中删除顶点,v3,访问与,v3,相邻接的所有未访问顶点并将它们插入队列,v1,v2,v4,v3,v3,v6,v6,v5,v5,v3,没有任何未访问的邻接顶点,9.4,解决图的遍历问题,广度优先搜索,从队列中删除顶点,v6,访问与,v6,相邻接的所有未访问顶点并将它们插入队列,v1,v2,v4,v3,v

15、6,v6,v5,v5,v3,没有任何未访问的邻接顶点,9.4,解决图的遍历问题,广度优先搜索,从队列中删除顶点,v5,访问与,v5,相邻接的所有未访问顶点并将它们插入队列,v1,v2,v4,v3,v6,v5,v5,v6,没有任何未访问的邻接顶点,9.4,解决图的遍历问题,广度优先搜索,队列现在是空的,因此，遍历完成,v1,v2,v4,v3,v6,v5,v5,没有任何未访问的邻接顶点,9.4,解决图的遍历问题,广度优先搜索,尽管上述算法提供了一个简单和方便的遍历图的方法，但是，如果图不是连接的，算法将不能正确工作。,在这样的情况中，你将不能从单个开始顶点遍历所有顶点。,9.4,解决图的遍历问题,

16、广度优先搜索,为了解决这个问题，你需要对图中的未访问顶点重复执行这个算法。,为图中每个顶点,V,重复步骤,2,。,如果,v,未被访问：,a.,调用,BFS(v,),9.4,解决图的遍历问题,广度优先搜索,图的最短路径问题,Dijkstra,算法的引入,Dijkstra,算法的基本思想是：,设置两个顶点集合,T,和,S,，集合,S,中存放己经找到最短路径的顶点，集合,T,中存放当前还未找到最短路径的顶点。初始状态时，集合,S,中只包含源点,v,0,，然后不断从集合,T,中选取到源点,v,0,路径长度最短的顶点,w,加入集合,S,，集合,S,中每加入一个新的顶点,w,，都要修改顶点,v,0,到集合,T,中剩余顶点的最短路径长度值，集合,T,中各顶点新的最短路径长度值为原来最短路径长度值与顶点,w,的最短路径长度加上,w,到该顶点的路径长度值中的较小值。此过程不断重复，直到集合,T,的顶点全部加入集合,S,为止。,图的最短路径问题,分析高速公路交通网的最短路径,下面用,Dijkstra,算法解决高速公路最短路径的问题。现在假设高速公路交通网采用邻接矩阵作为存储结构。若邻接矩阵为,matrix