数据结构(五) - 旧游无处不堪寻

本篇，我们来讨论一种多对多的数据结构 —— 图。

图的定义

图(Graph)是由顶点有穷非空集合和顶点之间边的集合组成，通常表示为: G(V, E)，其中，G 表示一个图，V 是图 G 中顶点的集合，E 是图 G 中边的集合。

对于图的定义，我们需要注意几个方面:

线性表中我们把元素叫元素，树中将集合元素称为节点，在图中数据元素，我们则称为顶点(Vertex)
线性表中可以没有数据元素，称为空表。树中可以没有节点，称为空树。但是，在图中，不允许没有顶点

各种图定义

无向边: 若顶点 v_i 到 v_j 之间的边没有方向，则称这条边为无向边(Edge)，用无序偶对 (v_i, v_j) 表示，如果图中的边都是无向边，则称该图为无向图(Undirected graphs)。

有向边: 若顶点 v_i 到 v_j 之间的边有方向，则称这条边为有向边，也称为弧(Arc)，用有序偶对 <v_i, v_j> 表示，v_i 称为弧尾(Tail)，v_j 称为弧头(Head)，如果图中的边都是有向边，则称该图为有向图(Directed graphs)。

在图中，若不存在顶点到其自身的边，且同一条边不重复出现，则称这样的图为简单图。我们在本篇要讨论的也都是简单图。

在无向图中，如果任意两个顶点之间都存在边，则称该图为无向完全图。含有 n 个顶点的无向完全图有 n*(n-1)/2 条边。

在有向图中，如果任意两个顶点之间都存在方向互为相反的两条弧，则称该图为有向完全图。含有 n 个顶点的有向完全图有 n*(n-1) 条边。

有很少条边或弧的图称为稀疏图，反之称为稠密图。

有些图的边或弧具有与他相关的数字，这种与图的边或弧相关的数叫做权(Weight)。这种带权的图称为网(Network)。

图的顶点与边间关系

对于无向图 G=(V, {E})，如果边 (v, v_i) ∈ E，则称顶点 v 和 v_i 互为邻接点，即 v 和 v_i 相邻接。边 (v, v_i) 依附于顶点 v 和 v_i，或者说 (v, v_i) 与顶点 v 和 v_i 相关联。
顶点 v 的度是和 v 相关联的边的数目，记为 TD(v)。

对于无向图 G=(V, {E})，如果弧 <v, v_i> ∈ E，则称顶点 v 邻接到顶点 v_i，顶点 v_i 邻接自顶点 v。以顶点 v 为头的弧的数目称为 v 的入度，记为 ID(v)，以 v 为尾的弧的数目称为 v 的出度，记为 OD(v)，顶点 v 的度为 TD(v) = ID(v) + OD(v)。

无向图 G=(V, {E}) 中从顶点 v 到顶点 v_i 的路径(Path)是一个顶点序列。
路径的长度是路径上的边或弧的数目。

第一个顶点到最后一个顶点相同的路径称为回路或环。

连通图

在无向图 G 中，如果从顶点 v 到顶点 v_i 有路径，则称 v 和 v_i 是连通的，如果对于图中任意两个顶点都是连通的，则称 G 是连通图。

图的存储结构

我们来看一下对于图的五种不同的存储结构:

邻接矩阵
邻接表
十字链表
邻接多重表
边集数组

图的遍历

从图中某一顶点除法访遍图中其余顶点，且每一个顶点仅被访问一次，这一过程就称为图的遍历。

可分为:

深度优先遍历(Depth First Search，DFS)
广度优先遍历(Breadth First Search，BFS)