排序时使用邻接矩阵与邻接表

Question

我想实现基于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 行中的邻接列表。

谢谢

Answer 1

这个列表我觉得不用改，反正你要记录下访问过的顶点的post顺序。

邻接矩阵将影响您遍历 u 的相邻顶点的方式，特别是这一行 for (int v : graph[u]) 需要更改为：

for (int v = 0; v < adjMatrix[u].length; v++) {
    if (adjMatrix[u][v] != null && !used(v))
    // If there exists an edge between (u, v), and haven't visited v yet.
    {
         dfs(adjMatrix, used, res, v); // visit v
    }
}

排序时使用邻接矩阵与邻接表

Using an adjacency matrix vs adjacency list when sorting

java

topological-sort

adjacency-matrix