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. 它是对图中顶点的排序,保证在有向图中,每个节点的出现都是线性的有序的。
注意:
6. 为什么对树进行bfs和dfs的时候,不需要记录visited.
因为树中的每一个节点只有一个parent. 也就是说,任意两个点只有一条唯一的path. 当本次节点的访问结束之后,该节点不再会被访问。
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的拓扑序可能有多个
- 拥有唯一拓扑序的条件:
排序算法:
- 统计每个点的入度
- 将每个入度为 0 的点放入队列(Queue)中作为起始节点
- 不断从队列中拿出一个点,去掉这个点的所有连边(指向其他点的边),其他点的相应的入度 - 1
- 一旦发现新的入度为 0 的点,丢回队列中
Question of Topological sort
- 求任意1个拓扑序
- Topological Order
- 是否存在拓扑序(是否可以被拓扑排序)
- 是否存在环?
- 求所有的拓扑序
- DFS
- backtracking
- 求是否存在且仅存在一个拓扑序
- 每次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.
从任何一个顶点开始,记录每一个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过的点
在每一层有且只有一个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
Post a Comment