forked from HarshCasper/NeoAlgo
-
Notifications
You must be signed in to change notification settings - Fork 2
Expand file tree
/
Copy pathDFS.java
More file actions
86 lines (67 loc) · 1.78 KB
/
DFS.java
File metadata and controls
86 lines (67 loc) · 1.78 KB
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
import java.util.Scanner;
public class DFS{
//dfs function for connected graph
public static void dfsHelper(int[][] edges,
int noVertices, int startVertex, boolean[] visited){
System.out.print(startVertex + " ");
visited[startVertex] = true;
for(int i = 0; i < noVertices; i++){
if(i == startVertex)
continue;
/*If there is an edge b/w starting vertex
and curr vertex, call print on curr vertex */
if(edges[startVertex][i] == 1){
/*If we have already visited curr vertex,
we will not call print on it */
if(visited[i])
continue;
dfsHelper(edges, noVertices, i, visited);
}
}
}
//this works for disconnected graph also
public static void dfs(int[][] edges, int noVertices){
boolean[] visited = new boolean[noVertices];
for(int i = 0; i < noVertices; i++){
if(!visited[i])
dfsHelper(edges, noVertices, i, visited);
}
}
public static void main(String[] args) {
Scanner scanner = new Scanner(System.in);
System.out.println("Enter the number of vertices in Graph : ");
int n = scanner.nextInt(); // no. of vertices
System.out.println("Enter the number of edges in the Graph : ");
int e = scanner.nextInt(); // no. of edges
// Adjacency Matrix
int[][] edges = new int[n+1][n+1];
//Take input of all edges
System.out.println("Enter the edges :");
for(int i = 0; i < e; i++){
int firstVertex = scanner.nextInt();
int secondVertex = scanner.nextInt();
edges[firstVertex][secondVertex] = 1;
edges[secondVertex][firstVertex] = 1;;
}
System.out.println("DFS Traversal : ");
dfs(edges, n);
}
}
/*
Sample Case :
Enter the number of vertices in Graph :
10
Enter the number of edges in the Graph :
8
Enter the edges :
1 2
1 3
2 4
4 6
3 5
5 0
7 8
8 9
DFS Traversal :
0 5 3 1 2 4 6 7 8 9
*/