java - 如何在有向图中从特定顶点执行 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/时遍历它们DFS。

遍历节点的顺序取决于 BFS/DFS 的实现。在您的情况下，这取决于您将每个节点插入邻接列表的顺序。

如果你想遍历整个图，那么你应该维护哪些节点被访问，然后对每个未访问的节点运行 BFS/DFS(例如通过使用循环)。特别是，遍历节点的出现顺序再次取决于您实际循环的项目的顺序。