Graph

Question 1

Implement

Dijkstra’s Algorithm:

Input:
a) graph as an adjacency list with costs
b) starting node as string
c) ending node as string

Ouput:
a) minimum cost of the trip from starting node to ending node
b) sequence of nodes as part of that shortest path / minimum cost

Ex:

graph = {
'A': [('B', 1), ('C', 4)],
'B': [('C', 2), ('D', 5)],
'C': [('D', 1)],
'D': []
}

prev = dijkstra(graph, 'A')
print('Distance to D:', dist['D'])
print('Path to D:', reconstruct_path(prev, 'D'))

Expected output:
Distance to D: 4
Path to D: [‘A’, ‘B’, ‘C’, ‘D’]

Time O((V + E) × log V)
Space O(V + E)

Answer 1

import heapq

def dijkstra(graph, start):
    dist = {node: float('inf') for node in graph}
    prev = {node: None for node in graph}  # Track previous nodes
    dist[start] = 0
    visited = set()
    heap = [(0, start)]

    while heap:
        current_dist, u = heapq.heappop(heap)
        if u in visited:
            continue
        visited.add(u)

        for v, weight in graph[u]:
            if dist[u] + weight < dist[v]:
                dist[v] = dist[u] + weight
                prev[v] = u
                heapq.heappush(heap, (dist[v], v))
    
    return dist, prev

def reconstruct_path(prev, target):
    path = []
    while target is not None:
        path.append(target)
        target = prev[target]
    return path[::-1]  # Reverse the path

Question 2

Implement

Topological Sort: Kahn’s Version (BFS)
Input:
~~~
graph = {
‘A’: [‘C’],
‘B’: [‘C’, ‘D’],
‘C’: [‘E’],
‘D’: [‘F’],
‘E’: [‘H’, ‘F’],
‘F’: [‘G’],
‘G’: [],
‘H’: []
}

Time Complexity : O(V + E)
Space Complexity: O(V + E)

~~~

Answer 2

from collections import deque, defaultdict

def topological_sort_kahn(graph):
    in_degree = defaultdict(int)
    for u in graph:
        for v in graph[u]:
            in_degree[v] += 1
    
    queue = deque([u for u in graph if in_degree[u] == 0])
    topo_order = []

    while queue:
        u = queue.popleft()
        topo_order.append(u)
        for v in graph[u]:
            in_degree[v] -= 1
            if in_degree[v] == 0:
                queue.append(v)

    if len(topo_order) == len(graph):
        return topo_order
    else:
        raise ValueError("Graph has a cycle")

Question 3

Solve: Alien Language Problem

You’re given a list of words sorted lexicographically in an alien language. Your task is to find the order of the characters in that language.

It’s essentially a topological sort problem on a directed graph, where:

Nodes = characters

Edges = inferred precedence from adjacent words

Input: words are list of strings
Output: A string representing the lexicograph order of the alphabet of the language

✅ Total Time Complexity:
O(N + K + E), where:

N = total characters in all words

K = number of unique characters (≤ 26 for lowercase)

E = number of precedence edges

💾 Space Complexity
1. Graph & in-degree map
Graph stores up to K nodes and E edges → O(K + E)

In-degree map → O(K)

2. Queue and result list
   Both store up to K nodes → O(K)

O(K + E)

Answer 3

from collections import defaultdict, deque

def build_graph(words):
    graph = {c: set() for word in words for c in word}
        
    for i in range(len(words) - 1):
        w1, w2 = words[i], words[i + 1]
        minlen = min(len(w1), len(w2))
        
        if len(w1) > len(w2) and w1[:minlen] == w2:
            return {}
        
        for j in range(minlen):
            if w1[j] != w2[j]:
                graph[w1[j]].add(w2[j])
                break
        
    return graph

def alien_order(words):
    graph = build_graph(words)
    if not graph:
        return ""
    dependency_count = defaultdict(int)
    for p in graph:
        for c in graph[p]:
            dependency_count[c] += 1
            
    queue = deque([n for n in graph if dependency_count[n] == 0])
    
    topo_order = []
    
    while len(queue) > 0:
        p = queue.popleft()
        topo_order.append(p)
        for c in graph[p]:
            dependency_count[c] -= 1
            if dependency_count[c] == 0:
                queue.append(c)
    
    if len(topo_order) != len(graph):
        return ""
        
    return "".join(topo_order)