Использование матрицы смежности и списка смежности при сортировке

Я хочу реализовать топологическую сортировку на основе метода 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.

Благодарю вас


java adjacency-matrix topological-sort
person Silverfin    schedule 23.05.2016    source источник
comment
строки 16,29... Я не вижу номеров строк в коде, очень сложно найти указанные строки.   -  person xiaofeng.li    schedule 23.05.2016
comment
@LukeLee извиняется за то, что я ссылаюсь на список массивов в методе: List‹Integer› res = new ArrayList‹›(); g[i] = новый ArrayList‹›();   -  person Silverfin    schedule 23.05.2016

Ответы (1)


arrow_upward
0
arrow_downward

На мой взгляд, этот список не нужно менять, вам все равно нужно записать порядок постов посещенных вершин.

Матрица смежности повлияет на то, как вы перебираете соседние вершины 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
    }
}
person xiaofeng.li    schedule 23.05.2016