DSA Quiz

def validate_edges(vertices, edges):
    if len(set(vertices)) != len(vertices) or any(not isinstance(vertex, str) for vertex in vertices):
        raise ValueError("Unique string vertices required")
    known = set(vertices)
    for first, second, weight in edges:
        if first not in known or second not in known or type(weight) is not int:
            raise ValueError("Invalid undirected edge")

import heapq

def prim_forest(vertices, edges):
    validate_edges(vertices, edges)
    adjacent = {vertex: [] for vertex in vertices}
    for first, second, weight in edges:
        adjacent[first].append((second, weight))
        adjacent[second].append((first, weight))
    seen, selected, total = set(), [], 0
    for start in vertices:
        if start in seen:
            continue
        pending = [(0, start, None)]
        while pending:
            weight, vertex, parent = heapq.heappop(pending)
            if vertex in seen:
                continue
            seen.add(vertex)
            if parent is not None:
                selected.append((parent, vertex, weight))
                total += weight
            for target, next_weight in adjacent[vertex]:
                if target not in seen:
                    heapq.heappush(pending, (next_weight, target, vertex))
    return selected, total

def validate_graph(graph, weighted=False, nonnegative=False):
    if not isinstance(graph, dict):
        raise ValueError("Expected an adjacency dictionary")
    if any(not isinstance(vertex, str) for vertex in graph):
        raise ValueError("String vertex labels required")
    for vertex, neighbors in graph.items():
        for edge in neighbors:
            if weighted:
                target, weight = edge
                if type(weight) is not int or (nonnegative and weight < 0):
                    raise ValueError("Invalid integer edge weight")
            else:
                target = edge
            if target not in graph:
                raise ValueError("Unknown target vertex")

import heapq

def dijkstra(graph, start):
    validate_graph(graph, weighted=True, nonnegative=True)
    if start not in graph:
        raise ValueError("Unknown start vertex")
    distance = {vertex: float("inf") for vertex in graph}
    distance[start] = 0
    parent, pending = {start: None}, [(0, start)]
    while pending:
        cost, vertex = heapq.heappop(pending)
        if cost != distance[vertex]:
            continue
        for target, weight in graph[vertex]:
            candidate = cost + weight
            if candidate < distance[target]:
                distance[target] = candidate
                parent[target] = vertex
                heapq.heappush(pending, (candidate, target))
    return distance, parent

vertices = ["gate", "oak", "pond"]
edges = [("gate", "oak", 2), ("oak", "pond", 2), ("gate", "pond", 3)]
_, connection_cost = prim_forest(vertices, edges)
graph = {vertex: [] for vertex in vertices}
for first, second, weight in edges:
    graph[first].append((second, weight))
    graph[second].append((first, weight))
distance, _ = dijkstra(graph, "gate")
print(connection_cost, distance["pond"])