解决图的编程问题

1、图编程问题、数据结构(c# language)、目标、本章中，将数据图存储在图中的深度优先搜索和宽度优先搜索算法最小生成树图的最短路径、学习情况图高速公路交通网络编程、问题描述区域由多个城市组成，为了实现城市之间的高速运输，必须在这些城市之间布置高速公路。经过调查和预算编制包装的高速公路交通网络如图9.1所示。其中，每个顶点表示一个城市，顶点之间的连接表示两个城市之间的高速公路，线的数量表示两个城市之间的距离(单位：公理)。如图所示。按照上面的说明解决以下问题：编写c#程序以存储有关高速公路交通网络的信息。从任何城市出发访问所有城市，并给出访问城市的顺序。如果你想从一个城市旅行到另一个城市，请

2、提出最短的旅行路线。插图是描述一系列顶点(节点)和顶点之间关系边(圆弧)的配置。插图是连接在一起形成网络的数据元素的集合。格式定义包括g=(v，e) v=vi | vi数据元素集合e=(vi，vj) | vi，vjvp(vi，vj)，了解示意图定义和术语1。地物的定义。其中g是图形，v是顶点集合，e是边或圆弧的集合。在集合e中，p(vi，vj)表示顶点vi和顶点vj之间连接了边或圆弧。了解图的定义和术语，2 .地物术语，顶点集：地物中具有相同特性的数据元素的集合称为顶点集边(圆弧):边是顶点对之间的路径，通常将带箭头的边称为圆弧头：每条箭头线头顶上的点表示构成圆弧的对齐对的下一个圆弧端点。每条

3、箭头线的端点顶点表示构成弧的对齐对的上一个顶点，称为弧端点或起点。度：在无向图中，顶点的度表示到该顶点的连接边数。在直接图形中，每个顶点有两种度：出图和入射度。粒度：顶点的传入程度是指向该顶点的边数。输出：顶点的输出是从该顶点出发的边数。权利：某些图形的边(或圆弧)附带称为边(或圆弧)的“权重”(weigh)的数据信息。图的定义和术语，3 .图形的分类，有向图形：如果由一个图形中任意两个顶点组成的偶数对(vi，vj)对齐，则称为有向图形。其中vi是弧尾，vj是弧头。这意味着存在从顶点vi到顶点vj的路径。但是从vj到vi是不可能的全方位图。在一个图中，如果由任意两个顶点组成的边(vi，vj)、

4、(vi，vj)和(vj，vi)在同一无向图中的任意两个顶点之间连接了边，则这称为无向完全图。全向完全图，也称为完全图，在两个顶点之间连接圆弧的情况下，直接称为完全图。几乎没有边缘或弧的图称为稀疏图，反之称为稠密图。setnode():将新顶点添加到地物getnode():获取地物中指定的顶点setedge():添加两个顶点之间指定权重的边或圆弧getedge():获取两个顶点之间的边deletedge():获取两个顶点之间的边或圆弧相邻矩阵由两个数组表示。一个是存储图形顶点信息的一维数组，一个是存储顶点之间相邻信息的二维数组，即边(或圆弧)的信息。如果地物有n个顶点，则表示地物需要nn大小的二

5、维阵列。用c#语言表示相邻矩阵的代码p190页，用相邻矩阵解决的编程问题相邻矩阵表示，参见相邻矩阵操作p191页代码。相邻表是顺序存储与链存储的组合，顺序存储用于存储有关图顶点的信息，而链存储用于存储有关图边缘(或弧)的信息。具体方法是使用一维数组，其中每个数组元素由两个字段组成。其结构如右图所示。其中存储顶点域(data):顶点相关信息。头指针字段：保留单个链接表(由与该顶点相邻的所有顶点组成)的头指针。相邻单个链接表中的每个节点表示与该顶点相连的一条边，其结构称为边节点，如右图所示。其中相邻点字段(adjvex):表示与一维阵列的序号相对应的顶点相邻点的位置，对于直接图形，存储一维阵列中相

6、应边节点所表示的圆弧的圆弧头顶点的序号。资料栏位(info):储存与边或弧相关的资讯，例如插图中边(或弧)不包含资讯时可以省略的权值。链(nextadj):连接至此顶点的下一个边节点的指针。请参阅p197页，以获取无向图相邻表节点类代码。使用相邻表解决图表编程问题的图(示例)，参见操作相邻表的代码p199页。9.4求解图的遍历问题深度优先搜索，1 .了解深度优先搜索算法，从图形中某个顶点x开始，访问x，依次遍历与x相邻的未访问顶点y，遍历与y相邻的未访问顶点z，直到所有相邻的点都到达访问的顶点为止。然后，相邻点依次回退到尚未访问的顶点，重复操作，直到地物中的所有顶点都已访问。以执行图形的深度优

7、先遍历。深度优先遍历的后面是堆栈基础，两种格式：第一种是使用堆栈堆栈操作在程序中显示配置堆栈。第二种是使用递归函数调用基于递归程序堆栈实现的。本章介绍堆栈和堆栈操作。按、v1、起始顶点v1作为堆栈。，9.4解析图中的遍历问题深度优先搜索，v1，将堆栈访问v1从堆栈中拉出到与v1相邻的所有未访问的顶点，v1，visited 3360，9.4解析图中的遍历问题深度优先搜索，v4，从堆栈中拉出v1访问v1 9.4映射中的遍历问题深度优先搜索，visited:堆栈中的顶点v2访问v2中与v2相邻的所有未访问的顶点，v1、v2、v3、v6、v4、9.4解析图表中的遍历问题深度优先搜索，visited 3

8、330 从堆栈中弹出顶点v3访问v3以中压输入堆栈中与v3相邻的所有未访问的顶点，与v1、v2、v3、v3相邻的未访问的顶点，v6、v5、v4、9.4解决图中遍历问题的深度优先搜索，visited: v4，9.4解决方案图表中横向问题的深度优先搜索、visited:从堆栈中弹出v4访问v4在堆栈中对与v4相邻的所有未访问顶点进行重压，在v1、v2、v3、v5、v6、v4、v4、9.4解决方案图表中横向问题的深度优先在这种情况下，不能从单个起始顶点开始跨越所有顶点。9.4求解图中遍历问题深度优先搜索，要解决此问题，必须对图中所有未访问的顶点重复上述算法。对插图中的每个顶点v重复步骤2。v未访问：

9、a. dfs(v)，9.4解析图中遍历问题深度优先搜索，9.4解析图中遍历问题宽度优先搜索，2 .了解宽度优先搜索算法，图形的宽度优先搜索是从图形的顶点x之一开始访问x。然后，与x相邻的所有未访问的顶点x1、x2、xn；然后x1、x2、依次访问与xn相邻的所有未访问的顶点。图中的每个顶点都将继续，直到访问完为止。，访问v1将v1放入队列，v1，v1，9.4解析图中的遍历问题宽度优先搜索，从队列中删除v1访问与v1相邻的所有未访问的顶点并将其放入队列，v1，v1，visited:9.4解析图中的遍历问题宽度优先搜索，从队列中删除顶点v1 9.4解析图中遍历问题宽度的优先搜索，从队列中删除顶点v4

10、以访问与v4相邻的所有未访问的顶点，然后访问队列、v1、v2、v4、v3、v3、v3、v6、v6、v5、v5、9.4解析图中遍历问题宽度的所有顶点9.4解析图中的遍历问题宽度优先搜索，从队列中删除顶点v6访问与v6相邻的所有未访问的顶点并将其入队，没有未访问v1、v2、v4、v3、v6、v6、v5、v5、v3的相邻顶点，9.4解析图中的遍历问题范围优先搜索，从队列中检索v1、v2、v4、v3、v6、v5、v5、v6没有未访问的相邻顶点。9.4解析图中的遍历问题宽度首先搜索，队列为空，因此遍历完成。v1、v2、v4、v3、v6、v5和v5没有未访问过的相邻顶点。9.4上述算法提供了简单方便的遍历

11、图方法，但是如果图形不连接，则算法不能正常运行。在这种情况下，不能从单个起始顶点穿过所有顶点。9.4求解图中遍历问题的广度优先搜索，要解决此问题，必须对图中未访问的顶点重复此算法。对地物中的每个顶点v重复步骤2。如果v未访问：a. bfs (v)调用，首先搜索9.4图形的遍历问题范围，引入图形的最短路径问题dijkstra算法，dijkstra算法的基本思想如下：两个顶点集合t和s设置，集合s在已找到的最短路径上具有顶点，集合t在当前未找到的最短路径上具有顶点。在初始状态下，集s仅包含源点v0，然后在集t中继续选择源点v0路径长度最短的顶点w。每次在集s中添加新顶点w时，都会修改从顶点v0到集

12、t中其馀顶点的最短路径长度值。集t中每个顶点的新最短路径长度值是原始最短路径长度值加上顶点w的最短路径长度和该顶点w的路径长度值两者中较小的值。此过程不断重复，直到集t中的所有顶点都添加到集s中。利用图的最短路径问题高速公路交通网络的最短路径分析，下面的dijkstra算法解决高速公路最短路径问题。现在假设高速公路交通网络采用相邻矩阵作为存储结构。当相邻矩阵为matrix时，使用dijkstra算法确定从城市a到其他城市的最小运行距离。dijkstra算法的过程包括教材p212页，final，distance，1，1，0，0，0，90，150，180，图形最短路径问题分析高速公路交通网络最短路径，a，b e、f、0、1、2、3、4、5、final、distance、1、1、0、0、0、90、150、140、250 分析图形中的最短路径问题高速公路交通网络中的最短路径，a，b，c，d，e，f，0，1，2，3，4，5，final，distance，1，1，1 1，1，1