TechInterview2020/src/Graph/DepthFirstSearchRecursive.java at master · kalpak92/TechInterview2020 · GitHub

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
packageGraph;

importjava.util.ArrayList;
importjava.util.HashMap;
importjava.util.List;
importjava.util.Map;

/**
 * @author kalpak
 *
 * DFS Traversal on a Graph - Recursive
 */
publicclassDepthFirstSearchRecursive {
staticclassEdge {
intfrom, to, cost;

publicEdge(intfrom, intto, intcost) {
this.from = from;
this.to = to;
this.cost = cost;
 }
 }

// Helper method to setup graph
privatestaticvoidaddDirectedEdge(Map<Integer, List<Edge>> graph, intfrom, intto, intcost) {
List<Edge> list = graph.get(from);
if (list == null) {
list = newArrayList<Edge>();
graph.put(from, list);
 }
list.add(newEdge(from, to, cost));
 }

publicstaticvoiddfsRecursive(intstart, boolean[] isVisited, Map<Integer, List<Edge>> graph) {
if(isVisited[start])
return;

isVisited[start] = true;
System.out.print(start + " ");

List<Edge> adjacencyList = graph.get(start);
if(adjacencyList != null) {
for(Edgeedge : adjacencyList) {
dfsRecursive(edge.to, isVisited, graph);
 }
 }
return;
 }

publicstaticvoidmain(String[] args) {
intnumNodes = 5;
Map<Integer, List<Edge>> graph = newHashMap<>();

addDirectedEdge(graph, 0, 1, 4);
addDirectedEdge(graph, 0, 2, 5);
addDirectedEdge(graph, 1, 2, -2);
addDirectedEdge(graph, 1, 3, 6);
addDirectedEdge(graph, 2, 3, 1);
addDirectedEdge(graph, 2, 2, 10); // Self loop

dfsRecursive(0, newboolean[numNodes], graph);
 }
}