Как сделать DFS и BFS в списке смежности?

Создание списка смежности

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

java hashmap depth-first-search breadth-first-search

23.03.2022 06:38

Пользовательский скаляр GraphQL

Листовые узлы системы типов GraphQL называются скалярами. Достигнув скалярного типа, невозможно спуститься дальше по иерархии типов. Скалярный тип...

Как вычислять биты и понимать побитовые операторы в Java - объяснение с примерами

В компьютерном программировании биты играют важнейшую роль в представлении и манипулировании данными на двоичном уровне. Побитовые операции...

Поднятие тревоги для долго выполняющихся методов в Spring Boot

Приходилось ли вам сталкиваться с требованиями, в которых вас могли попросить поднять тревогу или выдать ошибку, когда метод Java занимает больше...

Принятие принципов SOLID в Spring Boot: Создание обслуживаемых и масштабируемых приложений

Коллекции (ArrayList , HashSet , HashMap)

Полный курс Java для разработчиков веб-сайтов и приложений

Получите сертификат Java Web и Application Developer, используя наш курс.

Перейти к ответу Данный вопрос помечен как решенный

Ответы 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);
                }
            }
        }
    }
}

Вывод приведенного выше кода будет таким: