leetcode797图论-对邻接矩阵和邻接表不同形式进行dfs与bfs遍历方法

给你一个有 n 个节点的 有向无环图（DAG），请你找出所有从节点 0 到节点 n-1 的路径并输出（不要求按特定顺序）

 graph[i] 是一个从节点 i 可以访问的所有节点的列表（即从节点 i 到节点 graph[i][j]存在一条有向边）。

示例 1：

输入：graph = [[1,2],[3],[3],[]]
输出：[[0,1,3],[0,2,3]]
解释：有两条路径 0 -> 1 -> 3 和 0 -> 2 -> 3

本题输入方式为邻接表方式输入

对于邻接表方式解题方法：

1、DFS遍历

2、BFS遍历

DFS遍历实现代码（基于邻接表）

class Solution {
    List<Integer> path=new ArrayList<>();
     List<List<Integer>> result=new ArrayList<>();
    public List<List<Integer>> allPathsSourceTarget(int[][] graph) {
     
     path.add(0);
     dfs(graph,0);
     return result;
    }
    private void dfs(int[][] graph,int x){
        if(x==graph.length-1){
            result.add(new ArrayList<>(path));
            return;
        }
        for(int i=0;i<graph[x].length;i++){
            path.add(graph[x][i]);
            dfs(graph,graph[x][i]);
            path.remove(path.size()-1);
        }
    }
}

BFS遍历实现代码（基于邻接表）

import java.util.*;

class Solution {
    public List<List<Integer>> allPathsSourceTarget(int[][] graph) {
        List<List<Integer>> result = new ArrayList<>();
        int target = graph.length - 1;
        
        // BFS队列：存储（当前节点，路径）
        Queue<List<Integer>> queue = new LinkedList<>();
        
        // 初始路径：0
        List<Integer> initialPath = new ArrayList<>();
        initialPath.add(0);
        queue.offer(initialPath);
        
        while (!queue.isEmpty()) {
            List<Integer> currentPath = queue.poll();
            int lastNode = currentPath.get(currentPath.size() - 1);
            
            // 到达目标节点
            if (lastNode == target) {
                result.add(new ArrayList<>(currentPath));
                continue;
            }
            
            // 遍历邻接表中的所有邻居
            for (int neighbor : graph[lastNode]) {
                List<Integer> newPath = new ArrayList<>(currentPath); // 复制路径
                newPath.add(neighbor);
                queue.offer(newPath);
            }
        }
        
        return result;
    }
}

图论题目中除了邻接表还有邻接矩阵形式，可以将邻接表转换为邻接矩阵形式更为直观清晰。

邻接矩阵方式解题方法：

1、DFS遍历

2、BFS遍历

DFS遍历实现代码（基于邻接矩阵）

import java.util.*;

class Solution {
    List<List<Integer>> result = new ArrayList<>();
    List<Integer> path = new ArrayList<>();
    int[][] adjacencyMatrix; // 邻接矩阵

    public List<List<Integer>> allPathsSourceTarget(int[][] graph) {
        // 1. 将邻接表转换为邻接矩阵
        int n = graph.length;
        adjacencyMatrix = new int[n][n];
        for (int i = 0; i < n; i++) {
            for (int neighbor : graph[i]) {
                adjacencyMatrix[i][neighbor] = 1; // 标记存在边
            }
        }

        // 2. 从节点0开始DFS
        path.add(0);
        dfs(0, n - 1);
        return result;
    }

    private void dfs(int current, int target) {
        if (current == target) {
            result.add(new ArrayList<>(path)); // 找到一条路径
            return;
        }

        for (int next = 0; next < adjacencyMatrix.length; next++) {
            if (adjacencyMatrix[current][next] == 1) { // 如果存在边
                path.add(next);
                dfs(next, target);
                path.remove(path.size() - 1); // 回溯
            }
        }
    }
}

BFS遍历实现代码（基于邻接矩阵）

import java.util.*;

class Solution {
    public List<List<Integer>> allPathsSourceTarget(int[][] graph) {
        List<List<Integer>> result = new ArrayList<>();
        int n = graph.length;
        
        // 1. 将邻接表转换为邻接矩阵
        int[][] adjacencyMatrix = new int[n][n];
        for (int i = 0; i < n; i++) {
            for (int neighbor : graph[i]) {
                adjacencyMatrix[i][neighbor] = 1;
            }
        }
        
        // 2. BFS初始化：队列存储（当前节点，路径）
        Queue<Pair<Integer, List<Integer>>> queue = new LinkedList<>();
        List<Integer> initialPath = new ArrayList<>();
        initialPath.add(0);
        queue.offer(new Pair<>(0, initialPath));
        
        // 3. BFS遍历
        while (!queue.isEmpty()) {
            Pair<Integer, List<Integer>> current = queue.poll();
            int node = current.getKey();
            List<Integer> path = current.getValue();
            
            if (node == n - 1) {
                result.add(new ArrayList<>(path)); // 找到一条路径
                continue;
            }
            
            // 遍历所有邻接节点
            for (int next = 0; next < n; next++) {
                if (adjacencyMatrix[node][next] == 1) {
                    List<Integer> newPath = new ArrayList<>(path); // 复制路径
                    newPath.add(next);
                    queue.offer(new Pair<>(next, newPath));
                }
            }
        }
        
        return result;
    }
    
    // 辅助Pair类（Java 14+可用java.util.Record替代）
    static class Pair<K, V> {
        K key;
        V value;
        Pair(K key, V value) {
            this.key = key;
            this.value = value;
        }
        K getKey() { return key; }
        V getValue() { return value; }
    }
}