向图的从一个给定节点的BFS遍历 [英] BFS traversal of directed graph from a given node

问题描述

我的理解基本的广度优先搜索的遍历一个图是：

  BFS
    开始从任何节点。
    它添加到队列中。
    将它添加到访问数组。

    虽然队列不为空：
        删除头从队列中;
        打印节点。

        添加所有未访问的直接subchilds到阙;
        作为参观纪念他们
 

不过，如果我们从给定的节点遍历的针对的图形，而不是所有节点在给定的节点（直接或间接）访问，我们如何使用BFS遍历的图这种情况呢？

能否请您在此图解释以及：

  A =＆GT; B =＆GT; D =＆GT; E =＆GT; ð
A =＆GT; C =＆GT; ð
 

下面如果起始节点是 B ，我们从来不打印 A 和 C 。

我缺少的东西的算法？

我用的HashMap＆LT;字符串，ArrayList的＆GT; ADJ =新的HashMap（）; 以创建邻接表来存储图

解决方案

  

不过，如果我们从给定的节点遍历有向图，而不是所有节点都可以访问给定的节点[直接或间接]我们如何使用BFS为同一个。

一个搜索算法遍历一个图。如果您有无法到达的边缘，无法穿越，因此节点，搜索将根本找不到他们。

My understanding of basic breadth-first search traversal for a graph is:

BFS        
    Start from any node. 
    Add it to queue. 
    Add it to visited array.

    While queue is not empty:
        Remove head from queue; 
        Print node.

        add all unvisited direct subchilds to que; 
        mark them as visited  

However, if we have to traverse a directed graph from a given node and not all nodes are accessible from the given node (directly or indirectly), how do we use BFS for traversing the graph of this situation?

Can you please explain in this graph as well:

a=> b => d => e => d  
a=> c => d

Here if the starting node is b , we never print a and c.

Am I missing something in the algorithm?

I used HashMap<String, ArrayList> adj = new HashMap(); to create the adjacency list to store graph.

解决方案

However, if we have to traverse a DIRECTED graph from a given node and not all nodes are accessible from the given node [directly or indirectly] how do we use BFS for the same.

A search algorithm traverses a graph. If you have edges that cannot be traversed and thus nodes that cannot be reached, the search will simply not find them.

这篇关于向图的从一个给定节点的BFS遍历的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！