Graph Traversals

O(n)
n = size(nodes)

Python - DFS | Java - DFS

	def dfs(graph: Dict[int, List[int]], cur: int, visited: Set[int]):
	if cur in visited: return
	visited.add(cur)
	print(cur, end = " ");
	for next in graph[cur]:
	dfs(graph, next, visited)

view raw GraphDFS.py hosted with ❤ by GitHub

	void dfs(Map<Integer, List<Integer>> graph, int cur, Set<Integer> visited) {
	if (visited.contains(cur)) return;
	visited.add(cur);
	System.out.print(cur + " ");
	for (int next : graph.get(cur)) {
	dfs(graph, next, visited);
	}
	}

view raw GraphDFS.java hosted with ❤ by GitHub

Python - BFS | Java - BFS

	def bfs(graph: Dict[int, List[int]], node: int):
	q = deque([node])
	visited = set([node])
	while q:
	cur = q.popleft()
	print(cur, end = " ")
	for next in graph[cur]:
	if next in visited:
	continue
	q.append(next)
	visited.add(next)

view raw GraphBFS.py hosted with ❤ by GitHub

	void bfs(Map<Integer, List<Integer>> graph, int node) {
	Deque<Integer> q = new ArrayDeque<>();
	Set<Integer> visited = new HashSet<>();
	q.addLast(node);
	visited.add(node);
	while (q.isEmpty() == false) {
	int cur = q.removeFirst();
	System.out.print(cur + " ");
	for (int next : graph.get(cur)) {
	if (visited.contains(next)) continue;
	q.addLast(next);
	visited.add(next);
	}
	}
	}

view raw GraphBFS.java hosted with ❤ by GitHub