数据结构(五)

数据结构(五)

發佈於 2019-03-04

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

图的定义

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

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

各种图定义

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

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

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

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

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

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

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

图的顶点与边间关系

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

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

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

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

连通图

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

图的存储结构

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

1. 邻接矩阵
2. 邻接表
3. 十字链表
4. 邻接多重表
5. 边集数组

图的遍历

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

可分为:

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