文档介绍：解决图的编程问题
目标
在本章中,你将学到:
在图中存放数据
图深度优先搜索和广度优先搜索算法
最小生成树
图最短路径
学****情境——用图高速公路交通网编程
[问题描述]
　一个地域由很多城市组成, 为实现城市间高速运输, 需要在这些城市间铺设高速公路, 以达成任意两个城市间高速运输目。经过考察和预算, 铺设。其中每个顶点代表一个城市, 顶点间连线代表两个城市间铺设高速公路, 而线上数字表示两个城市间距离（单位: 公理）。如图所表示。
请依据上面描述, 处理下面问题:
用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页代码。
邻接表存放方法是一个次序存放与链式存放相结合存放方法, 次序存放部分用来保留图中顶点信息, 链式存放部分用来保留图中边（或弧）信息。具体做法是: 使用一个一维数组, 其中每个数组元素包含两个域, 其结构如右图