Created
May 12, 2017 22:02
-
-
Save sorindragan/e88f53ad52112cbfc3ab47cd80e6225d to your computer and use it in GitHub Desktop.
Topological Sort in Java
This file contains bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters.
Learn more about bidirectional Unicode characters
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