[LintCode] Topological Sorting [BFS & DFS]

draveness 发布于2019-08-14 15:24 / 2875人阅读

摘要：当队列非空时，拿出最后放入的元素。若减后入度为，则这个结点遍历完成，放入结果数组和队列。递归函数去遍历的，继续在中标记，使得所有点只遍历一次。最深的点最先，根结点最后，加入结果数组的头部处。

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 visited，标记遍历过的点node。递归dfs函数去遍历node的neighbors，继续在visited中标记，使得所有点只遍历一次。
最深的点最先，根结点最后，加入结果数组res的头部（index = 0处）。

Solution

BFS

public class Solution {
    public ArrayList topSort(ArrayList graph) {
        ArrayList res = new ArrayList<>();
        Queue queue = new LinkedList<>();
        Map 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 topSort(ArrayList graph) {
        ArrayList res = new ArrayList();
        Set visited = new HashSet();
        for (DirectedGraphNode node: graph) {
            if (!visited.contains(node)) {
                dfs(node, visited, res);
            }
        }
        return res;
    }
    public void dfs(DirectedGraphNode node, Set visited, List res) {
        visited.add(node);
        for (DirectedGraphNode n: node.neighbors) {
            if (!visited.contains(n)) dfs(n, visited, res);
        }
        res.add(0, node);
    }
}

云服务器 GPU云服务器 Sorting Topological BFS LintCode

文章版权归作者所有，未经允许请勿转载,若此文章存在违规行为，您可以联系管理员删除。

转载请注明本文地址：https://www.ucloud.cn/yun/65740.html

[LintCode/LeetCode] Clone Graph [BFS/DFS]

摘要：开始看这道题目的时候，没有看懂和的作用。然后对这个放入的结点开始操作遍历的所有，当前遍历到的的叫做。当完成，则中没有新的结点了，退出循环。返回在中更新过的，结束。 Problem Clone an undirected graph. Each node in the graph contains a label and a list of its neighbors. We use #...

fredshare 2019-08-14 15:23 评论0 收藏0
DOM树遍历之JS实现DFS&amp;BFS

摘要：对于上面例子遍历结果应为则总是先遍历当前层级的所有节点，只有当当前层级所有节点都遍历结束后才会进入下一层级。我们一般可以采用DFS（深度优先遍历）和BFS（广度优先遍历）来遍历DOM树介绍 DFS & BFS 我们来结合具体例子进行分析，给出HTML代码片段如下： DFS总是先进入下一...

imccl 2019-08-20 15:52 评论0 收藏0
DOM树遍历之JS实现DFS&amp;BFS

摘要：对于上面例子遍历结果应为则总是先遍历当前层级的所有节点，只有当当前层级所有节点都遍历结束后才会进入下一层级。我们一般可以采用DFS（深度优先遍历）和BFS（广度优先遍历）来遍历DOM树介绍 DFS & BFS 我们来结合具体例子进行分析，给出HTML代码片段如下： DFS总是先进入下一...

fengxiuping 2019-08-01 16:40 评论0 收藏0
js版本的BFS&amp;DFS

摘要：队列栈队列是先进先出，后进后出，常用的操作是取第一个元素尾部加入一个元素。栈是后进先出，就像一个垃圾桶，后入的垃圾先被倒出来。遍历中间过程，每一个节点入栈的时候是灰色的，出栈的时候是黑色的。 0. 前言广度优先搜索(BFS)和深度优先搜索(DFS)，大家可能在oj上见过，各种求路径、最短路径、最优方法、组合等等。于是，我们不妨动手试一下js版本怎么玩。 1.队列、栈队列是先进先出，...

刘福 2019-08-22 16:49 评论0 收藏0
[LintCode] Route Between Two Nodes in Graph [DFS/B

摘要：若为有向图的终点，经过下一次，会指向，返回否则，只要所有的深度搜索中包含满足条件的结果，就返回。 Problem Given a directed graph, design an algorithm to find out whether there is a route between two nodes. Example Given graph: A----->B----->C ...

187J3X1 2019-08-14 15:21 评论0 收藏0