Topological sort: Difference between revisions
Content added Content deleted
(→{{header|Java}}: adjacency entries are only 1 or 0, so are booleans) |
|||
Line 2,389: | Line 2,389: | ||
class Graph { |
class Graph { |
||
String[] vertices; |
String[] vertices; |
||
boolean[][] adjacency; |
|||
int numVertices; |
int numVertices; |
||
Line 2,395: | Line 2,395: | ||
vertices = s.split(","); |
vertices = s.split(","); |
||
numVertices = vertices.length; |
numVertices = vertices.length; |
||
adjacency = new |
adjacency = new boolean[numVertices][numVertices]; |
||
for (int[] edge : edges) |
for (int[] edge : edges) |
||
adjacency[edge[0]][edge[1]] = |
adjacency[edge[0]][edge[1]] = true; |
||
} |
} |
||
Line 2,430: | Line 2,430: | ||
boolean hasDependency(Integer r, List<Integer> todo) { |
boolean hasDependency(Integer r, List<Integer> todo) { |
||
for (Integer c : todo) { |
for (Integer c : todo) { |
||
if (adjacency[r][c] |
if (adjacency[r][c]) |
||
return true; |
return true; |
||
} |
} |