-
Notifications
You must be signed in to change notification settings - Fork 187
/
Graph.java
96 lines (79 loc) · 2.18 KB
/
Graph.java
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
import java.util.*;
class Graph {
int V;
List<Integer> adj[];
public Graph(int V)
{
this.V = V;
adj = new ArrayList[V];
for (int i = 0; i < V; i++)
adj[i] = new ArrayList<Integer>();
}
// Function to add an edge to graph
public void addEdge(int u, int v)
{
adj[u].add(v);
}
public void topologicalSort()
{
int indegree[] = new int[V];
for (int i = 0; i < V; i++) {
ArrayList<Integer> temp
= (ArrayList<Integer>)adj[i];
for (int node : temp) {
indegree[node]++;
}
}
// Create a queue and enqueue
// all vertices with indegree 0
Queue<Integer> q
= new LinkedList<Integer>();
for (int i = 0; i < V; i++) {
if (indegree[i] == 0)
q.add(i);
}
// Initialize count of visited vertices
int cnt = 0;
Vector<Integer> topOrder = new Vector<Integer>();
while (!q.isEmpty()) {
int u = q.poll();
topOrder.add(u);
their in-degree
// by 1
for (int node : adj[u]) {
// If in-degree becomes zero,
// add it to queue
if (--indegree[node] == 0)
q.add(node);
}
cnt++;
}
// Check if there was a cycle
if (cnt != V) {
System.out.println(
"There exists a cycle in the graph");
return;
}
// Print topological order
for (int i : topOrder) {
System.out.print(i + " ");
}
}
}
// Driver program to test above functions
class Main {
public static void main(String args[])
{
// Create a graph given in the above diagram
Graph g = new Graph(6);
g.addEdge(5, 2);
g.addEdge(5, 0);
g.addEdge(4, 0);
g.addEdge(4, 1);
g.addEdge(2, 3);
g.addEdge(3, 1);
System.out.println(
"Following is a Topological Sort");
g.topologicalSort();
}
}