有 Java 编程相关的问题?

你可以在下面搜索框中键入要查询的问题!

排序时使用邻接矩阵与邻接列表的java

我想基于DFS方法实现拓扑排序:

import java.util.*;

public class TopologicalSort {

  static void dfs(List<Integer>[] graph, boolean[] used, List<Integer> res, int u) {
    used[u] = true;
    for (int v : graph[u])
      if (!used[v])
        dfs(graph, used, res, v);
    res.add(u);
  }

  public static List<Integer> topologicalSort(List<Integer>[] graph) {
    int n = graph.length;
    boolean[] used = new boolean[n];
    List<Integer> res = new ArrayList<>();
    for (int i = 0; i < n; i++)
      if (!used[i])
        dfs(graph, used, res, i);
    Collections.reverse(res);
    return res;
  }

  // Usage example
  public static void main(String[] args) {
    int n = 3;
    List<Integer>[] g = new List[n];
    for (int i = 0; i < n; i++) {
      g[i] = new ArrayList<>();
    }
    g[2].add(0);
    g[2].add(1);
    g[0].add(1);

    List<Integer> res = topologicalSort(g);
    System.out.println(res);
  }
}

然而,我不确定当使用邻接矩阵而不是列表时,实现有何不同。我将其存储为:

private Edge[][] adjMatrix;       // Adjacency matrix

如何使用邻接矩阵来代替第16、29行中的邻接列表

谢谢!


共 (0) 个答案