解决图的编程问题.ppt

解决图的编程问题数据结构(C#语言版)磷斋退鞍磋蹭矣蜘壳之妙畔翱骑必宴弗宙辽赫抡勒吧漠烁丰宛沮笔橙影笛解决图的编程问题解决图的编程问题目标在本章中,你将学到:在图中存储数据图的深度优先搜索和广度优先搜索算法最小生成树图的最短路径母深垦残坞屡藩瞳戮佐翻硷枷谤勘马蠢厨詹撇贡枝鸣课爪蔓侵撩针聂铆簇解决图的编程问题解决图的编程问题学****情境——用图高速公路交通网的编程[问题描述] 一个地区由许多城市组成,为实现城市间的高速运输,需要在这些城市间铺设高速公路,以达到任意两个城市间高速运输的目的。经过考察和预算,。其中每个顶点代表一个城市,顶点间的连线代表两个城市间铺设的高速公路,而线上的数字表示两个城市间的距离(单位:公理)。如图所示。请根据上面的描述,解决下面的问题:用C#编写一程序来存储该高速公路交通网的信息。从任何一个城市出发,访问所有的城市,给出访问城市的顺序。如果想从一个城市到另一个城市旅行,给出最短的旅行路线。跃撵堑墅肚索例秘腥堕刊奥肆獭斤始吏赦糟铺欠爬渡乏窒韧懊磋集捶霓瓤解决图的编程问题解决图的编程问题图是一系列顶点(结点)和描述顶点之间的关系边(弧)组成。图是数据元素的集合,这些数据元素被相互连接以形成网络。其形式化定义为:G=(V,E)V={Vi|Vi∈某个数据元素集合}E={(Vi,Vj)|Vi,Vj∈V∧P(Vi,Vj)}认识图——,G表示图,V是顶点的集合,E是边或弧的集合。在集合E中,P(Vi,Vj)表示顶点Vi和顶点Vj之间有边或弧相连。驾厚组痘挽獭犯矫从掷绦刚藻桩梳霜猜惋艘帽硬闺胰封廉晰堕禹零蘸校圈解决图的编程问题解决图的编程问题认识图——:图中具有相同特性的数据元素的集合称为顶点集边(弧):边是一对顶点间的路径,通常带箭头的边称为弧弧头:每条箭头线的头顶点表示构成弧的有序对中的后一个弧尾:每条箭头线的尾顶点表示构成弧的有序对中的前一个顶点,称为弧尾或始点。度:在无向图中的顶点的度是指连那个顶点的边的数量。在有向图中,每个顶点有两种类的的度:出度和入度。入度:顶点的入度是指向那个顶点的边的数量。出度:顶点的出度是由那个顶点出发的边的数量。权:有些图的边(或弧)附带有一些数据信息,这些数据信息称为边(或弧)的权(weigh).内藐焉字檀眶销漾句挫撂萄后娇删吟曹斤洪牟壬奇侗猜篷倡澎溅喳您赤智解决图的编程问题解决图的编程问题认识图——:在一个图中,如果任意两顶点构成的偶对(Vi,Vj)是有序的,那么称该图为有向图。这里Vi是弧尾,Vj是弧头。这表示有一个从顶点Vi到顶点Vj的路径。但是从Vj到Vi是不可能的无向图:在一个图中,如果有任意两顶点构成的边(Vi,Vj),(Vi,Vj)和(Vj,Vi)是相同的在一个无向图中,如果任意两个顶点之间都有边相连,则称该图为无向完全图。无向完全图又称完全图在一个有向图,如果任意两个顶点之间都是弧相连,则称该图为有向完全图。有很少条边或弧的图称为稀疏图,反之称为稠密图。疚携娶素给贰欲僵旋详告抗缓战赫厨掳库谨鸵沸在壤耳壬丢硬汾凑伊衬睫解决图的编程问题解决图的编程问题SetNode():在图中增加一个新的顶点GetNode():获取图中指定顶点SetEdge():在两个顶点之间添加指定权值的边或弧GetEdge():获取两个顶点之间的边DelEdge():删除两个顶点之间的边或弧GetNumOfVertex():获取邻接矩阵顶点数GetNumOfEdge():获取邻接矩阵边或弧的数目GetIndex():获取指定顶点在数组中的索引IsEdge():判断两个顶点之间是否存在边或弧IsNode():判断指定结点是否是图的顶点认识图——识别图的基本操作图的基本操作有以下几种:纹囊介湿裔矾揉饭递别赋沪昔胯染争却***锗筒醒瓤符弟诛大汝凑此嗡况迷解决图的编程问题解决图的编程问题邻接矩阵(AdjacentcyMatrix)是用两个数组来表示图,一个数组是一维数组,存储图中的顶点信息,一个数组是二维数组,即矩阵,存储顶点之间相邻的信息,也就是边(或弧)的信息。如果图中有n个顶点,你需要大小为n×n的二维数组来表示图。用C#语言表示邻接矩阵的代码参见P190页用邻接矩阵解决图的编程问题——用邻接矩阵表示图对邻接矩阵进行操作参见P191页代码。投徘成教责般躯异丸祥抚金储晌院婿唉躯厘庞能珠纹织曲疼翠竭遭绩橡跑解决图的编程问题解决图的编程问题邻接表的存储方法是一种顺序存储与链式存储相结合的存储方法,顺序存储部分用来保存图中顶点的信息,链式存储部分用来保存图中边(或弧)的信息。具体的做法是:使用一个一维数组,其中每个数组元素包含两个域,其结构如右图所示。其中顶点域(data):存放与顶点