一、定义

图是由 顶点 的有穷非空集合和顶点之间 边的集合组成，通常表示为：G(V,E)，其中，G 表示一个图，V 是图 G 中顶点的集合，E 是图 G 中边的集合。图中不允许没有顶点，但是可以没有边

基本术语：

• 有向边 : 顶点之间的边有方向，简称 弧，箭头的一边为 弧头 ，另一边为 弧尾 ；如果边没有方向则是 无向边
• 有向图 ：任意两个顶点之间的边均是有向边的图；如果均是无向边就是 无向图
• 完全图 ：任意两顶点之间都存在边的无向图是 无向完全图 ；任意两顶点之间都存在两条边的有向图是 有向完全图
• 稠密图 ：一个含有较多边的图；相对的，含有较少边的图时 稀疏图
• 顶点的度 ：连接该顶点的边的数量；在有向图中，该顶点入边数量是 入度 ，该顶点出边数量是 出度
• 邻接 ：两个顶点之间有边；有向边的起始顶点称为 入边邻接顶点 ，有向边的结束顶点称为 出边邻接顶点
• 路径 ：图中首尾相连的一组边；首和尾是同一个顶点的路径称为 环
• 简单路径 ：不存在环的路径；首和尾是同一个顶点的简单路径称为 简单回路 或简单环
• 连通图 ：任意两个顶点都存在路径的图；如果该图是有向图则称 强连通图
• 弱连通图 ：将有向图的所有有向边替换为无向边，得到的图称为原图的 基图 ，基图为连通图的有向图是 弱连通图
• 权：与边相关的数值；如果一个图的边有权则是 有权图 ，否则就是 无权图 ，有权图简称 网

基本操作：

• 按照顶点集和边集构造图
• 销毁已存在的图
• 获取顶点在图中的位置
• 返回图中指定顶点的值
• 在图中插入新的顶点
• 删除图中的顶点及其相关的边
• 在图中添加边
• 在图中删除边
• 深度优先遍历并执行调用
• 广度优先遍历并执行调用

二、图的遍历

从图中某一顶点出发访问图中其余顶点，且每一个顶点仅被访问一次，这个过程称为 图的遍历 。根据搜索方法的不同，又可以划分为两种搜索策略：

• 深度优先搜索（DFS）：类似于树的先序遍历。从图中某个顶点 V 出发，访问该顶点，然后依次从 V 的未被访问的邻接点出发继续深度优先遍历图中的其余顶点，直至图中所有和 V 有路径相通的顶点都被访问完为止。
• 广度优先搜索（BFS）：是一个分层遍历的过程，和树的层序遍历算法类同。从图的某一顶点 V 出发，访问此顶点后，依次访问 V 的邻接点；然后分别从这些邻接点出发，直至图中所有已被访问的顶点的邻接点都被访问到。

三、存储结构

1、邻接矩阵

存储方式是用两个数组来表示图。一个一维数组存储图中顶点信息，一个二维数组（称为邻接矩阵）存储图中的边的信息，若图有 N 个顶点，则邻接矩阵就是一个 N×N 的方阵。
对于有向图和无向图，矩阵第 i 个元素存储记录图的第 i 个顶点是否能到达第 j 个顶点，若能记为 1，不能记为 0，i 和 j 相等也记为 0，而无向图的边视为双向边。特别的，无向图的邻接矩阵是一个对称矩阵。


对于有权的图，第 i 个元素存储记录图的第 i 个顶点到达第 j 个顶点的权，不能到达的记为∞，i 和 j 相等记为 0。

2、邻接表

对于边数相对顶点较少的图，邻接矩阵存在对存储空间的极大浪费的。因此我们考虑另外一种存储结构方式：邻接表，即数组与链表相结合的存储方法。用一个一维数组存储图中顶点信息，用单链表存储所有顶点的邻接点，无向图称为顶点的边表，有向图称为顶点的出边表，如果存储的是入边表，则称为 有向图的逆邻接表 ，如果是有权图，可以在边表结点定义中添加一个数据项来存储权值

3、十字链表

对于有向图来说，邻接表是有缺陷的，关心了出度问题，想了解入度就必须要遍历整个图才能知道，反之，逆邻接表也是类似的情况。可以把邻接表与逆邻接表结合起来，即有向图的一种存储方法十字链表。即在有向图的邻接表的边表结点定义中再增加一个入度指针。

4、邻接多重表

虽然邻接表是无向图的一种很有效的存储结构, 在邻接表中容易求得顶点和边的各种信息. 但是, 在邻接表中每一条边 (vi,vj) 有两个结点，分别在第 i 个和第 j 个链表中，这给某些图的操作带来不便。如对已被搜索过的边作记号或删除一条边等，此时需要找到表示同一条边的两个结点。可采用邻接多重表。

5、边集数组

由两个数组一维数组组成。一个一维数组存储图中顶点信息，另一个一个存储边信息，边数组的每个数据元素由一条边的起点下标、终点下标组成，如果是有权图，可以增加一个数据项存储权。

6、存储结构比较