# 1. BFS
from collections import deque

def bfs(graph, start):
    visited = {start}
    queue = deque([start])
    order = []

    while queue:
        node = queue.popleft()
        order.append(node)

        for neighbor in graph[node]:
            if neighbor not in visited:
                visited.add(neighbor)
                queue.append(neighbor)

    return order

# Example Usage:
graph = {
    0: [1, 2],
    1: [0, 3],
    2: [0, 3],
    3: [1, 2]
}
print("BFS Traversal:", bfs(graph, 0)) 


# 2. DFS
def dfs(graph, node, visited=None, order=None):
    if visited is None:
        visited, order = set(), []

    visited.add(node)
    order.append(node)

    for neighbor in graph[node]:
        if neighbor not in visited:
            dfs(graph, neighbor, visited, order)

    return order

# Example Usage:
graph = {
    0: [1, 2],
    1: [0, 3],
    2: [0, 3],
    3: [1, 2]
}
print("DFS Traversal:", dfs(graph, 0))


# 3. KRUSKALS
def find_root(parent, node):
    if parent[node] != node:
        parent[node] = find_root(parent, parent[node])
    return parent[node]

def kruskal(num_nodes, edges):
    # 1. Sort edges by weight
    edges.sort(key=lambda x: x[2])

    # 2. Initialize parent array
    parent = list(range(num_nodes))
    
    # 3. Track MST results
    mst = []
    total_cost = 0

    # 4. Iterate through each edge
    for u, v, weight in edges:
        root_u = find_root(parent, u)
        root_v = find_root(parent, v)

        # 5. Check if cycle is formed
        if root_u != root_v:
            parent[root_u] = root_v
            mst.append((u, v, weight))
            total_cost += weight

            # 6. Stop when spanning tree is complete
            if len(mst) == num_nodes - 1:
                break

    return mst, total_cost


edges = [
    (0, 1, 10),
    (0, 2, 6),
    (0, 3, 5),
    (1, 3, 15),
    (2, 3, 4)
]

num_nodes = 4

mst_edges, min_cost = kruskal(num_nodes, edges)

print("MST Edges:")
for edge in mst_edges:
    print(edge)

print("Total Cost:")
print(min_cost)


# 4. PRIM’S
def prim(num_nodes, edges):
    visited = {0}  # Start with node 0
    mst = []
    total_cost = 0

    while len(visited) < num_nodes:
        # Find the smallest edge that connects a visited node to an unvisited node
        crossing_edges = [
            (w, u, v) for u, v, w in edges 
            if (u in visited and v not in visited) or (v in visited and u not in visited)
        ]
        
        weight, u, v = min(crossing_edges)
        
        visited.add(u)
        visited.add(v)
        mst.append((u, v, weight))
        total_cost += weight

    return mst, total_cost


# --- Example Run ---
edges = [
    (0, 1, 10),
    (0, 2, 6),
    (0, 3, 5),
    (1, 3, 15),
    (2, 3, 4)
]
num_nodes = 4

mst, cost = prim(num_nodes, edges)

print("MST Edges:", mst)
print("Total Cost:", cost)




# 5. DIJKSTRA
import heapq

def dijkstra(graph, start_node):
    distances = {node: float("inf") for node in graph}
    paths = {node: "" for node in graph}

    distances[start_node] = 0
    paths[start_node] = str(start_node)
    pq = [(0, start_node)]

    while pq:
        curr_dist, u = heapq.heappop(pq)

        if curr_dist > distances[u]:
            continue

        for neighbor, weight in graph[u]:
            new_dist = curr_dist + weight
            if new_dist < distances[neighbor]:
                distances[neighbor] = new_dist
                paths[neighbor] = f"{paths[u]} → {neighbor}"
                heapq.heappush(pq, (new_dist, neighbor))

    # Print the table output
    print(f"{'Destination':<18}{'Shortest Distance':<22}{'Shortest Path'}")
    print("-" * 55)
    for node in graph:
        print(f"{node:<18}{distances[node]:<22}{paths[node]}")

# Undirected Graph Adjacency List
graph = {
    0: [(1, 10), (2, 6), (3, 5)],
    1: [(0, 10), (3, 15)],
    2: [(0, 6), (3, 4)],
    3: [(0, 5), (1, 15), (2, 4)]
}
dijkstra(graph, 0)










