Topological Sort

What's topological sort?

Topological sorting for Directed Acyclic Graph (DAG) is a linear ordering of vertices such that for every directed edge uv, vertex u comes before v in the ordering. Topological Sorting for a graph is not possible if the graph is not a DAG.

结果:
在DAG中,for every directed edge uv, vertex u comes before v in the ordering. 它是对图中顶点的排序,保证在有向图中,每个节点的出现都是线性的有序的。

注意:

  • 只有DAG能够拓扑排序。(什么是DAG? DAG 是没有回路的有向图。)
  • 不能拓扑排序的条件:
    • 有回路
    • 有向
  • 一个DAG的拓扑序可能有多个
  • 拥有唯一拓扑序的条件:


排序算法:
  1. 统计每个点的入度 
  2. 将每个入度为 0 的点放入队列(Queue)中作为起始节点 
  3. 不断从队列中拿出一个点,去掉这个点的所有连边(指向其他点的边),其他点的相应的入度 - 1 
  4. 一旦发现新的入度为 0 的点,丢回队列中

Question of Topological sort
  1. 求任意1个拓扑序
    • Topological Order 
  2. 是否存在拓扑序(是否可以被拓扑排序) 
    • 是否存在环?
  3. 求所有的拓扑序 
    • DFS
    • backtracking
  4. 求是否存在且仅存在一个拓扑序
    • 每次Queue中最多同时只有1个节点

拓展:
图的相关问题。
  • 树:in graph theory, a tree is an undirected graph in which any two vertices are connected by exactly one path. Every acyclic connected graph is a tree, and vice versa. 
    • 任意两个顶点有且只有一条path
    • 无环图就是一个数
  • 森林:
    • 多个不相连通的树组成森林
1. 如何判断一个图是否是一棵树

2. 搜索图中最近值为target的点

3. 无向图联通块
从任何一个顶点开始,记录每一个visit过的点,最后check是否每一个点都被visit过了。
For a disconnected graph, we get the DFS forest as output. 

4. 判断是否只有一个拓扑排序
在每一层有且只有一个indegree为0的点 -> queue.size() = 1 for all the time

5. 如何判断图里没有环?
无向图:check是否重复visit了已经visit过的点
有向图:check是否重复visit了已经在当前path上的点
To detect cycle, we can check for a cycle in individual trees by checking back edges. To detect a back edge, we can keep track of vertices currently in recursion stack of function for DFS traversal. If we reach a vertex that is already in the recursion stack, then there is a cycle in the tree. The edge that connects current vertex to the vertex in the recursion stack is a back edge.

6. 为什么对树进行bfs和dfs的时候,不需要记录visited.
因为树中的每一个节点只有一个parent. 也就是说,任意两个点只有一条唯一的path. 当本次节点的访问结束之后,该节点不再会被访问。


Comments

Popular posts from this blog

Unique Binary Search Trees

Coin in Line