脚本宝典收集整理的这篇文章主要介绍了[LintCode] Topological Sorting [BFS & DFS],脚本宝典觉得挺不错的,现在分享给大家,也给大家做个参考。
Problem
Given an directed graph, a topological order of the graph nodes is defined as follow:
For each directed edge A -> B
in graph, A must before B in the order list.
The first node in the order can be any node in the graph with no nodes direct to it.
Find any topological order for the given graph.
Notice
You can assume that there is at least one topological order in the graph.
Example
For graph as follow:
The topological order can be:
[0, 1, 2, 3, 4, 5]
[0, 2, 3, 1, 5, 4]
...
Challenge
Can you do it in both BFS and DFS?
Note
先看BFS的做法:
建立哈希表map
,存储graph
中所有neighbors
结点的入度。
然后建立空的队列q
,将所有非依赖结点(如例子中的0
结点,没有其它元素指向它,也可以理解为根节点)放入队列q
和结果数组res
。
当队列q
非空时,拿出q
最后放入的元素cur
。然后遍历cur
的所有neighbors
结点neighbor
,并将遍历后的neighbor
入度减1
。若减1
后入度为0
,则这个结点遍历完成,放入结果数组res
和队列q
。
再看DFS的做法:
建立HashSet<DirectedGraphNode> visited
,标记遍历过的点node
。递归dfs函数去遍历node
的neighbors
,继续在visited
中标记,使得所有点只遍历一次。
最深的点最先,根结点最后,加入结果数组res
的头部(index = 0处)。
Solution
BFS
public class Solution {
public ArrayList<DirectedGraphNode> topSort(ArrayList<DirectedGraphNode> graph) {
ArrayList<DirectedGraphNode> res = new ArrayList<>();
Queue<DirectedGraphNode> queue = new LinkedList<>();
Map<DirectedGraphNode, Integer> map = new HashMap<>();
//把除了头结点外的结点放入map
for (DirectedGraphNode n: graph) {
for (DirectedGraphNode node: n.neighbors) {
if (!map.containsKey(node)) map.put(node, 1);
else map.put(node, map.get(node)+1);
}
}
//找到头结点,放入queue和结果数组res
for (DirectedGraphNode n: graph) {
if (!map.containsKey(n)) {
queue.offer(n);
res.add(n);
}
}
//对queue中的结点的neighbors进行BFS(入度减1),当neighbor的入度减小为0,放入queue和结果数组res
while (!queue.isEmpty()) {
DirectedGraphNode n = queue.poll();
for (DirectedGraphNode node: n.neighbors) {
map.put(node, map.get(node)-1);
if (map.get(node) == 0) {
res.add(node);
queue.offer(node);
}
}
}
return res;
}
}
DFS Recursion
public class Solution {
public ArrayList<DirectedGraphNode> topSort(ArrayList<DirectedGraphNode> graph) {
ArrayList<DirectedGraphNode> res = new ArrayList();
Set<DirectedGraphNode> visited = new HashSet();
for (DirectedGraphNode node: graph) {
if (!visited.contains(node)) {
dfs(node, visited, res);
}
}
return res;
}
public void dfs(DirectedGraphNode node, Set<DirectedGraphNode> visited, List<DirectedGraphNode> res) {
visited.add(node);
for (DirectedGraphNode n: node.neighbors) {
if (!visited.contains(n)) dfs(n, visited, res);
}
res.add(0, node);
}
}
以上是脚本宝典为你收集整理的[LintCode] Topological Sorting [BFS & DFS]全部内容,希望文章能够帮你解决[LintCode] Topological Sorting [BFS & DFS]所遇到的问题。
本图文内容来源于网友网络收集整理提供,作为学习参考使用,版权属于原作者。
如您有任何意见或建议可联系处理。小编QQ:384754419,请注明来意。