图基本算法复习

1 图的基本算法

一般使用 V表示图中的所有顶点的集合 E表示图中所有边的集合, 对于图 G=(V,E) 计算复杂度的时候一般涉及两个输入作为计算规模 |V| |E| 即顶点数量和边的数量 O(VE) 表示 O(|V||E|)

图搜索算法可以用来发现图的结构,所以一般的图算法在一开始都会先通过搜索来获取图的结构,其他的一些图算法则是对基本的搜索加以优化,***图的搜索技巧是整个图算法领域的核心***

1.1 图的两种表示法

图有两种标准表示法 1.邻接表集合  2.邻接矩阵

两种表示法均可以表示有向图和无向图,但是对于稀疏图(边的数目|E|远小于|V|2)使用邻接矩阵无疑会填很多0,所以更适合使用邻接表集合的方法表示,反之对于稠密图(边数目|E|接近|V|2)使用邻接矩阵的表示方法无疑会提高缓存命中率而且使用随机存取性能会好很多(快速判断两个节点之间是否有边连接这种寻求比较强的时候也会使用邻接矩阵表示法)。

1.1.1 邻接表集合

邻接表集合是一个由|V|条链表组成的数组,暂且称之为Adj,每个顶点都有一条对应的链表,对于第u个顶点,链表 Adj[u]包含了与它直接由边连接的所有顶点(邻接结点) 对于有向图(a,b)将只出现在 Adj[a]中,因此所有邻接链表的长度之和等于|E|,但是对于无向图边(a,b)就是边(b,a)所以这个边的表示会出现在 Adj[a]和 Adj[b]中,因此所有邻接链表的长度之和等于 2|E|

  • 无论是不是有向图空间复杂度都是 Θ(V+E)
  1. 优点:
    • 鲁棒性高,比较容易做数据结构的扩展,比如增加权重的时候可以直接在存储结点的结构中增加权重属性,表示对应边的权重(邻接矩阵也可以在对应节点存储结构的指针来增强扩展性)
  2. 缺点:
    • 无法随机存取,判断边是否存在需要遍历链表,性能比较差。

1.1.2 邻接矩阵

通常在使用邻接矩阵表示图的时候需要将图中的结点编号为 1,2,3,4,5,6,…,|V|,这种编号可以是任意的(abc 神马的 无所谓) 图 G 的邻接矩阵表示由一个|V|×|V|的矩阵 A=(aij)予以表示,当 aij 的值为 1 的时候表示边(i,j)属于图 G,否则就是这条边不属于图 G。

  • 无论一个图有多少条边,它的邻接矩阵表示的空间复杂度都是 Θ(|V|2)
  • 对于无向图它的邻接矩阵是一个对称矩阵(自己就是自己的转置)。所以有些应用对于无向图用上半个矩阵就够了,节约一半存储空间。
  • 可以使用对应行列的数值来表示这条边的权重
  1. 优点:
    • 实现简单,适合小规模的图
    • 可以随机存取性能要好很多
  2. 缺点:
    • 对于稀疏图浪费的空间比较多

1.1.3 广度优先搜索

广度优先搜索是最简单的图搜索算法之一,也是许多重要的图算法的原型,Prim的最小生成树算法和Dijkstra的单源最短路径算法都使用了类似广度优先搜索的思想。 给定图G=(V,E)和一个可识别的源节点s,广度优先搜索对图G中的边进行系统性的探索来发现可以从源节点s到达的所有结点。该算法能够计算从源节点s到每个可到达的节点的距离(最少的边数),同时生成一个“广度优先搜索树”,该树以源结点s为根节点,包含所有可以从s到达的结点,对于每个从源节点s可以到达的结点v,在广度优先搜索树里从结点s到结点v的简单路径所对应的就是图G中从结点s到达结点v的“最短路径”,即包含最少边数的路径,该算法既可以用于有向图,也可以用于无向图。 广度优先搜索算法的得名就是因为它是以s结点为中心,延其广度方向向外扩展,一层层的发现所有结点,即算法需要在发现所有距离源结点为k的所有结点之后,才会发现距离源结点k+1的其他结点。 为了实现上述的算法,我们需要知道哪些结点已经被发现,哪些还没有,这样才不会绕回到源结点。因此广度优先搜索在概念上将每个结点涂上了黑白灰三个颜色,标识三种不同的状态(其实两种状态就够了,这里标记三种主要是为了便于理解)。所有节点最开始的状态都是白色的,在算法的推进过程中,第一次遇到一个节点的时候,该节点就会被标记为“发现”状态。这时候它的颜色也会进行相应的调整。黑色标识已经被遍历了所有和他连接了的结点都已经被发现的结点。灰色标识发现的“边界”即已经被发现,但是和它相连的其他邻接结点可能还没有被发现,灰色结点就是待遍历邻接链表的结点,一般通过一个队列管理,白色就是标识所有未发现结点。 在广度优先搜索的执行过程中将构造一棵广度优先树,一开始,该树仅含有根节点就是源结点s,在扫描已发现结点u的邻接链表时,每当发现一个白色结点v就将结点v和边(u,v)同时加入到这个树中,在广度优先树中,称结点u是结点v的前驱或者父节点,由于每个结点最多被发现一次(之后就会被标记),所以它最多只有一个父节点(在遍历这个结点所有未发现结点的时候发现了此结点)

  • 注意: 广度优先搜索树可能因为邻接链表的不同而不同。但是对距离的计算不会变
  • 时间复杂度:O(V+E) 扫描了所有顶点 O(V)初始化所有结点 O(E)扫描邻接表的内部项
  • 在向外扩展的过程中增加当前扩展层级的计数,即为当前结点到源结点的最短距离,递归的向父节点移动的路径即为最短路径。
  • 如果给定 G=(V,E),G 为一个有向图或无向图,设 s∈V 为任意结点,则对于任意边(u,v)∈E,(s,v)的最短距离小于或者等于 (s,u)的最短距离+1,其实就是排除 s 到 u 不可达的情况,s 到 v 的最短距离顶多也就是 s 到 u 的距离,加上 u 到 v 的这个 1

1.1.4 深度优先搜索

和广度优先很相似,但是一开始会尽可能的深入到尽可能边缘的结点,直到无法进一步深入的时候检查所有邻接结点,然后回溯到它的前驱结点再次执行深度优先搜索,和广度优先一样,深度优先搜索也会对结点进行染色,已发现但是邻接结点未遍历的结点标记灰色,未发现结点标记白色,已经发现且所有邻接结点也已经发现的结点标记黑色。

  • 深度优先搜索相关算法更倾向于从多个源结点开始搜索,所以结果很可能是个森林,而广度优先搜索一般为了获取最短路径相关的详细,所以一般是单源结点搜索,结果一般是一个树。
Last Updated 2017-07-04 二 21:32.
Emacs 24.5.1 (Org mode 9.0.9)