Creating a Adjacency List

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);
} 

How to do DFS and BFS in this?

I've tried something like this. how to loop through ?

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);
        }
    }
}

CodePudding user response：

You are creating Adjacency List correctly(but it is better to name this function something like adjList), but for both BFS and DFS, you need to have a visited status per node, and iterate over all nodes neighbors of a node and do the BFS/DFS recursively on them.

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);
                }
            }
        }
    }
}

The output of above code would be:

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