# 1. BFS
# For V vertices and E edges: O(V + E) time and O(V) space.
from collections import deque
import heapq


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


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


# 2. DFS
# For V vertices and E edges: O(V + E) time and O(V) space, including the recursion stack.
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


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


# 3. KRUSKALS
# For V vertices and E edges: O(E log E + (V + E) log V) time and O(V + E) space.
def find_root(parent, node):
    if parent[node] != node:
        parent[node] = find_root(parent, parent[node])
    return parent[node]


def kruskal(num_nodes, edges):
    if num_nodes < 1:
        raise ValueError("The graph must contain at least one node.")

    parent = list(range(num_nodes))
    mst = []
    total_cost = 0

    for u, v, weight in sorted(edges, key=lambda edge: edge[2]):
        root_u = find_root(parent, u)
        root_v = find_root(parent, v)
        if root_u != root_v:
            parent[root_u] = root_v
            mst.append((u, v, weight))
            total_cost += weight
            if len(mst) == num_nodes - 1:
                break

    if len(mst) != num_nodes - 1:
        raise ValueError("The graph is disconnected.")
    return mst, total_cost


edges = [(0, 1, 10), (0, 2, 6), (0, 3, 5), (1, 3, 15), (2, 3, 4)]
mst_edges, min_cost = kruskal(4, edges)
print("MST edges:", mst_edges)
print("Total cost:", min_cost)


# 4. PRIM’S
# For V vertices and E edges: O(VE) time and O(V + E) space.
def prim(num_nodes, edges):
    if num_nodes < 1:
        raise ValueError("The graph must contain at least one node.")

    visited = {0}
    mst = []
    total_cost = 0

    while len(visited) < num_nodes:
        crossing = [
            (weight, u, v)
            for u, v, weight in edges
            if (u in visited and v not in visited) or (v in visited and u not in visited)
        ]
        if not crossing:
            raise ValueError("The graph is disconnected.")

        weight, u, v = min(crossing)
        visited.update((u, v))
        mst.append((u, v, weight))
        total_cost += weight

    return mst, total_cost


edges = [(0, 1, 10), (0, 2, 6), (0, 3, 5), (1, 3, 15), (2, 3, 4)]
mst, cost = prim(4, edges)
print("MST edges:", mst)
print("Total cost:", cost)


# 5. DIJKSTRA
# Core algorithm: O((V + E) log V) time and O(V + E) space.
# Materialized path strings can add O(EV) time and O(V^2) space.
def dijkstra(graph, start):
    if start not in graph:
        raise ValueError("Start node is not in the graph.")
    if any(weight < 0 for edges in graph.values() for _, weight in edges):
        raise ValueError("Dijkstra's algorithm requires non-negative weights.")

    distances = {node: float("inf") for node in graph}
    paths = {node: "" for node in graph}
    distances[start] = 0
    paths[start] = str(start)
    queue = [(0, start)]

    while queue:
        distance, node = heapq.heappop(queue)
        if distance > distances[node]:
            continue

        for neighbor, weight in graph[node]:
            new_distance = distance + weight
            if new_distance < distances[neighbor]:
                distances[neighbor] = new_distance
                paths[neighbor] = f"{paths[node]} -> {neighbor}"
                heapq.heappush(queue, (new_distance, neighbor))

    for node in graph:
        print(f"{node}: distance={distances[node]}, path={paths[node]}")
    return distances, paths


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)
