dfs.py

def dfs(graph, start):
    """
    Perform Depth-First Search (DFS) on a graph starting from a given node.
    
    Args:
        graph: Dictionary representing the adjacency list of the graph
        start: Starting node for DFS
        
    Returns:
        Dictionary with discovery and finish times for each node
    """
    visited = set()
    discovery = {}
    finish = {}
    time = [0]  # Using a list to allow modification in nested functions
    
    def dfs_visit(node):
        time[0] += 1
        discovery[node] = time[0]
        visited.add(node)
        
        for neighbor in graph.get(node, []):
            if neighbor not in visited:
                dfs_visit(neighbor)
        
        time[0] += 1
        finish[node] = time[0]
    
    dfs_visit(start)
    return {'discovery': discovery, 'finish': finish}

# Test DFS on the first example (dressing order)
dressing_graph = {
    'undershorts': ['pants', 'shoes'],
    'pants': ['belt', 'shoes'],
    'belt': ['jacket'],
    'shirt': ['tie', 'belt'],
    'tie': ['jacket'],
    'jacket': [],
    'socks': ['shoes'],
    'shoes': [],
    'watch': []
}

dfs_result = dfs(dressing_graph, 'undershorts')
print("DFS Results:")
print("Discovery times:", dfs_result['discovery'])
print("Finish times:", dfs_result['finish'])

spanning.py

class DisjointSet:
    """Disjoint Set (Union-Find) data structure for Kruskal's algorithm"""
    def __init__(self, vertices):
        self.parent = {v: v for v in vertices}
        self.rank = {v: 0 for v in vertices}
    
    def find(self, item):
        while self.parent[item] != item:
            item = self.parent[item]
        return item
    
    def union(self, set1, set2):
        root1 = self.find(set1)
        root2 = self.find(set2)
        
        if root1 == root2:
            return
        
        if self.rank[root1] > self.rank[root2]:
            self.parent[root2] = root1
        else:
            self.parent[root1] = root2
            if self.rank[root1] == self.rank[root2]:
                self.rank[root2] += 1

def kruskal(graph, weights):
    """
    Find Minimum Spanning Tree (MST) using Kruskal's algorithm.
    
    Args:
        graph: Dictionary representing the adjacency list of the graph
        weights: Dictionary of edge weights (u, v): weight
        
    Returns:
        List of edges in the MST
    """
    edges = sorted(weights.keys(), key=lambda e: weights[e])
    vertices = set(graph.keys())
    ds = DisjointSet(vertices)
    mst = []
    
    for edge in edges:
        u, v = edge
        if ds.find(u) != ds.find(v):
            mst.append(edge)
            ds.union(u, v)
    
    return mst

# Test Kruskal's algorithm on the third example
example_graph_kruskal = {
    'a': ['b', 'h'],
    'b': ['a', 'c', 'h'],
    'c': ['b', 'd', 'f', 'i'],
    'd': ['c', 'e', 'f'],
    'e': ['d', 'f'],
    'f': ['c', 'd', 'e', 'g'],
    'g': ['f', 'h', 'i'],
    'h': ['a', 'b', 'g', 'i'],
    'i': ['c', 'g', 'h']
}

weights = {
    ('a', 'b'): 4, ('a', 'h'): 8,
    ('b', 'c'): 8, ('b', 'h'): 11,
    ('c', 'd'): 7, ('c', 'f'): 4, ('c', 'i'): 2,
    ('d', 'e'): 9, ('d', 'f'): 14,
    ('e', 'f'): 10,
    ('f', 'g'): 2,
    ('g', 'h'): 1, ('g', 'i'): 6,
    ('h', 'i'): 7
}

# Make sure all edges are bidirectional
full_weights = weights.copy()
for (u, v), w in weights.items():
    full_weights[(v, u)] = w

print("\nKruskal's Algorithm Results:")
mst_edges = kruskal(example_graph_kruskal, full_weights)
print("Edges in MST:", mst_edges)
print("Total weight:", sum(full_weights[e] for e in mst_edges))

topologica.py

def topological_sort(graph):
    """
    Perform topological sort on a directed acyclic graph (DAG) using DFS.
    
    Args:
        graph: Dictionary representing the adjacency list of the graph
        
    Returns:
        List of nodes in topologically sorted order
    """
    visited = set()
    result = []
    
    def dfs_visit(node):
        visited.add(node)
        for neighbor in graph.get(node, []):
            if neighbor not in visited:
                dfs_visit(neighbor)
        result.append(node)
    
    for node in graph:
        if node not in visited:
            dfs_visit(node)
    
    return result[::-1]  # Reverse to get the correct order

# Test Topological Sort on the dressing example
print("\nTopological Sort Results:")
topo_order = topological_sort(dressing_graph)
print("Dressing order:", topo_order)

# Test on the second example (u, v, w, x, y, z)
example_graph = {
    'u': ['v', 'x'],
    'v': ['y'],
    'w': ['y', 'z'],
    'x': ['v'],
    'y': ['x'],
    'z': ['z']
}

print("\nTopological Sort for second example:")
print(topological_sort(example_graph))