BFS обход ориентированного графа из заданного узла

Question

Мое понимание базового поиска в ширину обхода для графика:

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  

Однако, если мы должны пройти направленный граф изданный узел и не все узлы доступны из данного узла (прямо или косвенно), как мы используем BFS для обхода графика этой ситуации?

Не могли бы вы также объяснить в этом графе:

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

Здесь, если начальный узел b, мы никогда не выводим a и c.

Я что-то упустил в алгоритме?

Я использовал HashMap<String, ArrayList> adj = new HashMap();, чтобы создать список смежности для хранения графа.

Answer 1

Тем не менее, если мы должны пройти НАПРАВЛЕННЫЙ граф из заданного узла, и не все узлы доступны из данного узла [прямо или косвенно], как мы используем BFS для одного и того же.

Алгоритм поиска пересекает график. Если у вас есть ребра, которые не могут быть пройдены, и, следовательно, узлы, которые не могут быть достигнуты, поиск просто не найдет их.

Answer 2

Вы правы в своем понимании, за исключением для части «Начать с любого узла» - обратный путь BFS должен начинаться с корневого узла. Таким образом, в вашем примере вы должны иметь , чтобы начать с узла a, иначе, как вы сказали, вы никогда не посетите его.