Yesterday (blogging every day now!) I have presented a visualization with Python, in which a simple and basic graph was displayed. Today, I have showed how to traverse it with DFS (Depth-First Search) with quite basic skills. Just for the sake of it, if we are talking about graphs and algorithms, time complexity and space complexity are to be mentioned:
- Worst-case performance – O(|V| + |E|)
- Worst-case space complexity – O(|V|)
- Optimal? No!
The graph, used for the DFS search
In the video at the bottom of the article, DFS is explained with two different functions – dfs_minimal() and dfs_normal(). The minimal one only returns boolean value, stating whether the there is a road from the start node to the end node. And nothing else:
|
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 |
def dfs_minimal(raw_data): lines = raw_data.strip().split('\n') n_edges = int(lines[0].split()[0]) edge_lines = lines[1:1+n_edges] start, end = lines[-1].split() graph = {} for line in edge_lines: u, v, _ = line.split() if u not in graph: graph[u] = [] if v not in graph: graph[v] = [] graph[u].append(v) stack = [start] visited = set() while stack: node = stack.pop() if node == end: return True if node not in visited: visited.add(node) neighbors = graph.get(node, []) for n in reversed(neighbors): stack.append(n) return False |
As that is probably not enough for almost any scenario, another DFS algorithm is implemented – returning the path to home, the nodes visited in order and the path length:
|
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 |
def dfs_normal(raw_data): lines = raw_data.strip().split('\n') n_edges = int(lines[0].split()[0]) edge_lines = lines[1:1+n_edges] start, end = lines[-1].split() print(f"Finding a path from {start} to {end}!") print("-" * 50) graph = {} for line in edge_lines: u, v, _ = line.split() if u not in graph: graph[u] = [] if v not in graph: graph[v] = [] graph[u].append(v) stack = [start] visited = set() visited_sequence = [] parents = {start: None} step = 0 while stack: node = stack.pop() if node == end: visited_sequence.append(node) break if node not in visited: step += 1 visited_sequence.append(node) print(f'Step {step}: visiting {node}') visited.add(node) neighbors = graph.get(node, []) for n in reversed(neighbors): if n not in visited_sequence: stack.append(n) if n not in parents: parents[n] = node print("-" * 50) if end in visited_sequence: print("Reconstructing the path to home! :)") path = [] current = end while current is not None: path.append(current) current = parents[current] path.reverse() print(f'Final path: {" -> ".join(path)}') print(f'Total Nodes Visited: {len(visited_sequence)}.') print(f'Path length: {len(path)}.') else: return False return True |
As you can see yourself, for the run of that algorithm, the node between F and P is removed:
DFS searches in depth, using LIFO. Think of it as it is the biggest optimist, who always thinks that the newest task is the best option to go for. Sometimes it works!
The GitHub code is here: https://github.com/Vitosh/Python_personal/tree/master/YouTube/048_Python-Graph
The YouTube video with the writing of the code is below:
Thank you and have a great day! 🙂