Using an adjacency matrix vs adjacency list when sorting

Question

I want to implement a topological sort based on the DFS method:

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

However im unsure how the implementation differs when using as adjacency matrix rather than a list. Which I have stored as:

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

how would I use an adjacency matrix in place of the adjacency list as in lines 16, 29.

Thank You

Answer 1

That list does not need to be changed in my opinion, you need to record the post order of the visited vertices anyway.

The adjacency matrix is going to affect how you iterate through neighbour vertices of u, specifically this line for (int v : graph[u]) needs to be changed to something like:

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