Depth-First Search (DFS) algorithm with Python

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!

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:

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:

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:

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! 🙂