#1. Search

  • Search Algorithms work for both Direceted and Undirected graph.

#1.1 Depth First Search (DFS)

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
public class DFS {
public static void traversal(final Map<Integer, Set<Integer>> graph) {
if (graph == null) {
throw new IllegalArgumentException();
}
final Set<Integer> visited = new HashSet<>();
final List<Integer> res = new ArrayList<>();
for (final int v : graph.keySet()) {
if (!visited.contains((v))) {
dfs(v, graph, visited, res);
}
}
}
private static void dfs(final int v, final Map<Integer, Set<Integer>> graph, final Set<Integer> visited, final List<Integer> res) {
visited.add(v);
res.add(v);
for (final int adj : graph.get(v)) {
if (!visited.contains(adj)) {
dfs(adj, graph, visited, res);
}
}
}
}

Python

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
# Directed & Undirected Graph both work
def search(graph):
"""
:graph Dict:
:rtype: List
"""
res = []
if not graph:
return res
v = next(iter(graph))
visited = set()
dfs(graph, v, visited, res)
return res
def dfs(graph, v, visited, res):
"""
:graph Dict:
:v int:
:visited Set:
:res List:
"""
if not graph or not graph[v]:
return
visited.add(v)
res.append(v)
for adj in graph[v]:
if adj not in visited:
dfs(graph, adj, visited, res)

#1.2 Breadth First Search (BFS)

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
public class BFS {
public static List<Integer> traversal(final Map<Integer, Set<Integer>> graph) {
if (graph == null) {
throw new IllegalArgumentException();
}
final Queue<Integer> queue = new LinkedList<>();
final Set<Integer> visited = new HashSet<>();
final List<Integer> res = new ArrayList<>();
for (final int v : graph.keySet()) {
if (!visited.contains(v)) {
queue.offer(v);
bfs(graph, queue, visited, res);
}
}
return res;
}
private static void bfs(final Map<Integer, Set<Integer>> graph, final Queue<Integer> queue,
final Set<Integer> visited, final List<Integer> res) {
while (!queue.isEmpty()) {
final int v = queue.poll();
res.add(v);
visited.add(v);
for (final int adj : graph.get(v)) {
if (!visited.contains(adj)) {
queue.offer(adj);
}
}
}
}
}

Python

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
import collections
# Directed & Undirected graph both work
def search(graph):
res = []
if not graph:
return res
visited = set()
queue = collections.deque()
v = next(iter(graph))
queue.append(v)
visited.add(v)
while queue:
size = len(queue)
for _ in range(size):
curr = queue.popleft()
res.append(curr)
for adj in graph[curr]:
if adj not in visited:
queue.append(adj)
return res

Comments

01/03/2020