0

Reference: 8.23-8.24

关于 Graph 的算法就讲到这边啦~

我们讲了：

• 如何用 BFS 来找到 unweighted shortest path；
• 如何用 Dijkstra’s 算法来找到 weighted shortest path；
• 如何用 DFS 来做 graph exploration；
• 如何用 Strongly connected components（SCC）来简化图；
• 如何用 Topological sort 来进行排序；
• 如何用 Minimum weight spanning tree 来广播 message。

1. 关键术语复习

1. 基本概念

• edge：边

  edge cost = weight：边的重量

• vertex：顶点（我也经常用 node 来替换）

• path：vertex + edge

• parenthesis property：括号属性

  每个 node 的 discovery time 和 finish time 被称为括号属性。

2. 两种常见的 Graph 实现方式

• adjacency list 邻接表
• adjacency matrix 邻接矩阵

3. 不同的种类

1. acyclic graph 无环图

2. cyclic graph 有环图

3. directed graph 有向图

   Strongly connected components (SCC) 紧密连接的部分

4. directed acyclic graph DAG 有向无环图

4. 常见问题

• shortest path：最短路径

  weighted shortest path - Dijkstra’s 算法

  unweighted shortest path - BFS

• 广播问题

5. 算法

• breadth first search (BFS)

• depth first search (DFS) - graph exploration

  topological sort (解决流程问题)

• Minimum Spanning tree 最小生成树 (解决广播问题）

延伸：uncontrolled flooding（暴力解法）