成人无码视频,亚洲精品久久久久av无码,午夜精品久久久久久毛片,亚洲 中文字幕 日韩 无码

資訊專欄INFORMATION COLUMN

[LintCode] Topological Sorting [BFS & DFS]

draveness / 2943人閱讀

摘要：當(dāng)隊(duì)列非空時(shí)，拿出最后放入的元素。若減后入度為，則這個(gè)結(jié)點(diǎn)遍歷完成，放入結(jié)果數(shù)組和隊(duì)列。遞歸函數(shù)去遍歷的，繼續(xù)在中標(biāo)記，使得所有點(diǎn)只遍歷一次。最深的點(diǎn)最先，根結(jié)點(diǎn)最后，加入結(jié)果數(shù)組的頭部處。

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，存儲(chǔ)graph中所有neighbors結(jié)點(diǎn)的入度。
然后建立空的隊(duì)列q，將所有非依賴結(jié)點(diǎn)（如例子中的0結(jié)點(diǎn)，沒有其它元素指向它，也可以理解為根節(jié)點(diǎn)）放入隊(duì)列q和結(jié)果數(shù)組res。
當(dāng)隊(duì)列q非空時(shí)，拿出q最后放入的元素cur。然后遍歷cur的所有neighbors結(jié)點(diǎn)neighbor，并將遍歷后的neighbor入度減1。若減1后入度為0，則這個(gè)結(jié)點(diǎn)遍歷完成，放入結(jié)果數(shù)組res和隊(duì)列q。

再看DFS的做法：
建立HashSet visited，標(biāo)記遍歷過的點(diǎn)node。遞歸dfs函數(shù)去遍歷node的neighbors，繼續(xù)在visited中標(biāo)記，使得所有點(diǎn)只遍歷一次。
最深的點(diǎn)最先，根結(jié)點(diǎn)最后，加入結(jié)果數(shù)組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<>();
        //把除了頭結(jié)點(diǎn)外的結(jié)點(diǎn)放入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);
            }
        }
        //找到頭結(jié)點(diǎn)，放入queue和結(jié)果數(shù)組res
        for (DirectedGraphNode n: graph) {
            if (!map.containsKey(n)) {
                queue.offer(n);
                res.add(n);
            }
        }
        //對queue中的結(jié)點(diǎn)的neighbors進(jìn)行BFS（入度減1），當(dāng)neighbor的入度減小為0，放入queue和結(jié)果數(shù)組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);
    }
}

文章版權(quán)歸作者所有，未經(jīng)允許請勿轉(zhuǎn)載,若此文章存在違規(guī)行為，您可以聯(lián)系管理員刪除。

轉(zhuǎn)載請注明本文地址：http://m.hztianpu.com/yun/65740.html

相關(guān)文章

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

    摘要：開始看這道題目的時(shí)候，沒有看懂和的作用。然后對這個(gè)放入的結(jié)點(diǎn)開始操作遍歷的所有，當(dāng)前遍歷到的的叫做。當(dāng)完成，則中沒有新的結(jié)點(diǎn)了，退出循環(huán)。返回在中更新過的，結(jié)束。 Problem Clone an undirected graph. Each node in the graph contains a label and a list of its neighbors. We use #...

    fredshare 評論0 收藏0

  • DOM樹遍歷之JS實(shí)現(xiàn)DFS&amp;BFS

    摘要：對于上面例子遍歷結(jié)果應(yīng)為則總是先遍歷當(dāng)前層級的所有節(jié)點(diǎn)，只有當(dāng)當(dāng)前層級所有節(jié)點(diǎn)都遍歷結(jié)束后才會(huì)進(jìn)入下一層級。 我們一般可以采用DFS（深度優(yōu)先遍歷）和BFS（廣度優(yōu)先遍歷）來遍歷DOM樹 介紹 DFS & BFS 我們來結(jié)合具體例子進(jìn)行分析，給出HTML代碼片段如下： DFS總是先進(jìn)入下一...

    imccl 評論0 收藏0

  • DOM樹遍歷之JS實(shí)現(xiàn)DFS&amp;BFS

    摘要：對于上面例子遍歷結(jié)果應(yīng)為則總是先遍歷當(dāng)前層級的所有節(jié)點(diǎn)，只有當(dāng)當(dāng)前層級所有節(jié)點(diǎn)都遍歷結(jié)束后才會(huì)進(jìn)入下一層級。 我們一般可以采用DFS（深度優(yōu)先遍歷）和BFS（廣度優(yōu)先遍歷）來遍歷DOM樹 介紹 DFS & BFS 我們來結(jié)合具體例子進(jìn)行分析，給出HTML代碼片段如下： DFS總是先進(jìn)入下一...

    fengxiuping 評論0 收藏0

  • js版本的BFS&amp;DFS

    摘要：隊(duì)列棧隊(duì)列是先進(jìn)先出，后進(jìn)后出，常用的操作是取第一個(gè)元素尾部加入一個(gè)元素。棧是后進(jìn)先出，就像一個(gè)垃圾桶，后入的垃圾先被倒出來。遍歷中間過程，每一個(gè)節(jié)點(diǎn)入棧的時(shí)候是灰色的，出棧的時(shí)候是黑色的。 0. 前言 廣度優(yōu)先搜索(BFS)和深度優(yōu)先搜索(DFS)，大家可能在oj上見過，各種求路徑、最短路徑、最優(yōu)方法、組合等等。于是，我們不妨動(dòng)手試一下js版本怎么玩。 1.隊(duì)列、棧 隊(duì)列是先進(jìn)先出，...

    劉福 評論0 收藏0

  • [LintCode] Route Between Two Nodes in Graph [DFS/B

    摘要：若為有向圖的終點(diǎn)，經(jīng)過下一次，會(huì)指向，返回否則，只要所有的深度搜索中包含滿足條件的結(jié)果，就返回。 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 評論0 收藏0

發(fā)表評論

0條評論

閱讀需要支付1元查看
<