解决图的编程问题
数据结构(C#语言版)
解决图的编程问题
数据结构(C#语言版)
目标
在本章中,你将学到:
在图中存储数据
图的深度优先搜索和广度优先搜索算法
最小生成树
图的最短路径
学习情境——用图高速公路交通网的编程
[问题描述]
一个地区由许多城市组成,为实现城市间的高速运输,需要在这些城市间铺设高速公路,以达到任意两个城市间高速运输的目的.经过考察和预算,铺设的高速公路交通网如图9.1所示.其中每个顶点代表一个城市,顶点间的连线代表两个城市间铺设的高速公路,而线上的数字表示两个城市间的距离(单位:公理).如图所示.
请根据上面的描述,解决下面的问题:
用C#编写一程序来存储该高速公路交通网的信息 .
从任何一个城市出发,访问所有的城市,给出访问城市的顺序.
如果想从一个城市到另一个城市旅行,给出最短的旅行路线.
图是一系列顶点(结点)和描述顶点之间的关系边(弧)组成.图是数据元素的集合,这些数据元素被相互连接以形成网络.其形式化定义为:
G=(V,E)
V={Vi | Vi∈某个数据元素集合}
E={(Vi,Vj) | Vi,Vj∈V∧P(Vi,Vj)}
认识图——图的定义和术语
1. 图的定义
其中,G表示图,V是顶点的集合,E是边或弧的集合.在集合E中,P(Vi,Vj)表示顶点Vi和顶点Vj之间有边或弧相连.
认识图——图的定义和术语
2. 图的术语
顶点集:图中具有相同特性的数据元素的集合称为顶点集
边(弧):边是一对顶点间的路径,通常带箭头的边称为弧
弧头:每条箭头线的头顶点表示构成弧的有序对中的后一个
弧尾:每条箭头线的尾顶点表示构成弧的有序对中的前一个顶点,称为弧尾或始点.
度:在无向图中的顶点的度是指连那个顶点的边的数量.在有向图中,每个顶点有两种类的的度:出度和入度.
入度:顶点的入度是指向那个顶点的边的数量.
出度:顶点的出度是由那个顶点出发的边的数量.
权:有些图的边(或弧)附带有一些数据信息,这些数据信息称为边(或弧)的权(weigh).
认识图——图的定义和术语
3. 图的分类
有向图:在一个图中,如果任意两顶点构成的偶对(Vi,Vj)是有序的,那么称该图为有向图.这里Vi是弧尾,Vj是弧头.这表示有一个从顶点Vi到顶点 Vj的路径.但是从Vj到Vi是不可能的
无向图:在一个图中,如果有任意两顶点构成的边(Vi,Vj),(Vi,Vj)和(Vj ,Vi)是相同的
在一个无向图中,如果任意两个顶点之间都有边相连,则称该图为无向完全图.无向完全图又称完全图
在一个有向图,如果任意两个顶点之间都是弧相连,则称该图为有向完全图.
有很少条边或弧的图称为稀疏图,反之称为稠密图.

下一页