Question

数据结构10 图

Answer 1

这一篇我们要总结的是图(Graph)，图可能比我们之前学习的线性结构和树形结构都要复杂，不过没关系，我们一点一点地来总结。那么关于图，我将从以下几点进行总结：

1、图的定义

2、图相关的概念和术语

3、图的创建和遍历

什么是图呢？

图是一种复杂的非线性结构。

在线性结构中，数据元素之间满足唯一的线性关系，每个数据元素(除第一个和最后一个外)只有一个直接前驱和一个直接后继；

在树形结构中，数据元素之间有着明显的层次关系，并且每个数据元素只与上一层中的一个元素(父节点)及下一层的多个元素(孩子节点)相关；

而在图形结构中，节点之间的关系是任意的，图中任意两个数据元素之间都有可能相关。

图G由两个集合V(顶点Vertex)和E(边Edge)组成，定义为G=(V，E)

对于一个图，若每条边都是没有方向的，则称该图为无向图。图示如下：

因此，(V _i ，V _j )和(V _j ，V _i )表示的是同一条边。注意，无向图是用小括号，而下面介绍的有向图是用尖括号。

无向图的顶点集和边集分别表示为：

V(G)={V ₁ ，V ₂ ，V ₃ ，V ₄ ，V ₅ }

E(G)={(V ₁ ，V ₂ )，(V ₁ ，V ₄ )，(V ₂ ，V ₃ )，(V ₂ ，V ₅ )，(V ₃ ，V ₄ )，(V ₃ ，V ₅ )，(V ₄ ，V ₅ )}

对于一个图G，若每条边都是有方向的，则称该图为有向图。图示如下：

因此，(V _i ，V _j )和(V _j ，V _i )是两条不同的有向边。注意，有向边又称为弧。

有向图的顶点集和边集分别表示为：

V(G)={V ₁ ，V ₂ ，V ₃ }

E(G)={<V ₁ ，V ₂ >，<V ₂ ，V ₃ >，<V ₃ ，V ₁ >，<V ₁ ，V ₃ >}

我们将具有n(n-1)/2条边的无向图称为无向完全图。同理，将具有n(n-1)条边的有向图称为有向完全图。

对于无向图，顶点的度表示以该顶点作为一个端点的边的数目。比如，图(a)无向图中顶点V ₃ 的度D(V ₃ )=3

对于有向图，顶点的度分为入度和出度。入度表示以该顶点为终点的入边数目，出度是以该顶点为起点的出边数目，该顶点的度等于其入度和出度之和。比如，图(b)中顶点V ₁ 的入度ID(V ₁ )=1，出度OD(V ₁ )=2，所以D(V ₁ )=ID(V ₁ )+OD(V ₁ )=1+2=3

不管是无向图还是有向图，边数e、顶点数n和顶点的度数有如下关系：

拿图(b)来举例，由公式可以得到图G的边数e=(D(V ₁ )+D(V ₂ )+D(V ₃ ))/2=(3+2+3)/2=4

故名思义，这个就不解释了。

路径，比如在无向图G中，存在一个顶点序列V _p ，V _i1 ，V _i2 ，V _i3 …，V _im ，V _q ，使得(V _p ,V _i1 )，(V _i1 ,V _i2 )，…，(V _im ,V _q )均属于边集E(G)，则称顶点V _p 到V _q 存在一条路径。

路径长度，是指一条路径上经过的边的数量。

回路，指一条路径的起点和终点为同一个顶点。

连通图是指图G中任意两个顶点V _i 和V _j 都连通，则称为连通图。比如图(b)就是连通图。下面是一个非连通图的例子：

上图中，因为V ₅ 和V ₆ 是单独的，所以是非连通图。

强连通图是对于有向图而言的，与无向图的连通图类似。

带”权值”的连通图称为网。如图所示：

1.深度优先搜索遍历

深度优先搜索(DFS)遍历类似于树的前序遍历。其基本思路是：

①假设初始状态是图中所有顶点都未曾访问过，则可从图G中任意一顶点V为初始出发点，首先访问出发点V，并将其标记为已访问过。

②然后依次从V出发搜索V的每个邻接点W，若W未曾访问过，则以W作为新的出发点出发，继续进行深度优先遍历，直到图中所有和V有路径相通的顶点都被访问到。

③若此时图中仍有顶点未被访问，则另选一个未曾访问的顶点作为起点，重复上述步骤，直到图中所有顶点都被访问到为止。

图示如下：

注：红色数字代表遍历的先后顺序

如果采用邻接矩阵存储，则时间复杂度为O(n ² )；如果采用邻接表存储，时间复杂度为O(n+e)

2.广度优先搜索遍历

广度优先搜索遍历(BFS)类似于树的按层次遍历。其基本思路是：

①首先访问出发点V _i

②接着依次访问V _i 的所有未被访问过的邻接点V _i1 ，V _i2 ，V _i3 ，…，V _it 并均标记为已访问过。

③然后再按照V _i1 ，V _i2 ，… ，V _it 的次序，访问每一个顶点的所有未曾访问过的顶点并均标记为已访问过，依此类推，直到图中所有和初始出发点V _i 有路径相通的顶点都被访问过为止。

图示如下：

因此，图(f)采用广度优先搜索遍历以V ₀ 为出发点的顶点序列为：V ₀ ，V ₁ ，V ₃ ，V ₄ ，V ₂ ，V ₆ ，V ₈ ，V ₅ ，V ₇

如果采用邻接矩阵存储，则时间复杂度为O(n ² )，如果采用邻接表存储，则时间复杂度为O(n+e)