邻接表中的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) {
    //gettting 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

邻接表中的DFS和BFS如何做？

How to do DFS and BFS in Adjacency List?

java

hashmap

breadth-first-search

depth-first-search