Mengzelev's Blog

算法导论学习笔记-基本图论算法

Word count: 744 / Reading time: 3 min
2018/10/24 Share

辣鸡po主只挖坑不填坑
因为作业实在太多了!!!

试一下Mathjax有没有配置成功!

图的表示

邻接链表(Adjacency-list)

  • 由一个包含$|V|$条链表的数组Adj所构成,Adj[u]包含所有与结点u之间有右边相连的结点v
  • 存储空间需求:$\Theta(V+E)$
  • 鲁棒性高,稍加修改可以支持许多图的变种(如:有权图)
  • 缺陷:无法快速判断一条边是否在图中

邻接矩阵(Adjacency-matrix)

  • 用矩阵来存储连通信息
  • 存储空间需求:\Theta(V^2) 与边数|E|无关
  • 简单,图规模较小时优先使用

广度优先搜索BFS

算法描述

  • 从一个源结点s开始,每次从已发现的结点向未发现的结点扩展
  • 算法需要在发现所有距离源结点s为k的所有结点之后,才会发现距离源结点s为k+1的其他结点
  • 用三种颜色标记结点的访问状态:
    • 白色:未被发现
    • 黑色:本身被发现且所有与之相连的结点都已经被发现
    • 灰色:本身被发现且与之相连的结点中存在未被发现的
  • 结果可能以来

伪代码



  • 使用队列存储所有灰色结点
  • while循环的循环不变式:队列Q中包含的是灰色结点的集合

分析

  • 结点信息初始化: O(V)
  • 队列操作总时间: O(V) (每个结点都要进出各一次)
  • 扫描邻接链表: O(E)

总时间复杂度: O(V+E)
是图G的邻接链表大小的一个线性函数

最短路径正确性证明

一堆定理和证明

广度优先树

深度优先搜索DFS

算法描述

  • 大胆地往前走,走到底再回头(雾
  • 深度优先搜索的前驱子图可能有多棵树组成,即深度优先森林因为搜索可能从多个源结点重复进行
  • 对结点进行黑白灰染色,可以保证每个结点仅在一棵深度优先树中出现,保证所有的深度优先树是不相交的
  • 时间戳: 每个结点v有两个时间戳
    • 第一个时间戳v.d记录结点v第一次被发现的时间(染上灰色的时候)
    • 第二个时间戳v.f记录搜索完成对v的邻接链表扫描的时间(图上黑色的时候)
    • 时间戳都是处于1和2|V|之间的整数
    • u.d < u.f
  • 非树边:
    • 前向边F:从祖先指向后代
    • 后向边B:从后代指向祖先(包括有向图中的自循环)
    • 横向边C:两端点无血缘关系

伪代码



时间复杂度

  • 结点信息初始化: O(V)
  • DFS-VISIT: O(E)

总运行时间: O(V+E)

性质

能提供关于图结构的价值很高的信息

括号化结构

CATALOG
  1. 1. 图的表示
    1. 1.1. 邻接链表(Adjacency-list)
    2. 1.2. 邻接矩阵(Adjacency-matrix)
  2. 2. 广度优先搜索BFS
    1. 2.1. 算法描述
    2. 2.2. 伪代码
    3. 2.3. 分析
    4. 2.4. 最短路径正确性证明
    5. 2.5. 广度优先树
  3. 3. 深度优先搜索DFS
    1. 3.1. 算法描述
    2. 3.2. 伪代码
    3. 3.3. 时间复杂度
    4. 3.4. 性质
    5. 3.5. 括号化结构