Skip to content

Commit 2f8e458

Browse files
amangit1314amangit1314
committed
#Modification 92
1 parent cdb86cd commit 2f8e458

5 files changed

Lines changed: 266 additions & 55 deletions

File tree

‎graphs/BFS.java‎

Lines changed: 66 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,66 @@
1+
package graphs;
2+
import java.util.*;
3+
4+
// Problem Title => Java program to print BFS traversal from a given source vertex.
5+
// BFS(int s) traverses vertices reachable from s.
6+
// This class represents a directed graph using adjacency list representation
7+
class BFS{
8+
private int V; // No. of vertices
9+
private LinkedList<Integer>[] adj; //Adjacency Lists
10+
11+
// Constructor
12+
BFS(int v) {
13+
V = v;
14+
adj = new LinkedList[v];
15+
for (int i=0; i<v; ++i)
16+
adj[i] = new LinkedList();
17+
}
18+
19+
// Function to add an edge into the graph
20+
void addEdge(int v,int w) {
21+
adj[v].add(w);
22+
}
23+
24+
// prints BFS traversal from a given source s
25+
void bfs(int s) {
26+
// Mark all the vertices as not visited(By default set as false)
27+
boolean[] visited = new boolean[V];
28+
29+
// Create a queue for BFS
30+
LinkedList<Integer> queue = new LinkedList<>();
31+
32+
// Mark the current node as visited and enqueue it
33+
visited[s] = true;
34+
queue.add(s);
35+
36+
while (queue.size() != 0) {
37+
// Dequeue a vertex from queue and print it
38+
s = queue.poll();
39+
System.out.print(s + " ");
40+
41+
// Get all adjacent vertices of the dequeued vertex s If an adjacent has not been visited, then mark it visited and enqueue it
42+
for (int n : adj[s]) {
43+
if (!visited[n]) {
44+
visited[n] = true;
45+
queue.add(n);
46+
}
47+
}
48+
}
49+
}
50+
51+
// Driver method to
52+
public static void main(String[] args) {
53+
BFS g = new BFS(4);
54+
55+
g.addEdge(0, 1);
56+
g.addEdge(0, 2);
57+
g.addEdge(1, 2);
58+
g.addEdge(2, 0);
59+
g.addEdge(2, 3);
60+
g.addEdge(3, 3);
61+
62+
System.out.println("Following is Breadth First Traversal "+ "(starting from vertex 2)");
63+
64+
g.bfs(2);
65+
}
66+
}

‎graphs/DFS.java‎

Lines changed: 62 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,62 @@
1+
package graphs;
2+
import java.util.*;
3+
4+
/* Approach:
5+
Depth-first search is an algorithm for traversing or searching tree or graph data structures.
6+
The algorithm starts at the root node (selecting some arbitrary node as the root node in the case of a graph) and explores as far as possible along each branch before backtracking.
7+
So the basic idea is to start from the root or any arbitrary node and mark the node and move to the adjacent unmarked node and continue this loop until there is no unmarked adjacent node.
8+
Then backtrack and check for other unmarked nodes and traverse them.
9+
Finally, print the nodes in the path.
10+
*/
11+
12+
/*Algorithm:
13+
1. Create a recursive function that takes the index of the node and a visited array.
14+
2. Mark the current node as visited and print the node.
15+
3. Traverse all the adjacent and unmarked nodes and call the recursive function with the index of the adjacent node.
16+
*/
17+
18+
public class DFS {
19+
private int V;
20+
private LinkedList<Integer> adj[];
21+
22+
DFS(int v){
23+
V = v;
24+
adj = new LinkedList[v];
25+
for(int i = 0; i < v; ++i){
26+
adj[i] = new LinkedList<>();
27+
}
28+
}
29+
30+
void addEdge(int v, int w){
31+
adj[v].add(w);
32+
}
33+
34+
void DFSUtil(int v, boolean[] visited){
35+
visited[v] = true;
36+
System.out.print(v + " ");
37+
38+
for (int n : adj[v]) {
39+
if (!visited[n])
40+
DFSUtil(n, visited);
41+
}
42+
}
43+
44+
void DFS(int v){
45+
boolean[] visited = new boolean[V];
46+
DFSUtil(v, visited);
47+
}
48+
49+
public static void main(String[] args) {
50+
DFS g = new DFS(4);
51+
52+
g.addEdge(0, 1);
53+
g.addEdge(0, 2);
54+
g.addEdge(1, 2);
55+
g.addEdge(2, 0);
56+
g.addEdge(2, 3);
57+
g.addEdge(3, 3);
58+
59+
System.out.println("Following is Depth First Traversal " + "(starting from vertex 2)");
60+
g.DFS(2);
61+
}
62+
}

‎graphs/Graph_Problem_05.java‎

Lines changed: 9 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,9 @@
1+
package graphs;
2+
// Problem Title => Detect Cycle in UnDirected Graph using BFS/DFS Algo
3+
4+
public class Graph_Problem_05 {
5+
6+
public static void main(String[] args) {
7+
8+
}
9+
}

‎graphs/Graph_Problem_06.java‎

