-
Notifications
You must be signed in to change notification settings - Fork 4.3k
/
DepthFirstSearchAdjacencyListIterativeFastStack.java
134 lines (111 loc) · 3.56 KB
/
DepthFirstSearchAdjacencyListIterativeFastStack.java
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
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
/**
* An implementation of a iterative DFS with an adjacency list using a custom stack for extra speed.
* Time Complexity: O(V + E)
*
* @author William Fiset, william.alexandre.fiset@gmail.com
*/
package com.williamfiset.algorithms.graphtheory;
import java.util.*;
// This file contains an implementation of an integer only stack which is
// extremely quick and lightweight. In terms of performance it can outperform
// java.util.ArrayDeque (Java's fastest stack implementation) by a factor of 50!
// However, the downside is you need to know an upper bound on the number of
// elements that will be inside the stack at any given time for it to work correctly.
class IntStack {
private int[] ar;
private int pos = 0, sz;
// max_sz is the maximum number of items
// that can be in the queue at any given time
public IntStack(int max_sz) {
ar = new int[(sz = max_sz)];
}
public boolean isEmpty() {
return pos == 0;
}
// Returns the element at the top of the stack
public int peek() {
return ar[pos - 1];
}
// Add an element to the top of the stack
public void push(int value) {
ar[pos++] = value;
}
// Make sure you check that the stack is not empty before calling pop!
public int pop() {
return ar[--pos];
}
}
public class DepthFirstSearchAdjacencyListIterativeFastStack {
static class Edge {
int from, to, cost;
public Edge(int from, int to, int cost) {
this.from = from;
this.to = to;
this.cost = cost;
}
}
// Perform a depth first search on a graph with n nodes
// from a starting point to count the number of nodes
// in a given component.
static int dfs(Map<Integer, List<Edge>> graph, int start, int n) {
int count = 0;
boolean[] visited = new boolean[n];
IntStack stack = new IntStack(n);
// Start by visiting the starting node
stack.push(start);
while (!stack.isEmpty()) {
int node = stack.pop();
if (!visited[node]) {
count++;
visited[node] = true;
List<Edge> edges = graph.get(node);
if (edges != null) {
for (Edge edge : edges) {
if (!visited[edge.to]) {
stack.push(edge.to);
}
}
}
}
}
return count;
}
// Example usage of DFS
public static void main(String[] args) {
// Create a fully connected graph
// (0)
// / \
// 5 / \ 4
// / \
// 10 < -2 >
// +->(2)<------(1) (4)
// +--- \ /
// \ /
// 1 \ / 6
// > <
// (3)
int numNodes = 5;
Map<Integer, List<Edge>> graph = new HashMap<>();
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
long nodeCount = dfs(graph, 0, numNodes);
System.out.println("DFS node count starting at node 0: " + nodeCount);
if (nodeCount != 4) System.err.println("Error with DFS");
nodeCount = dfs(graph, 4, numNodes);
System.out.println("DFS node count starting at node 4: " + nodeCount);
if (nodeCount != 1) System.err.println("Error with DFS");
}
// Helper method to setup graph
private static void addDirectedEdge(Map<Integer, List<Edge>> graph, int from, int to, int cost) {
List<Edge> list = graph.get(from);
if (list == null) {
list = new ArrayList<Edge>();
graph.put(from, list);
}
list.add(new Edge(from, to, cost));
}
}