Skip to content

Commit 7df387a

Browse files
darpanjboradarpanjbora
committed
🔥 BFS DFS and Topological sorting
1 parent 854deb3 commit 7df387a

File tree

3 files changed

+245
-0
lines changed

3 files changed

+245
-0
lines changed

‎Graph Algorithms/BFS.java

Lines changed: 69 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,69 @@
1+
/**
2+
* Time Complexity: O(V+E) where V is number of vertices in the graph and
3+
* E is number of edges in the graph.
4+
*/
5+
6+
7+
import java.util.*;
8+
import java.io.*;
9+
10+
@SuppressWarnings("unchecked")
11+
12+
class BFS {
13+
int vertices;
14+
LinkedList<Integer>[] adjacencyList ;
15+
16+
BFS(int vertices) {
17+
this.vertices = vertices;
18+
adjacencyList = new LinkedList[vertices];
19+
for(int i=0; i<vertices; i++)
20+
adjacencyList[i] = new LinkedList();
21+
}
22+
23+
void addEdge(int v, int w){
24+
adjacencyList[v].add(w);
25+
}
26+
27+
void BFSTraversal(int source){
28+
29+
boolean[] visited = new boolean[vertices];
30+
LinkedList<Integer> queue = new LinkedList<Integer>();
31+
32+
visited[source] = true;
33+
queue.add(source);
34+
System.out.print("BFS TRAVERSAL OF THE GRAPH : ");
35+
36+
while(!queue.isEmpty()){
37+
38+
int elem = queue.poll();
39+
System.out.print(elem+" ");
40+
41+
Iterator<Integer> iterator = adjacencyList[elem].listIterator();
42+
43+
while(iterator.hasNext())
44+
{
45+
int num = iterator.next();
46+
if(!visited[num]){
47+
visited[num] = true;
48+
queue.add(num);
49+
}
50+
}
51+
}
52+
System.out.print("\n");
53+
}
54+
55+
public static void main(String[] args) {
56+
BFS bfs = new BFS(7);
57+
58+
bfs.addEdge(1, 2);
59+
bfs.addEdge(1, 3);
60+
bfs.addEdge(2, 4);
61+
bfs.addEdge(2, 5);
62+
bfs.addEdge(3, 5);
63+
bfs.addEdge(4, 5);
64+
bfs.addEdge(4, 6);
65+
bfs.addEdge(5, 6);
66+
67+
bfs.BFSTraversal(1);
68+
}
69+
}

‎Graph Algorithms/DFS.java

Lines changed: 86 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,86 @@
1+
/**
2+
* Time Complexity: O(V+E) where V is number of vertices in the graph and
3+
* E is number of edges in the graph.
4+
*
5+
* Following are the problems that use DFS as a bulding block :
6+
* 1) For an unweighted graph, DFS traversal of the graph produces the minimum spanning tree and all pair shortest path tree.
7+
* 2) Detecting cycle in a graph
8+
* 3) Path Finding
9+
* 4) Topological Sorting
10+
* 5) To test if a graph is bipartite
11+
* 6) Finding Strongly Connected Components of a graph.
12+
* 7) Solving puzzles with only one solution, such as mazes. (DFS can be adapted to find all solutions to a maze by only including nodes on the current path in the visited set.)
13+
*/
14+
15+
import java.util.*;
16+
import java.io.*;
17+
18+
@SuppressWarnings("unchecked")
19+
20+
class DFS {
21+
int vertices;
22+
LinkedList<Integer>[] adjacencyList;
23+
24+
DFS(int vertices) {
25+
this.vertices = vertices;
26+
adjacencyList = new LinkedList[vertices];
27+
for (int i = 0; i < vertices; i++)
28+
adjacencyList[i] = new LinkedList<Integer>();
29+
}
30+
31+
void addEdge(int v, int w) {
32+
adjacencyList[v].add(w);
33+
}
34+
35+
void DFSUtil(int source, boolean[] visited){
36+
37+
Stack<Integer> stack = new Stack<>();
38+
39+
stack.push(source);
40+
41+
while (!stack.isEmpty()) {
42+
43+
int elem = stack.pop();
44+
45+
if (!visited[elem]) {
46+
visited[elem] = true;
47+
System.out.print(elem + " ");
48+
}
49+
50+
Iterator<Integer> iterator = adjacencyList[elem].listIterator();
51+
52+
while (iterator.hasNext()) {
53+
int num = iterator.next();
54+
if (!visited[num]) {
55+
stack.add(num);
56+
}
57+
}
58+
}
59+
}
60+
61+
void DFSTraversal(int source) {
62+
63+
System.out.print("DFS TRAVERSAL OF THE GRAPH : ");
64+
65+
boolean[] visited = new boolean[vertices];
66+
67+
for(int i=0 ; i<vertices; i++){
68+
if(!visited[i]){
69+
DFSUtil(i, visited);
70+
}
71+
}
72+
System.out.print("\n");
73+
}
74+
75+
public static void main(String[] args) {
76+
DFS dfs = new DFS(5);
77+
78+
dfs.addEdge(1, 0);
79+
dfs.addEdge(0, 2);
80+
dfs.addEdge(2, 1);
81+
dfs.addEdge(0, 3);
82+
dfs.addEdge(1, 4);
83+
84+
dfs.DFSTraversal(0);
85+
}
86+
}

‎Graph Algorithms/TopologicalSort.java

Lines changed: 90 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,90 @@
1+
/**
2+
* Topological sorting for Directed Acyclic Graph (DAG) is a linear ordering of vertices
3+
* such that for every directed edge uv, vertex u comes before v in the ordering.
4+
* Topological Sorting for a graph is not possible if the graph is not a DAG.
5+
*
6+
*
7+
* Algorithm
8+
* We can modify DFS to find Topological Sorting of a graph.
9+
* In DFS, we start from a vertex, we first print it and then recursively call DFS for its adjacent vertices.
10+
* In topological sorting, we use a temporary stack.
11+
* We don’t print the vertex immediately, we first recursively call topological sorting for all its adjacent vertices,
12+
* then push it to a stack.
13+
* Finally, print contents of stack.
14+
* Note that a vertex is pushed to stack only
15+
* when all of its adjacent vertices (and their adjacent vertices and so on) are already in stack.
16+
*/
17+
18+
import java.util.*;
19+
import java.io.*;
20+
21+
@SuppressWarnings("unchecked")
22+
23+
class TopologicalSort {
24+
int vertices;
25+
LinkedList<Integer>[] adjacencyList;
26+
27+
TopologicalSort(int vertices) {
28+
29+
this.vertices = vertices;
30+
adjacencyList = new LinkedList[vertices];
31+
32+
for (int i = 0; i < vertices; i++)
33+
adjacencyList[i] = new LinkedList<Integer>();
34+
}
35+
36+
void addEdge(int v, int w) {
37+
adjacencyList[v].add(w);
38+
}
39+
40+
void TopologicalSortingUtil(int node, boolean[] visited, Stack stack){
41+
42+
visited[node] = true;
43+
44+
Iterator<Integer> iterator = adjacencyList[node].listIterator();
45+
46+
while (iterator.hasNext()) {
47+
48+
int num = iterator.next();
49+
if (!visited[num]) {
50+
TopologicalSortingUtil(num, visited, stack);
51+
}
52+
}
53+
stack.push(node);
54+
}
55+
56+
void TopologicalSorting() {
57+
58+
System.out.print("Topological Sorting of the Graph : ");
59+
60+
boolean[] visited = new boolean[vertices];
61+
62+
Stack<Integer> stack = new Stack<Integer>();
63+
64+
for(int i=0 ; i<vertices; i++){
65+
if(!visited[i]){
66+
TopologicalSortingUtil(i, visited, stack);
67+
}
68+
}
69+
70+
while(!stack.isEmpty()){
71+
System.out.print(stack.pop()+" ");
72+
}
73+
74+
System.out.print("\n");
75+
}
76+
77+
public static void main(String[] args) {
78+
79+
TopologicalSort TopologicalSort = new TopologicalSort(6);
80+
81+
TopologicalSort.addEdge(5, 2);
82+
TopologicalSort.addEdge(5, 0);
83+
TopologicalSort.addEdge(4, 0);
84+
TopologicalSort.addEdge(4, 1);
85+
TopologicalSort.addEdge(2, 3);
86+
TopologicalSort.addEdge(3, 1);
87+
88+
TopologicalSort.TopologicalSorting();
89+
}
90+
}

0 commit comments

Comments
 (0)