Skip to content

Instantly share code, notes, and snippets.

@sorindragan
Created May 12, 2017 22:02
Show Gist options
  • Save sorindragan/e88f53ad52112cbfc3ab47cd80e6225d to your computer and use it in GitHub Desktop.
Save sorindragan/e88f53ad52112cbfc3ab47cd80e6225d to your computer and use it in GitHub Desktop.
Topological Sort in Java
import java.io.BufferedReader;
import java.io.FileReader;
import java.io.IOException;
import java.util.LinkedList;
import java.util.Stack;
import java.util.StringTokenizer;
class GeneratedGraph {
public boolean error = false; // eroare graf ciclic
public int n; // numar de noduri
public LinkedList<Integer>[] list;// lista de adiacenta
@SuppressWarnings("unchecked")
GeneratedGraph(int n) {
this.n = n;
list = new LinkedList[n];
for (int i = 0; i < n; i++) {
list[i] = new LinkedList<>();
}
}
void addEdge(int a, int b) {
list[a].add(b); // adauga muchie de la a la b
}
void exploreForTopologicalSort(Stack<Integer> s, int[] visited, int x) {
// marcheaza ca vizitat
visited[x] = 1; // gri
for (int iter : list[x]) {
if (visited[iter] == 1) {
error = true;
break;
}
if (visited[iter] == 0) {
exploreForTopologicalSort(s, visited, iter);
}
}
visited[x] = 2;// negru
s.push(x);
}
void topologicalSort() {
Stack<Integer> s = new Stack<Integer>();
int[] visited2 = new int[n];
for (int i = 0; i < n; i++) {
visited2[i] = 0;// alb
}
for (int i = 0; i < n; i++) {
if (visited2[i] == 0) {
exploreForTopologicalSort(s, visited2, i);
if (error == true) {
System.out.println("Graf Ciclic");
return;
}
}
}
while (!s.empty()) {
System.out.print(s.pop() + " ");
}
}
}
public class Permutari {
private static BufferedReader br;
public static void main(String[] args) throws IOException {
FileReader file = new FileReader("file");
br = new BufferedReader(file);
GeneratedGraph g = new GeneratedGraph(n);
g.addEdge(1,2);
//...
// sortarea topologica pe graf
g.topologicalSort();
br.close();
file.close();
}
}
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment