forked from thuva4/Algorithms
-
Notifications
You must be signed in to change notification settings - Fork 0
Expand file tree
/
Copy pathDFS_Iterative.java
More file actions
64 lines (49 loc) · 1.36 KB
/
DFS_Iterative.java
File metadata and controls
64 lines (49 loc) · 1.36 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
import java.util.ArrayList;
import java.util.Scanner;
import java.util.Stack;
public class DFS_Iterative {
/**
* @author Youssef Ali(https://github.com/youssefAli11997/)
*/
private static boolean[] visited;
private static ArrayList<Integer> AdjList[];
public static void DFS_iterative(int source){
Stack<Integer> s = new Stack<>();
s.push(source);
visited[source] = true;
while(!s.isEmpty()){
int parent = s.pop();
System.out.print(parent+" ");
for(int child : AdjList[parent]){
if(visited[child])
continue;
visited[child] = true;
s.push(child);
}
}
}
@SuppressWarnings("unchecked")
public static void main(String[] args) {
Scanner in = new Scanner(System.in);
System.out.println("How many nodes?");
int nodes = in.nextInt();
visited = new boolean[nodes];
AdjList = new ArrayList[nodes];
for(int i=0; i<nodes; i++)
AdjList[i] = new ArrayList<Integer>();
System.out.println("How many edges?");
int edges = in.nextInt();
for(int i=0; i<edges; i++){
System.out.println("To indicate that u is connected to v, type: u v");
int u = in.nextInt();
int v = in.nextInt();
// Assuming that it's an undirected graph
AdjList[u].add(v);
AdjList[v].add(u);
}
System.out.println("Source node?");
int source = in.nextInt();
DFS_iterative(source);
System.out.println();
}
}