文档介绍：解决图的编程问题数据结构(C# 语言版) 解决图的编程问题数据结构(C# 语言版) 目标在本章中,你将学到: –在图中存储数据–图的深度优先搜索和广度优先搜索算法–最小生成树–图的最短路径解决图的编程问题数据结构(C# 语言版) 学****情境——用图高速公路交通网的编程[问题描述] 一个地区由许多城市组成,为实现城市间的高速运输,需要在这些城市间铺设高速公路,以达到任意两个城市间高速运输的目的。经过考察和预算,铺设的高速公路交通网如图 所示。其中每个顶点代表一个城市,顶点间的连线代表两个城市间铺设的高速公路,而线上的数字表示两个城市间的距离(单位:公理)。如图所示。请根据上面的描述,解决下面的问题: ?用 C# 编写一程序来存储该高速公路交通网的信息。?从任何一个城市出发,访问所有的城市,给出访问城市的顺序。?如果想从一个城市到另一个城市旅行,给出最短的旅行路线。解决图的编程问题数据结构(C# 语言版) 图是一系列顶点(结点)和描述顶点之间的关系边(弧)组成。图是数据元素的集合,这些数据元素被相互连接以形成网络。其形式化定义为: G= (V,E) V={V i | V i∈某个数据元素集合} E={( V i ,V j ) | V i ,V j∈V∧ P(V i ,V j )} 认识图——图的定义和术语 1. 图的定义其中, G表示图, V是顶点的集合, E是边或弧的集合。在集合 E中, P(V i,V j)表示顶点 V i和顶点 V j之间有边或弧相连。解决图的编程问题数据结构(C# 语言版) 认识图——图的定义和术语 2. 图的术语顶点集:图中具有相同特性的数据元素的集合称为顶点集边(弧):边是一对顶点间的路径,通常带箭头的边称为弧弧头:每条箭头线的头顶点表示构成弧的有序对中的后一个弧尾:每条箭头线的尾顶点表示构成弧的有序对中的前一个顶点,称为弧尾或始点。度:在无向图中的顶点的度是指连那个顶点的边的数量。在有向图中,每个顶点有两种类的的度:出度和入度。入度:顶点的入度是指向那个顶点的边的数量。出度:顶点的出度是由那个顶点出发的边的数量。权:有些图的边(或弧)附带有一些数据信息,这些数据信息称为边(或弧)的权( weigh ).解决图的编程问题数据结构(C# 语言版) 认识图——图的定义和术语 3. 图的分类有向图:在一个图中,如果任意两顶点构成的偶对( Vi,Vj )是有序的,那么称该图为有向图。这里 Vi是弧尾, Vj是弧头。这表示有一个从顶点 Vi到顶点 Vj的路径。但是从 Vj到 Vi是不可能的无向图:在一个图中,如果有任意两顶点构成的边( Vi,Vj ),( Vi,Vj )和( Vj, Vi)是相同的在一个无向图中,如果任意两个顶点之间都有边相连,则称该图为无向完全图。无向完全图又称完全图在一个有向图,如果任意两个顶点之间都是弧相连,则称该图为有向完全图。有很少条边或弧的图称为稀疏图,反之称为稠密图。解决图的编程问题数据结构(C# 语言版) SetNode ():在图中增加一个新的顶点 GetNode ():获取图中指定顶点 SetEdge ():在两个顶点之间添加指定权值的边或弧 GetEdge ():获取两个顶点之间的边 DelEdge ():删除两个顶点之间的边或弧 GetNumOfVertex ():获取邻接矩阵顶点数 GetNumOfEdge ():获取邻接矩阵边或弧的数目 GetIndex ():获取指定顶点在数组中的索引 IsEdge ():判断两个顶点之间是否存在边或弧 IsNode ():判断指定结点是否是图的顶点认识图——识别图的基本操作图的基本操作有以下几种: 解决图的编程问题数据结构(C# 语言版) 邻接矩阵( Adjacentcy Matrix) 是用两个数组来表示图,一个数组是一维数组,存储图中的顶点信息,一个数组是二维数组,即矩阵,存储顶点之间相邻的信息,也就是边(或弧)的信息。如果图中有 n个顶点, 你需要大小为 n×n的二维数组来表示图。用 C# 语言表示邻接矩阵的代码参见 P190 页用邻接矩阵解决图的编程问题——用邻接矩阵表示图对邻接矩阵进行操作参见 P191 页代码。解决图的编程问题数据结构(C# 语言版) 邻接表的存储方法是一种顺序存储与链式存储相结合的存储方法,顺序存储部分用来保存图中顶点的信息,链式存储部分用来保存图中边(或弧)的信息。具体的做法是: 使用一个一维数组,其中每个数组元素包含两个域,其结构如右图所示。 其中顶点域( data ):存放与顶点有关的信息; 头指针域( firstadj ):存放与该顶点相邻接的所有顶点组成的单链表的头指针用邻接表解决图的编程问题——用邻接表表示图邻接单链表中每个结点