Lines changed: 129 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,129 @@
1+
package graphs;
2+
import java.util.*;
3+
4+
// Problem Title => Search in a Maze.
5+
6+
/*
7+
* Consider a rat placed at (0, 0) in a square matrix of order N * N. It has to reach the destination at (N - 1, N - 1). Find all possible paths that the rat can take to reach from source to destination. The directions in which the rat can move are 'U'(up), 'D'(down), 'L' (left), 'R' (right). Value 0 at a cell in the matrix represents that it is blocked and rat cannot move to it while value 1 at a cell in the matrix represents that rat can be travel through it.
8+
Note: In a path, no cell can be visited more than one time.
9+
10+
Example 1:
11+
12+
Input:
13+
N = 4
14+
m[][] = {{1, 0, 0, 0},
15+
{1, 1, 0, 1},
16+
{1, 1, 0, 0},
17+
{0, 1, 1, 1}}
18+
Output:
19+
DDRDRR DRDDRR
20+
Explanation:
21+
The rat can reach the destination at
22+
(3, 3) from (0, 0) by two paths - DRDDRR
23+
and DDRDRR, when printed in sorted order
24+
we get DDRDRR DRDDRR.
25+
Example 2:
26+
Input:
27+
N = 2
28+
m[][] = {{1, 0},
29+
{1, 0}}
30+
Output:
31+
-1
32+
Explanation:
33+
No path exists and destination cell is
34+
blocked.*/
35+
36+
/*
37+
* Approach =>
38+
* 1. Start from the initial index (i.e. (0,0)) and look for the valid moves through the adjacent cells in the order Down->Left->Right->Up (to get the sorted paths) in the grid.
39+
* 2. If the move is possible, then move to that cell while storing the character corresponding to the move(D,L,R,U) and again start looking for the valid move until the last index (i.e. (n-1,n-1)) is reached.
40+
* 3. Also, keep on marking the cells as visited and when we traversed all the paths possible from that cell,
41+
* then unmark that cell for other different paths and remove the character from the path formed.
42+
* 4. As the last index of the grid(bottom right) is reached, then store the traversed path.
43+
* */
44+
public class Graph_Problem_06{
45+
46+
// Vector to store all the possible paths
47+
static Vector<String> possiblePaths = new Vector<>();
48+
static String path = "";
49+
static final int MAX = 5;
50+
51+
// Function returns true if the move taken is valid else it will return false.
52+
static boolean isSafe(int row, int col, int[][] m, int n, boolean[][] visited) {
53+
return ( row != -1 && row != n && col != -1 && col != n && !visited[row][col] && m[row][col] != 0) ;
54+
}
55+
56+
// Function to print all the possible paths from (0, 0) to (n-1, n-1).
57+
static void printPathUtil(int row, int col, int[][] m, int n, boolean[][] visited) {
58+
// This will check the initial point (i.e. (0, 0)) to start the paths.
59+
if (row == -1 || row == n || col == -1 || col == n || visited[row][col] || m[row][col] == 0)
60+
return;
61+
62+
// If reach the last cell (n-1, n-1) then store the path and return
63+
if (row == n - 1 && col == n - 1) {
64+
possiblePaths.add(path);
65+
return;
66+
}
67+
68+
// Mark the cell as visited
69+
visited[row][col] = true;
70+
71+
// Try for all the 4 directions (down, left, right, up) in the given order to get the paths in lexicographical order
72+
73+
// Check if downward move is valid
74+
if (isSafe(row + 1, col, m, n, visited)) {
75+
path += 'D';
76+
printPathUtil(row + 1, col, m, n, visited);
77+
path = path.substring(0, path.length() - 1);
78+
}
79+
80+
// Check if the left move is valid
81+
if (isSafe(row, col - 1, m, n, visited)) {
82+
path += 'L';
83+
printPathUtil(row, col - 1, m, n, visited);
84+
path = path.substring(0, path.length() - 1);
85+
}
86+
87+
// Check if the right move is valid
88+
if (isSafe(row, col + 1, m, n, visited)) {
89+
path += 'R';
90+
printPathUtil(row, col + 1, m, n, visited);
91+
path = path.substring(0, path.length() - 1);
92+
}
93+
94+
// Check if the upper move is valid
95+
if (isSafe(row - 1, col, m, n, visited)) {
96+
path += 'U';
97+
printPathUtil(row - 1, col, m, n, visited);
98+
path = path.substring(0, path.length() - 1);
99+
}
100+
101+
// Mark the cell as unvisited for other possible paths
102+
visited[row][col] = false;
103+
}
104+
105+
// Function to store and print all the valid paths
106+
static void printPath(int[][] m, int n) {
107+
boolean [][]visited = new boolean[n][MAX];
108+
109+
// Call the utility function to find the valid paths
110+
printPathUtil(0, 0, m, n, visited);
111+
112+
// Print all possible paths
113+
for (String possiblePath : possiblePaths) System.out.print(possiblePath + " ");
114+
}
115+
116+
// Driver code
117+
public static void main(String[] args) {
118+
int[][] m = {
119+
{ 1, 0, 0, 0, 0 },
120+
{ 1, 1, 1, 1, 1 },
121+
{ 1, 1, 1, 0, 1 },
122+
{ 0, 0, 0, 0, 1 },
123+
{ 0, 0, 0, 0, 1 }
124+
};
125+
int n = m.length;
126+
127+
printPath(m, n);
128+
}
129+
}

‎graphs/Graph_Traversal_DFS.java‎

Lines changed: 0 additions & 55 deletions
This file was deleted.

0 commit comments

Comments
 (0)