package org.example.test1;

import java.util.ArrayList;
import java.util.List;
import java.util.function.Consumer;

abstract class ListGraph {
    List<List<Integer>> graphs;
    public ListGraph(int size) {
        graphs = new ArrayList<>(size);
        for (int i = 0; i < size; i++) {
            graphs.add(new ArrayList<>());
        }
    }

    public void addEdge(int start, int end) {
        graphs.get(start).add(end);
    }

    public void removeEdge(int start, int end) {
        graphs.get(start).remove(end);
    }

    abstract void traversal(Consumer<Integer> func);
}

问题：图遍历（Graph Traversal）

深度优先（DFS，Depth First Search）
广度优先（BFS，Breadth First Search）

DFS

package org.example.test1;

import java.util.LinkedList;
import java.util.Queue;
import java.util.function.Consumer;

public class DfsListGraph extends ListGraph {
    public DfsListGraph(int v) {
        super(v);
    }

    @Override
    public void traversal(Consumer<Integer> func) {
        DfsTraversal traversal = new DfsTraversal(this);
        for (int i = 0; i < graphs.size(); i++) {
            traversal.traversal(i, func);
        }
    }

    /**
     * 深度优先遍历
     */
    private static class DfsTraversal {
        ListGraph graph;
        boolean[] visited;
        // Deque<Integer> queue = new ArrayDeque<>(); // 数组，方便中间增删
        Queue<Integer> queue = new LinkedList<>(); // 链表，方便前后增删

        DfsTraversal(ListGraph graph) {
            this.graph = graph;
            visited = new boolean[graph.graphs.size()];
        }

        void traversal(int v, Consumer<Integer> func) {
            offer(v);
            while (!queue.isEmpty()) {
                func.accept(queue.poll());
                // add
                graph.graphs.get(v).forEach(neighbor -> {
                    offer(v);
                });
            }
        }

        private void offer(int v) {
            if (!visited[v]) {
                queue.offer(v);
                visited[v] = true;
            }
        }
    }
}

BFS

package org.example.test1;

import java.util.function.Consumer;

public class BfsListGraph extends ListGraph {
    public BfsListGraph(int size) {
        super(size);
    }

    @Override
    void traversal(Consumer<Integer> func) {
        BfsTraversal traversal = new BfsTraversal(this);
        for (int i = 0; i < graphs.size(); i++) {
            traversal.traversal(i, func);
        }
    }

    /**
     * 广度优先遍历
     */
    private static class BfsTraversal {
        ListGraph graph;
        boolean[] visited;

        BfsTraversal(ListGraph graph) {
            this.graph = graph;
            visited = new boolean[graph.graphs.size()];
        }

        void traversal(int v, Consumer<Integer> func) {
            if (visited[v]) {
                return;
            }
            visited[v] = true;
            func.accept(v);
            // next
            graph.graphs.get(v).forEach(neighbor -> {
                traversal(neighbor, func);
            });
        }
    }
}

遍历测试用例

package org.example.test1;

import lombok.extern.slf4j.Slf4j;
import org.junit.jupiter.api.Assertions;
import org.junit.jupiter.api.Test;

import java.util.concurrent.atomic.AtomicInteger;

@Slf4j
public class ListGraphTravelTest {
    @Test
    void testBfs() {
        ListGraph listGraph = new BfsListGraph(10);
        for (int i = 1; i < listGraph.graphs.size(); i++) {
            listGraph.addEdge(i-1, i);
        }
        listGraph.addEdge(2, 8);
        listGraph.addEdge(3, 6);
        //
        assertTravel(listGraph);
    }

    @Test
    void testDfs() {
        ListGraph listGraph = new DfsListGraph(10);
        for (int i = 1; i < listGraph.graphs.size(); i++) {
            listGraph.addEdge(0, i);
        }
        listGraph.addEdge(2, 6);
        listGraph.addEdge(6, 3);
        listGraph.addEdge(6, 9);
        //
        assertTravel(listGraph);
    }

    private static void assertTravel(ListGraph listGraph) {
        AtomicInteger count = new AtomicInteger();
        listGraph.traversal(v -> {
            log.info("{} cur: {}", listGraph.getClass().getName(), v);
            count.getAndIncrement();
        });
        Assertions.assertEquals(listGraph.graphs.size(), count.get());
    }
}