This code implements and demonstrates various graph traversal algorithms (BFS,...

April 4, 2025 at 01:48 AM

from collections import deque
# BFS Implementation
def bfs(graph, start_node, end_node):
    solution = []
    frontier = deque([start_node])
    visited = set([start_node])

    while frontier:
        selected_node = frontier.popleft()
        solution.append(selected_node)

        if selected_node == end_node:
            return solution

        for neighbor in graph.get(selected_node, []):
            if neighbor not in visited:
                visited.add(neighbor)
                frontier.append(neighbor)

    return []

# DFS Implementation
def dfs(graph, start_node, end_node):
    solution = []
    stack = [start_node]
    visited = set()

    while stack:
        selected_node = stack.pop()
        if selected_node in visited:
            continue
        visited.add(selected_node)
        solution.append(selected_node)

        if selected_node == end_node:
            return solution

        for neighbor in reversed(graph.get(selected_node, [])):
            if neighbor not in visited:
                stack.append(neighbor)

    return []

# Bidirectional BFS Implementation
def bidirectional_bfs(graph, start_node, end_node):
    if start_node == end_node:
        return [start_node]

    front_frontier = deque([start_node])
    back_frontier = deque([end_node])
    front_visited = {start_node: None}
    back_visited = {end_node: None}

    while front_frontier and back_frontier:
        # Expand front frontier
        if front_frontier:
            current = front_frontier.popleft()
            for neighbor in graph.get(current, []):
                if neighbor not in front_visited:
                    front_visited[neighbor] = current
                    front_frontier.append(neighbor)
                    if neighbor in back_visited:
                        return construct_path(front_visited, back_visited, neighbor)

        # Expand back frontier
        if back_frontier:
            current = back_frontier.popleft()
            for neighbor in graph.get(current, []):
                if neighbor not in back_visited:
                    back_visited[neighbor] = current
                    back_frontier.append(neighbor)
                    if neighbor in front_visited:
                        return construct_path(front_visited, back_visited, neighbor)

    return []

# Bidirectional DFS Implementation
def bidirectional_dfs(graph, start_node, end_node):
    def dfs_partial(node, visited, opposite_visited, stack, path):
        while stack:
            current = stack.pop()
            if current in visited:
                continue
            visited[current] = path[:]
            path.append(current)

            if current in opposite_visited:
                return path + opposite_visited[current][::-1]

            for neighbor in reversed(graph.get(current, [])):
                if neighbor not in visited:
                    stack.append(neighbor)

        return None

    front_stack = [start_node]
    back_stack = [end_node]
    front_visited = {}
    back_visited = {}

    while front_stack or back_stack:
        if front_stack:
            front_path = dfs_partial(front_stack.pop(), front_visited, back_visited, front_stack, [])
            if front_path:
                return front_path

        if back_stack:
            back_path = dfs_partial(back_stack.pop(), back_visited, front_visited, back_stack, [])
            if back_path:
                return back_path

    return []

# Helper function to construct the path
def construct_path(front_visited, back_visited, meeting_point):
    path = []
    current = meeting_point

    while current:
        path.append(current)
        current = front_visited[current]
    path.reverse()

    current = back_visited[meeting_point]
    while current:
        path.append(current)
        current = back_visited[current]

    return path

# Function to get user input for graph and run the algorithms
def main():
    graph = {}
    print("Enter the graph (node -> neighbors). Type 'done' when finished:")
    while True:
        line = input()
        if line.lower() == 'done':
            break
        node, *neighbors = line.split()
        graph[node] = neighbors

    start_node = input("Enter the start node: ").strip()
    end_node = input("Enter the end node: ").strip()

    print("\n--- BFS ---")
    print("Solution:", bfs(graph, start_node, end_node))

    print("\n--- DFS ---")
    print("Solution:", dfs(graph, start_node, end_node))

    print("\n--- Bidirectional BFS ---")
    print("Solution:", bidirectional_bfs(graph, start_node, end_node))

    print("\n--- Bidirectional DFS ---")
    print("Solution:", bidirectional_dfs(graph, start_node, end_node))

if __name__ == "__main__":
    main()

This code implements and demonstrates various graph traversal algorithms (BFS, DFS, bidirectional BFS, and bidirectional DFS) and provides a user interface to input a graph and nodes to test the traversal methods. Here's a breakdown of what the code does:

Breadth-First Search (BFS):
- The function bfs(graph, start_node, end_node) performs a breadth-first search on the given graph, starting from the start_node and aiming to reach the end_node.
- It uses a queue (deque) to traverse layer by layer, and a visited set to keep track of already visited nodes.
- Returns the path from start_node to end_node if found; otherwise, returns an empty list.
Depth-First Search (DFS):
- The function dfs(graph, start_node, end_node) performs a depth-first search on the graph starting from start_node.
- It uses a stack (LIFO structure) to explore deeper paths first, and a visited set to avoid revisiting nodes.
- Returns the path from start_node to end_node if found; otherwise, returns an empty list.
Bidirectional BFS:
- The function bidirectional_bfs(graph, start_node, end_node) performs a bidirectional breadth-first search from start_node and end_node simultaneously.
- Tracks visited nodes separately from each frontier (forward and backward), and looks for an intersection between the two.
- Uses the helper function construct_path to construct the final path by combining the paths from both directions.
- Returns the path if the nodes are connected, or an empty list if no connection exists.
Bidirectional DFS:
- The function bidirectional_dfs(graph, start_node, end_node) performs a bidirectional depth-first search in a similar fashion to bidirectional BFS, but explores the graph in a depth-first manner.
- The helper function dfs_partial handles partial DFS from either start or end nodes, checking whether paths intersect with the opposite visited set.
- Returns the combined path if the nodes are connected, or an empty list otherwise.
Helper Function construct_path:
- This function aids the bidirectional BFS solution by reconstructing the complete path from the start_node to end_node after the two frontiers meet.
User Interaction (main()):
- The main() function allows the user to enter a graph interactively as an adjacency list (e.g., A B C means A connects to B and C).
- It then accepts a starting node and ending node, and runs all four traversal algorithms (BFS, DFS, bidirectional BFS, and bidirectional DFS) on the input graph.
- Displays the path results for each algorithm.

Key Features:

Supports unweighted, directed graphs.
Explores and displays the path between nodes using multiple traversal methods.
Demonstrates the difference between BFS, DFS, and their bidirectional counterparts in terms of search strategy.

Usage:

When run, this script prompts the user to input the graph and nodes to explore.
It calculates and prints the paths found by BFS, DFS, bidirectional BFS, and bidirectional DFS. If a path isn't found, it prints an empty list for that algorithm.

Generate your own explanations

Download our vscode extension

Read other generated explanations

Built by @thebuilderjr