文档介绍：.
解决图的编程问题
数据结构(C#语言版)
.
目标
在本章中,你将学到:
在图中存储数据
图的深度优先搜索和广度优先搜索算法
最小生成树
图的最短路径
.
学****情境——用图高速公路交通网的编程
[问题描述]
　一个地区由许多城市组成，为实现城市间的高速运输，需要在这些城市间铺设高速公路，以达到任意两个城市间高速运输的目的。经过考察和预算，。其中每个顶点代表一个城市，顶点间的连线代表两个城市间铺设的高速公路，而线上的数字表示两个城市间的距离（单位：公理）。如图所示。
请根据上面的描述，解决下面的问题：
用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）是相同的
在一个无向图中，如果任意两个顶点之间都有边相连，则称该图为无向完全图。无向完全图又称完全图
在一个有向图，如果任意两个顶点之间都是弧相连，则称该图为有向完全图。
有很少条边或弧的图称为稀疏图，反之称为稠密图。
.
SetNode()：在图中增加一个新的顶点
GetNode()：获取图中指定顶点
SetEdge()：在两个顶点之间添加指定权值的边或弧
GetEdge()：获取两个顶点之间的边
DelEdge()：删除两个顶点之间的边或弧
GetNumOfVertex()：获取邻接矩阵顶点数
GetNumOfEdge()：获取邻接矩阵边或弧的数目
GetIndex()：获取指定顶点在数组中的索引
IsEdge()：判断两个顶点之间是否存在边或弧
IsNode()：判断指定结点是否是图的顶点
认识图——识别图的基本操作
图的基本操作有以下几种：
.
邻接矩阵(Adjacentcy Matrix)是用两个数组来表示图，一个数组是一维数组，存储图中的顶点信息，一个数组是二维数组，即矩阵，存储顶点之间相邻的信息，也就是边（或弧）的信息。如果图中有n个顶点，你需要大小为n×n的二维数组来表示图。
用C#语言表示邻接矩阵的代码参见P190页
用邻接矩阵解决图的编程问题 ——用邻接矩阵表示图
对邻接矩阵进行操作参见P191页代码。
.
邻接表的存储方法是一种顺序存储与链式存储相结合的存储方法，顺序存储部分用来保存图中顶点的信息，链式存储部分用来保存图中边（或弧）的信息。具体的做法是：使用一个一维数组，其中每个数组元素包含两个域，其结构如右图所示。
　
　　其中
　顶点域（data）：存放与顶点有关的信息；
　　头指针域（firstadj）：存放与该顶点相邻接的所有顶点组成的单链表的头指针
用邻接表解决图的编程问题 ——用邻接表表示图
邻接单链表中每个结点表示依附于该顶点的一条边，称作边结点，边结点的结构如右图所示。
　
　其中
　邻接点域(adjvex)：指示与顶点邻接点在图中的位置，对应着一维
　数组中的序号，对于有向图，存放的是该边结