02_Depth_First_Search.py

# File: practical2_dfs.py
# Iterative DFS implementation using adjacency list.

from collections import deque

def iterative_dfs(adj, start):
    visited = set()
    order = []
    stack = [start]
    while stack:
        node = stack.pop()
        if node not in visited:
            visited.add(node)
            order.append(node)
            # add neighbors in reversed sorted order for deterministic output
            neighbors = list(adj.get(node, []))
            try:
                neighbors.sort(reverse=True)
            except TypeError:
                pass
            for neigh in neighbors:
                if neigh not in visited:
                    stack.append(neigh)
    return order

def main():
    # Example graph (adjacency list)
    graph = {
        "A": ["B", "C"],
        "B": ["D", "E"],
        "C": ["F"],
        "D": [],
        "E": ["F"],
        "F": []
    }
    start = "A"
    order = iterative_dfs(graph, start)
    print("Iterative DFS starting from node", start)
    print("Traversal order:", " -> ".join(order))

if __name__ == "__main__":
    main()