Topological Sort
1. Topological Sorting
- DFS
- BFS
dfs
set: 记录已经到访过的node
可以随便从graph里面挑选一个未访问过的node, 从这个node开始dfs。每访问一个node，就要马上把node放进visited里面，即使这个点的邻居可能还没有遍历完。
需要注意的是，最后把遍历完邻居的点放进result里的时候，可以选择放在尾部，但是最后要翻转回来Collections.reverse()；或者每次都插在result的最前面。只有这样，才是正确顺序的top sort。
写起来比较方便。
/**
* Definition for Directed graph.
* class DirectedGraphNode {
* int label;
* ArrayList<DirectedGraphNode> neighbors;
* DirectedGraphNode(int x) { label = x; neighbors = new ArrayList<DirectedGraphNode>(); }
* };
*/
public class Solution {
/*
* @param graph: A list of Directed graph node
* @return: Any topological order for the given graph.
*/
public ArrayList<DirectedGraphNode> topSort(ArrayList<DirectedGraphNode> graph) {
if (graph == null || graph.size() == 0) return new ArrayList<DirectedGraphNode>();
Set<DirectedGraphNode> visited = new HashSet<DirectedGraphNode>();
ArrayList<DirectedGraphNode> result = new ArrayList<DirectedGraphNode>();
for (DirectedGraphNode node: graph) {
if (!visited.contains(node)) {
visited.add(node);//马上放入visited set
dfs(node, visited, result);
}
}
//这里需要翻转
Collections.reverse(result);
return result;
}
private void dfs(DirectedGraphNode node, Set<DirectedGraphNode> visited, ArrayList<DirectedGraphNode> result) {
for (DirectedGraphNode nei: node.neighbors) {
if (!visited.contains(nei)) {
visited.add(nei);//马上放入visited set
dfs(nei, visited, result);
}
}
result.add(node);
}
}
bfs
map: count indegree
queue: node with indegree = 0
因为给的是DirectedGraphNode，比较方便。
第一步都是先过一遍nodes，用map储存每个点对应的Indegree。Indegree为0的点并不会放进map里面，因为它不是任何点的邻居它们会被放进queue里面，方便后面作为开头来访问。
第二步就是，对照原本的graph和map.keySet()来看看那些点不在map，不在的点可以立刻放进result里面，同时也可以作为起始点放进queue里面（起始点可以是多个）。
第三步就是从起始点出发，遍历每一个邻居，遍历的同时，邻居的indegree - 1。如果indegree变成正好为0的话，那么这点就是被蹂躏完了，可以放在result和起始点queue里了。
/**
* Definition for Directed graph.
* class DirectedGraphNode {
* int label;
* ArrayList<DirectedGraphNode> neighbors;
* DirectedGraphNode(int x) { label = x; neighbors = new ArrayList<DirectedGraphNode>(); }
* };
*/
public class Solution {
/**
* @param graph: A list of Directed graph node
* @return: Any topological order for the given graph.
*/
public ArrayList<DirectedGraphNode> topSort(ArrayList<DirectedGraphNode> graph) {
HashMap<DirectedGraphNode, Integer> inDegree = countInDegree(graph);
ArrayList<DirectedGraphNode> result = new ArrayList<>();
Queue<DirectedGraphNode> queue = findHead(graph, inDegree, result);
while (!queue.isEmpty()) {
DirectedGraphNode node = queue.poll();
for (DirectedGraphNode neighbor : node.neighbors) {
inDegree.put(neighbor, inDegree.get(neighbor) - 1);
if (inDegree.get(neighbor) == 0) {
result.add(neighbor);
queue.add(neighbor);
}
}
}
return result;
}
private HashMap<DirectedGraphNode, Integer> countInDegree(ArrayList<DirectedGraphNode> graph) {
HashMap<DirectedGraphNode, Integer> inDegree = new HashMap<>();
for (DirectedGraphNode node : graph) {
for (DirectedGraphNode neighbor : node.neighbors) {
if (inDegree.containsKey(neighbor)) {
inDegree.put(neighbor, inDegree.get(neighbor) + 1);
} else {
inDegree.put(neighbor, 1);
}
}
}
return inDegree;
}
private Queue<DirectedGraphNode> findHead(ArrayList<DirectedGraphNode> graph, HashMap<DirectedGraphNode, Integer> inDegree, ArrayList<DirectedGraphNode> result) {
Queue<DirectedGraphNode> queue = new LinkedList<DirectedGraphNode>();
for (DirectedGraphNode node : graph) {
//if the node is not in the map, that means the node has 0 in-degree
if (!inDegree.containsKey(node)) {
queue.offer(node);
result.add(node);
}
}
return queue;
}
}
2. Course Schedule
top sort(dfs / bfs)
实际这题就是detect cycle on graph。用拓扑排序。
要修改的是如何记录visited的node。
visited有三种状态, unvisited, visiting, visited。
会检测到cycle的只有第二种情况，也就是在走这条dfs路的时候，回到前面的某一个点。
有点特殊的是，题目给了条件说，course number will be from 0 ~ n - 1。可以直接用int[] 来记录visited status。
DFS
(dfs is better than bfs on detecting cycle in graph)
需要注意的是，可能有些点不在map里面，那么map.get(i)可能是null 的邻居列队。
class Solution {
public boolean canFinish(int numCourses, int[][] prerequisites) {
if (prerequisites == null || prerequisites.length == 0) return true;
Map<Integer, List<Integer>> graph = convertToGraph(prerequisites);
int[] status = new int[numCourses];
for (int node : graph.keySet()) {
if (status[node] == 0) {
if (hasCycle(node, graph, status)) return false;
}
}
return true;
}
private Map<Integer, List<Integer>> convertToGraph (int[][] prerq) {
Map<Integer, List<Integer>> map = new HashMap<>();
for (int[] edge : prerq) {
int from = edge[1];
int to = edge[0];
if (!map.containsKey(from)) map.put(from, new ArrayList<Integer>());
map.get(from).add(to);
}
return map;
}
private boolean hasCycle (int node, Map<Integer, List<Integer>> graph, int[] status) {
status[node] = 1;
if (!graph.containsKey(node)) {//leaf node
status[node] = 2;
return false;
}
for (int nei : graph.get(node)) {
if (status[nei] == 1) return true;
if (status[nei] == 2) continue;
if (hasCycle(nei, graph, status)) return true;
}
status[node] = 2;
return false;
}
}
BFS
首先，在 DAG 上找环，DFS 要比 BFS 强。
其次重点注意，有向图靠 3 个状态 BFS 是不能正确判断是否有环的，要靠 indegree，一个例子是 【0, 1】 和 【1,0】，环在发现之前已经被标注为 state 2 了。
- 扫一遍所有 edge，记录每个节点的 indegree.
- 在有向无环图中，一定会存在至少一个 indegree 为 0 的起点，将所有这样的点加入queue。
- 依次处理queue里的节点，把每次poll出来的节点的 children indegree -1. 减完之后如果 child 的 indegree = 0 了，就也放入队列。
- 如果图真的没有环，可以顺利访问完所有节点，如果还有剩的，说明图中有环，因为环上节点的 indegree 没法归 0.
class Solution {
public boolean canFinish(int numCourses, int[][] prerequisites) {
if (prerequisites == null || prerequisites.length == 0) return true;
int[] indegrees = new int[numCourses];
Map<Integer, List<Integer>> graph = getGraphAndIndegree(prerequisites, indegrees);
Queue<Integer> queue = getHeads(indegrees);
bfs(queue, indegrees, graph);
//check if there is a node with indegree > 0
for (int indegree : indegrees) {
if (indegree > 0) return false;
}
return true;
}
private Map<Integer, List<Integer>> getGraphAndIndegree (int[][] prerq, int[] indegrees) {
Map<Integer, List<Integer>> map = new HashMap<>();
for (int[] edge : prerq) {
int from = edge[1];
int to = edge[0];
indegrees[to] += 1;
if (!map.containsKey(from)) map.put(from, new ArrayList<Integer>());
map.get(from).add(to);
}
return map;
}
private Queue<Integer> getHeads (int[] indegrees) {
Queue<Integer> queue = new LinkedList<>();
for (int i = 0; i < indegrees.length; i++) {
if (indegrees[i] == 0) queue.add(i);
}
return queue;
}
private void bfs (Queue<Integer> queue, int[] indegrees, Map<Integer, List<Integer>> graph) {
while (!queue.isEmpty()) {
for (int i = 0; i < queue.size(); i++) {
List<Integer> neighbors = graph.get(queue.poll());
if (neighbors == null) continue;
for (int nei : neighbors) {
indegrees[nei] -= 1;
if (indegrees[nei] == 0) queue.add(nei);
}
}
}
}
}
3. Course Schedule II
BFS
这就是又要detect cycle 又要 topo sort，所以用bfs比dfs好。
If use dfs, will miss edge case such as "3 []". The test case has the course number but the prerequisites is empty, which means there is no relation among them. If use dfs, it will return an empty array. However, in bfs, all nodes that indegree == 0 will be recorded, bfs can handle this edge case.
class Solution {
public int[] findOrder(int numCourses, int[][] prerequisites) {
if (prerequisites == null) return new int[1];
//construct graph: parent --> children + count indegree
ArrayList[] graph = new ArrayList[numCourses];
for (int i = 0; i < numCourses; i++) {
graph[i] = new ArrayList<Integer>();
}
int[] indegree = new int[numCourses];
for (int i = 0; i < prerequisites.length; i++) {
int[] pair = prerequisites[i];
int parent = pair[1];
int child = pair[0];
graph[parent].add(child);
indegree[child]++;
}
//take out all starting points
Queue<Integer> queue = new LinkedList<Integer>();
for (int i = 0; i < numCourses; i++) {
if (indegree[i] == 0) queue.add(i);
}
//bfs
int[] res = new int[numCourses];
int index = 0;
while (!queue.isEmpty()) {
int size = queue.size();
for (int i = 0; i < size; i++) {
int curr = queue.poll();
res[index++] = curr;
ArrayList<Integer> neighbors = graph[curr];
for (int nei: neighbors) {
indegree[nei]--;
if (indegree[nei] == 0) queue.add(nei);
}
}
}
if (index != numCourses) return new int[0];
return res;
}
}