《解决图的编程问题幻灯片》由会员分享，可在线阅读，更多相关《解决图的编程问题幻灯片（48页珍藏版）》请在金锄头文库上搜索。
1、解决图的编程问题,数据结构(C#语言版),1,目标,在本章中,你将学到: 在图中存储数据 图的深度优先搜索和广度优先搜索算法 最小生成树 图的最短路径,2,学习情境用图高速公路交通网的编程,问题描述 一个地区由许多城市组成，为实现城市间的高速运输，需要在这些城市间铺设高速公路，以达到任意两个城市间高速运输的目的。经过考察和预算，铺设的高速公路交通网如图9.1所示。其中每个顶点代表一个城市，顶点间的连线代表两个城市间铺设的高速公路，而线上的数字表示两个城市间的距离（单位：公理）。如图所示。,请根据上面的描述，解决下面的问题： 用C#编写一程序来存储该高速公路交通网的信息 。 从任何一个城市出发，
2、访问所有的城市，给出访问城市的顺序。 如果想从一个城市到另一个城市旅行，给出最短的旅行路线。,3,图是一系列顶点（结点）和描述顶点之间的关系边（弧）组成。图是数据元素的集合，这些数据元素被相互连接以形成网络。其形式化定义为： G=（V，E） V=Vi | Vi某个数据元素集合 E=(Vi,Vj) | Vi,VjVP(Vi,Vj),认识图图的定义和术语,1. 图的定义,其中，G表示图，V是顶点的集合，E是边或弧的集合。在集合E中，P(Vi,Vj)表示顶点Vi和顶点Vj之间有边或弧相连。,4,认识图图的定义和术语,2. 图的术语,顶点集：图中具有相同特性的数据元素的集合称为顶点集 边（弧）：边是一
3、对顶点间的路径，通常带箭头的边称为弧 弧头：每条箭头线的头顶点表示构成弧的有序对中的后一个 弧尾：每条箭头线的尾顶点表示构成弧的有序对中的前一个顶点，称为弧尾或始点。 度：在无向图中的顶点的度是指连那个顶点的边的数量。在有向图中，每个顶点有两种类的的度：出度和入度。 入度：顶点的入度是指向那个顶点的边的数量。 出度：顶点的出度是由那个顶点出发的边的数量。 权：有些图的边（或弧）附带有一些数据信息，这些数据信息称为边（或弧）的权（weigh）.,5,认识图图的定义和术语,3. 图的分类,有向图：在一个图中，如果任意两顶点构成的偶对（Vi,Vj）是有序的，那么称该图为有向图。这里Vi是弧尾，Vj是
4、弧头。这表示有一个从顶点Vi到顶点 Vj的路径。但是从Vj到Vi是不可能的 无向图：在一个图中，如果有任意两顶点构成的边（Vi,Vj），（Vi,Vj）和（Vj ，Vi）是相同的 在一个无向图中，如果任意两个顶点之间都有边相连，则称该图为无向完全图。无向完全图又称完全图 在一个有向图，如果任意两个顶点之间都是弧相连，则称该图为有向完全图。 有很少条边或弧的图称为稀疏图，反之称为稠密图。,6,SetNode()：在图中增加一个新的顶点 GetNode()：获取图中指定顶点 SetEdge()：在两个顶点之间添加指定权值的边或弧 GetEdge()：获取两个顶点之间的边 DelEdge()：删除两个
5、顶点之间的边或弧 GetNumOfVertex()：获取邻接矩阵顶点数 GetNumOfEdge()：获取邻接矩阵边或弧的数目 GetIndex()：获取指定顶点在数组中的索引 IsEdge()：判断两个顶点之间是否存在边或弧 IsNode()：判断指定结点是否是图的顶点,认识图识别图的基本操作,图的基本操作有以下几种：,7,邻接矩阵(Adjacentcy Matrix)是用两个数组来表示图，一个数组是一维数组，存储图中的顶点信息，一个数组是二维数组，即矩阵，存储顶点之间相邻的信息，也就是边（或弧）的信息。如果图中有n个顶点，你需要大小为nn的二维数组来表示图。 用C#语言表示邻接矩阵的代码
6、参见P190页,用邻接矩阵解决图的编程问题 用邻接矩阵表示图,对邻接矩阵进行操作参见P191页代码。,8,邻接表的存储方法是一种顺序存储与链式存储相结合的存储方法，顺序存储部分用来保存图中顶点的信息，链式存储部分用来保存图中边（或弧）的信息。具体的做法是：使用一个一维数组，其中每个数组元素包含两个域，其结构如右图所示。 其中 顶点域（data）：存放与顶点有关的信息； 头指针域（firstadj）：存放与该顶点相邻接的所有顶点组成的单链表的头指针,用邻接表解决图的编程问题 用邻接表表示图,邻接单链表中每个结点表示依附于该顶点的一条边，称作边结点，边结点的结构如右图所示。 其中 邻接点域(adj
7、vex)：指示与顶点邻接点在图中的位置，对应着一维 数组中的序号，对于有向图，存放的是该边结点所表示的弧的弧头 顶点在一维数组中的序号； 数据域(info)：存储边或弧相关的信息，如权值等，当图中边（或弧） 不含有信息时，该域可以省略。 链域(nextadj)：指向依附于该顶点的下一个边结点的指针。,无向图邻接表的邻接表结点类的代码参见P197页 。,9,用邻接表解决图的编程问题 用邻接表表示图 （举例）,对邻接表进行操作的代码参见P199页 。,10,9.4解决图的遍历问题深度优先搜索,1.理解深度优先搜索算法,从图的某一顶点x出发，访问x，然后遍历任何一个与x相邻的未被访问的顶点y，再遍历
8、任何一个与y相邻的未被访问的顶点z，如此下去，直到到达一个所有邻接点都被访问的顶点为止。然后依次回退到尚有邻接点未被访问过的顶点，重复上述过程，直到图中的全部顶点都被访问过为止。,对图进行深度优先遍历。深度优先遍历背后基于堆栈，有2种形式: 第一种是程序中显示构造堆栈，利用压栈出栈操作实现;第二种是利用递归函数调用，基于递归程序栈实现。本章介绍压栈和出栈的操作。,11,v1,将起始顶点v1压入栈。,9.4解决图的遍历问题深度优先搜索,12,v1,将顶点v1弹出栈 访问 v1 在栈中压入所有与v1相邻接的未访问顶点,v1,Visited:,9.4解决图的遍历问题深度优先搜索,13,v4,从栈中弹
9、出顶点 v1 访问 v1 在栈中压入所有与v1相邻接的未访问顶点,v1,Visited:,v2,9.4解决图的遍历问题深度优先搜索,14,Visited:,从栈中弹出顶点 v2 访问 v2 在栈中压入所有与v2相邻接的未访问顶点,v1,v2,v4,v2,9.4解决图的遍历问题深度优先搜索,15,Visited:,从栈中弹出顶点 v2 访问 v2 在栈中压入所有与v2相邻接的未访问顶点,v1,v2,v3,v6,v4,9.4解决图的遍历问题深度优先搜索,16,Visited:,从栈中弹出顶点 v3 访问v3 在栈中压入所有与v3相邻接的未访问顶点,v1,v2,v3,有与v3相邻接的未访问顶点,v6
10、,v3,v4,9.4解决图的遍历问题深度优先搜索,17,Visited:,从栈中弹出顶点 v3 访问v3 在栈中压入所有与v3相邻接的未访问顶点,v1,v2,v3,有与v3相邻接的未访问顶点,v6,v5,v4,9.4解决图的遍历问题深度优先搜索,18,Visited:,从栈中弹出顶点 v5 访问v5 在栈中压入所有与v5相邻接的未访问顶点,v1,v2,v3,v5,v6,v4,9.4解决图的遍历问题深度优先搜索,v5,19,Visited:,从栈中弹出顶点 v6 访问v6 在栈中压入所有与v6相邻接的未访问顶点,v1,v2,v3,v5,v6,v6,v4,9.4解决图的遍历问题深度优先搜索,20,
11、Visited:,从栈中弹出顶点 v4 访问v4 在栈中压入所有与v4相邻接的未访问顶点,v1,v2,v3,v5,v6,v4,v4,9.4解决图的遍历问题深度优先搜索,21,Visited:,栈现在是空的 因此，遍历完成,v1,v2,v3,v5,v6,v4,9.4解决图的遍历问题深度优先搜索,22,尽管上述算法提供了一个简单和常用的方法来遍历图，但是，如果图不是连接的，算法将不能正确工作。 在这样的情况下，你将不能够从单个起始顶点开始遍历所有顶点。,9.4解决图的遍历问题深度优先搜索,23,为了解决这个问题，你需要对图中所有未访问顶点重复执行上述算法。,对图中每个顶点v重复步骤2 如果v未被访
12、问： a. 调用 DFS(v),9.4解决图的遍历问题深度优先搜索,24,9.4解决图的遍历问题广度优先搜索,2.理解广度优先搜索算法,图的广度优先搜索是从图的某个顶点x出发，访问x。然后访问与x相邻接的所有未被访问的顶点x1,x2,.,xn；接着再依次访问与x1,x2,.,xn相邻接的未被访问过的所有顶点。依此类推，直至图的每个顶点都被访问。,25,访问 v1 将v1 插入队列,v1,v1,9.4解决图的遍历问题广度优先搜索,26,从队列中删除顶点 v1 访问与v1相邻接的所有未访问顶点并将它们插入队列,v1,v1,Visited:,9.4解决图的遍历问题广度优先搜索,27,从队列中删除顶点
13、 v1 访问与v1相邻接的所有未访问顶点并将它们插入队列,v2,v1,v2,v4,v4,9.4解决图的遍历问题广度优先搜索,28,从队列中删除顶点 v2 访问与v2相邻接的所有未访问顶点并将它们插入队列,v2,v1,v2,v4,v4,9.4解决图的遍历问题广度优先搜索,29,从队列中删除顶点 v4 访问与v4相邻接的所有未访问顶点并将它们插入队列,v1,v2,v4,v4,v3,v3,v6,v6,v5,v5,9.4解决图的遍历问题广度优先搜索,30,从队列中删除顶点 v3 访问与v3相邻接的所有未访问顶点并将它们插入队列,v1,v2,v4,v3,v3,v6,v6,v5,v5,v3没有任何未访问的
14、邻接顶点,9.4解决图的遍历问题广度优先搜索,31,从队列中删除顶点 v6 访问与v6相邻接的所有未访问顶点并将它们插入队列,v1,v2,v4,v3,v6,v6,v5,v5,v3没有任何未访问的邻接顶点,9.4解决图的遍历问题广度优先搜索,32,从队列中删除顶点 v5 访问与v5相邻接的所有未访问顶点并将它们插入队列,v1,v2,v4,v3,v6,v5,v5,v6没有任何未访问的邻接顶点,9.4解决图的遍历问题广度优先搜索,33,队列现在是空的 因此，遍历完成,v1,v2,v4,v3,v6,v5,v5没有任何未访问的邻接顶点,9.4解决图的遍历问题广度优先搜索,34,尽管上述算法提供了一个简单
15、和方便的遍历图的方法，但是，如果图不是连接的，算法将不能正确工作。 在这样的情况中，你将不能从单个开始顶点遍历所有顶点。,9.4解决图的遍历问题广度优先搜索,35,为了解决这个问题，你需要对图中的未访问顶点重复执行这个算法。,为图中每个顶点V重复步骤2。 如果 v 未被访问： a. 调用BFS(v),9.4解决图的遍历问题广度优先搜索,36,图的最短路径问题 Dijkstra算法的引入,Dijkstra算法的基本思想是： 设置两个顶点集合T和S，集合S中存放己经找到最短路径的顶点，集合T中存放当前还未找到最短路径的顶点。初始状态时，集合S中只包含源点v0，然后不断从集合T中选取到源点v0路径长
16、度最短的顶点w加入集合S，集合S中每加入一个新的顶点w，都要修改顶点v0到集合T中剩余顶点的最短路径长度值，集合T中各顶点新的最短路径长度值为原来最短路径长度值与顶点w的最短路径长度加上w到该顶点的路径长度值中的较小值。此过程不断重复，直到集合T的顶点全部加入集合S为止。,37,图的最短路径问题 分析高速公路交通网的最短路径,下面用Dijkstra算法解决高速公路最短路径的问题。现在假设高速公路交通网采用邻接矩阵作为存储结构。若邻接矩阵为matrix，并规定：,用Dijkstra算法来确定从城市A到其他城市的最短践离。Dijkstra算法的步骤 参见教材P212页,38,final,distance,1,1,0,0,0,0,0,90,150,180,图的最短路径问题 分析高速公路交通网的最短路径,A,B,C,D,
