C++ 算法 数据结构 图的表示方式及定义

引言

Graph–现实世界或抽象概念之间的连接关系，例如：
（1）城市交通网
（2）人际相识关系
（3）网络连接关系

图的定义：图G(V,E)是某种数据或概念的顶点vertex集合V和连接这些顶点的边edge集合E组成的数据结构。图由顶点之间的关系和边之间的关系定义，顶点的位置或边的顺序不属于图的定义范围。

图的类型：最常见的一个类型是有向图，即边带着方向属性，有向图中有u、v两个顶点的边，就可以说是从u到v一条边和从v到u一条边，这种类型的图可以表示单向的关系，例如人与人之间的单恋关系，道路的单行线。边不带方向属性的图就是无向图。

还有一个常见的类型叫做加权图，即图中的边带有权值的属性，这种图可以表示两个点之间的距离，两种物品的交换比率，两个人之间的好感度。

还有把图的形态看作重要的因素，例如，多重图，其某些顶点之间存在两条以上的边，表示一些复杂的交通类型。两顶点间最多只有一条边的图结构成为简单图。

也可以仅从边的连接关系上看，通过边连接的两个顶点的方法只有一个的结构就叫做无根树，它是与树相同的无向图。

将图的各顶点分成不重叠的两组后，只有不同组的顶点间存在边，这样的图结构成为二分图，比如分为男性和女性用图结构表示异性恋者。

有时候同一图结构可以用上面介绍的多个属性，比如加权有向图或加权二分图。还有一种图叫做有向非循环图（DAG），这种图的特点是从某个点出发后，没有路径回到起点。

图的路径：路径path表示首尾相连的边。其中，对一个顶点最多只通过一次的路径称为简单路径，终止于起点的路径称为环路cycle或者回路。

图的应用示例

（1）铁路网的安全性分析：断点查找算法。
（2）分析社交网络：宽度优先搜索法。
（3）计算网速：最小生成树算法。
（4）一笔画：深度优先搜素法。
（5）外汇交易：最短路径算法。

隐式图结构

一些问题不具有图结构，但我们利用图结构可以轻松解决，这样的图结构称为隐式图。
（1）整理行程：深度优先搜索法。
（2）15拼图：最短路径问题。
（3）覆盖游戏版：二分图匹配算法。
（4）分配会议室：强连通分量。

图的几种表示法

邻接表表示方法：adjacency list中，图的各个顶点将保存从该顶点出发的各边线的目录，以此表示图结构。这种图的表示方法中，每个顶点都会保存一个链表：

vector<list<int> > adjacant;

也可以使用动态数组保存信息。
当需要表示加权图等具有附加属性的图结构时，可以使用结构体：

struct Edge{
	int vertex;	//边线另一侧顶点的编号
	int weight;	//边线加权值
};

这个也可以使用更简单的pair代替。

邻接矩阵表示方法：邻接表最大的缺点是，检查两个顶点是否相连时，需要逐个检查链表。为提高效率，使用邻接矩阵表示图结构。
邻接矩阵使用|V|*|V|大小的矩阵，即二维数组保存边线信息：

vector<vector<bool> > adjacent;

布尔型变量adjacant[i, j]表示是否存在从顶点i到顶点j的边线。使用邻接矩阵表示加权图时，可以使用int类型代替bool类型保存边线信息，如果两个顶点没有边线，可是赋值-1，或者不可能出现的极大值INF。

邻接矩阵和邻接表的比较：邻接矩阵一次就可以找到两点之间存在边线与否。不过邻接矩阵需要|V|*|V|的空间，邻接表需要|V|*|E|的空间。
边线条数正比于|V|²的图结构称为稠密图，比|V|²少很多的图结构称为稀疏图。考虑空间复杂度，稠密图使用邻接矩阵，稀疏图使用邻接表表示比较好。

隐式图的表示方法：例如迷宫问题，不需要建图，只判断具体情况即可。图非常大，只取其中一点或者当前状态要用到的。