Как сделать BFS или DFS в ориентированном графе из определенной вершины с некоторой вершиной, имеющей степень 0?

Question

Каков порядок обходов DFS или BFS для графов, когда могут быть вершины, у которых есть степени 0, если мы хотим сделать DFS / BFS из данной вершины {0..n-1}.

Ниже приведена одна реализация BFS для графа

import java.util.LinkedList;
import java.util.ListIterator;
import java.util.Queue;

public class BreadthFirstSearch {

    static class Graph {
        int V;
        LinkedList[] vertexList;

        Graph(int v) {
            this.V = v;
            vertexList = new LinkedList[v];

            for (int i = 0; i < v; i++) {
                vertexList[i] = new LinkedList<>();
            }
        }
    }

    private void addEdge(Graph graph, int src, int dest) {
        graph.vertexList[src].add(dest); // Directed Graph Only
    }

    private void bfs(Graph graph, int vertex) {

        if (vertex > graph.V) {
            throw new IllegalArgumentException("Value not defined");
        }
        boolean visited[] = new boolean[graph.V];

        Queue<Integer> queue = new LinkedList<>();

        queue.add(vertex);
        while (!queue.isEmpty()) {
            int a = queue.poll();
            if (!visited[a]) {
                System.out.print(a + " ");
                visited[a] = true;

            }
            for (Object o : graph.vertexList[a]) {
                int n = (int) o;
                if (!visited[n]) {
                    queue.add(n);
                }
            }
        }
    }

    private void traverseGraphList(Graph G) {
        int i = 0;
        for (LinkedList list : G.vertexList) {
            ListIterator itr = list.listIterator();
            System.out.print("src: " + i++ + " ");
            while (itr.hasNext()) {
                System.out.print(" -> " + itr.next());
            }
            System.out.println();
        }
    }

    public static void main(String args[]) {
        BreadthFirstSearch g = new BreadthFirstSearch();
        int n = 8;
        Graph graph = new Graph(n);
        g.addEdge(graph, 0, 1);
        g.addEdge(graph, 0, 2);
        g.addEdge(graph, 1, 2);
        g.addEdge(graph, 2, 0);
        g.addEdge(graph, 2, 3);
        g.addEdge(graph, 3, 3);
        g.addEdge(graph, 3, 4);
        g.addEdge(graph, 5, 4);
        g.addEdge(graph, 5, 6);
        g.addEdge(graph, 7, 6);
        System.out.println("BFS starting from node 2");
        g.bfs(graph, 2);

        System.out.println();
        g.traverseGraphList(graph);
        //2 0 3 1 4

    }
}

Вывод 2 0 3 1 4

Answer 1

Итак, насколько я вижу, реализация BFS в порядке. ИМО, его вывод - это то, что я ожидал бы для стандартной реализации алгоритма, когда для входа для начального вызова установлено значение 2 для параметра vertex.

При этом не все ориентированные графы полностью проходимы из любого данного узла. Основываясь на направлениях стрелок, когда я начинаю движение в узле 2, я действительно могу добраться только до узлов 0, 1, 3 и 4. Узлы 5, 6 и 7 недоступны из узла 2, поскольку 5 указывает на 4, но 4 не указывает на 5.

Если вы хотите действительно пройти весь граф, вам нужно изменить алгоритм BFS так, чтобы, если в конце текущей реализации длина массива visited была меньше длины массива vertexList, то вам нужно будет найти следующий элемент в vertexList, которого нет в visited, пока длины двух массивов не совпадут.

Answer 2

Если вы хотите обойти все узлы графа, то вы должны знать, что, поскольку есть узлы, которые недоступны из выбранного вами узла root, вы не сможете обойти их при использовании одного BFS / DFS.

Порядок следования узлов зависит от реализации вашей BFS / DFS. В вашем случае это зависит от порядка, в который вы вставляете каждый узел в список смежности.

Если вы хотите пройти по всему графу, вам следует указать, какие узлы посещались, а затем запустить BFS / DFS для каждого не посещаемый узел (например, используя al oop). В частности, порядок появления пройденных узлов снова зависит от порядка элементов, на которых вы фактически будете l oop.