邻接表中如何进行DFS和BFS？

Question

创建邻接表：

HashMap <Interger,ArrayList<Integer>> adjList =  new HashMap<Integer,ArrayList<Integer>>();  

// adding element in Adjacency list (Undirected)

void AdjList(Integer a, Integer b){
    adjList.putIfAbsent(a, new ArrayList<>());
    adjList.get(a).add(b);
    adjList.putIfAbsent(b, new ArrayList<>());
    adjList.get(b).add(a);
} 

如何在其中进行 DFS 和 BFS？

我尝试过这样的事情。如何循环通过？

void DFS(Integer i) {
    //getting first element from adjlist
    if (adjList.containsKey(i)) {
        Integer ele1 = adjList.get(i).get(adjList.get(i).size() - 1);
        if (adjList.containsKey(ele1)) {
            Integer ele2 = adjList.get(ele1).get(adjList.get(ele1).size() - 1);
        }
    }
}

Answer 1

您正在正确创建邻接列表（但最好将此函数命名为 adjList），但对于 BFS 和 DFS，您需要每个节点都有一个已访问状态，并迭代一个节点的所有邻居节点，并对它们递归执行 BFS/DFS。

import java.util.*;

public class Graph {
    public static void main(String[] args) {
        Graph g = new Graph();
        g.adjList(0, 1);
        g.adjList(0, 2);
        g.adjList(1, 3);
        g.adjList(2, 3);

        g.DFS(0);
        g.BFS(0);

    }

    HashMap<Integer, ArrayList<Integer>> adjList = new HashMap<>();

    // adding element in Adjacency list (Undirected)

    void adjList(Integer a, Integer b) {
        adjList.putIfAbsent(a, new ArrayList<>());
        adjList.get(a).add(b);
        adjList.putIfAbsent(b, new ArrayList<>());
        adjList.get(b).add(a);
    }

    void dfsRecursive(int v, boolean[] visited) {
        visited[v] = true;
        System.out.print(v + " ");

        for (int n : adjList.get(v)) {
            if (!visited[n])
                dfsRecursive(n, visited);
        }
    }

    void DFS(int s) {
        boolean[] visited = new boolean[adjList.size()];
        System.out.print("DFS: ");
        dfsRecursive(s, visited);
        System.out.println();

    }

    void BFS(int s) {
        boolean[] visited = new boolean[adjList.size()];

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

        visited[s] = true;
        queue.add(s);
        System.out.print("BFS: ");
        while (queue.size() != 0) {
            s = queue.poll();
            System.out.print(s + " ");

            for (int n : adjList.get(s)) {
                if (!visited[n]) {
                    visited[n] = true;
                    queue.add(n);
                }
            }
        }
    }
}

上述代码的输出将是：

DFS: 0 1 3 2 
BFS: 0 1 2 3