Advanced Graph Algorithms in Python

Advanced graph algorithms solve complex relationship, routing, and optimization problems. They are widely used in real-world systems such as:

• Compilers and build systems
• Dependency resolution (pip, npm, Maven)
• Social networks and community detection
• Navigation systems and maps
• AI search and game pathfinding
• Network routing and optimization

---

When Do We Need Advanced Graph Algorithms?

Graphs become challenging when they are:

• Directed (dependencies, workflows)
• Weighted (costs, distances, time)
• Cyclic (loops in dependencies)
• Global in nature (SCCs, all-pairs shortest paths)

Advanced algorithms handle these efficiently and correctly.

---

1. Topological Sorting

Topological sorting produces a linear ordering of vertices in a Directed Acyclic Graph (DAG) such that for every edge
u → v, u appears before v.

Use Cases

• Course prerequisites
• Build systems and compilers
• Task scheduling
• Dependency resolution

Important Rule

✅ Only works for DAGs
❌ If a cycle exists, topological ordering is impossible.

---

Topological Sort using Kahn’s Algorithm (BFS)

Idea

1. Compute in-degree for each node
2. Push all nodes with in-degree 0 into a queue
3. Remove nodes, reduce neighbors’ in-degrees
4. If all nodes are processed → valid ordering

Implementation

from collections import deque, defaultdict

def topo_sort_kahn(n, edges):
    graph = defaultdict(list)
    indegree = [0] * n

    for u, v in edges:
        graph[u].append(v)
        indegree[v] += 1

    q = deque([i for i in range(n) if indegree[i] == 0])
    order = []

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

        for neigh in graph[node]:
            indegree[neigh] -= 1
            if indegree[neigh] == 0:
                q.append(neigh)

    return order if len(order) == n else None

Complexity

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

---

Topological Sort using DFS

Idea

• Perform DFS
• Add node to stack after visiting all neighbors
• Reverse stack for final order
• Detect cycles using visitation states

Implementation

from collections import defaultdict

def topo_sort_dfs(n, edges):
    graph = defaultdict(list)
    for u, v in edges:
        graph[u].append(v)

    visited = [0] * n  # 0=unvisited, 1=visiting, 2=visited
    stack = []

    def dfs(node):
        if visited[node] == 1:
            return False
        if visited[node] == 2:
            return True

        visited[node] = 1
        for neigh in graph[node]:
            if not dfs(neigh):
                return False

        visited[node] = 2
        stack.append(node)
        return True

    for i in range(n):
        if visited[i] == 0 and not dfs(i):
            return None

    return stack[::-1]

---

2. Strongly Connected Components (SCC)

A Strongly Connected Component is a group of nodes in a directed graph where every node is reachable from every other node.

Applications

• Cycle detection in dependency graphs
• Social network communities
• Web graph clustering
• Control flow analysis

---

Kosaraju’s Algorithm

Idea

1. DFS and store nodes by finish time
2. Reverse the graph
3. DFS in reverse finish-time order
4. Each DFS traversal forms one SCC

Implementation

from collections import defaultdict

def kosaraju_scc(n, edges):
    graph = defaultdict(list)
    rev_graph = defaultdict(list)

    for u, v in edges:
        graph[u].append(v)
        rev_graph[v].append(u)

    visited = [False] * n
    order = []

    def dfs1(node):
        visited[node] = True
        for neigh in graph[node]:
            if not visited[neigh]:
                dfs1(neigh)
        order.append(node)

    for i in range(n):
        if not visited[i]:
            dfs1(i)

    visited = [False] * n
    sccs = []

    def dfs2(node, comp):
        visited[node] = True
        comp.append(node)
        for neigh in rev_graph[node]:
            if not visited[neigh]:
                dfs2(neigh, comp)

    for node in reversed(order):
        if not visited[node]:
            comp = []
            dfs2(node, comp)
            sccs.append(comp)

    return sccs

Complexity

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

---

3. Floyd–Warshall Algorithm (All-Pairs Shortest Path)

Finds shortest paths between every pair of vertices.

When to Use

• Small to medium graphs
• Need distances between all node pairs
• Graph may contain negative edges (no negative cycles)

---

Idea

Dynamic Programming:

dist[i][j] = min(dist[i][j], dist[i][k] + dist[k][j])

Implementation

def floyd_warshall(dist):
    n = len(dist)
    for k in range(n):
        for i in range(n):
            for j in range(n):
                if dist[i][k] + dist[k][j] < dist[i][j]:
                    dist[i][j] = dist[i][k] + dist[k][j]
    return dist

Complexity

• Time: O(V³)
• Space: O(V²)

---

4. A* (A-Star) Search Algorithm

A* is a heuristic-based shortest path algorithm widely used in AI, games, and navigation systems.

Key Components

• g(n) → cost from start to node
• h(n) → heuristic estimate to goal
• f(n) = g(n) + h(n)

Why A*?

• Faster than Dijkstra
• Focuses search toward the goal
• Works best with a good heuristic

---

A* on a Grid (Manhattan Distance)

import heapq

def astar(grid, start, goal):
    rows, cols = len(grid), len(grid[0])

    def heuristic(a, b):
        return abs(a[0]-b[0]) + abs(a[1]-b[1])

    pq = [(0, start)]
    g_cost = {start: 0}
    parent = {start: None}

    while pq:
        _, current = heapq.heappop(pq)

        if current == goal:
            path = []
            while current:
                path.append(current)
                current = parent[current]
            return path[::-1]

        r, c = current
        for dr, dc in [(1,0),(-1,0),(0,1),(0,-1)]:
            nr, nc = r+dr, c+dc
            if 0 <= nr < rows and 0 <= nc < cols and grid[nr][nc] == 0:
                neighbor = (nr, nc)
                new_g = g_cost[current] + 1
                if neighbor not in g_cost or new_g < g_cost[neighbor]:
                    g_cost[neighbor] = new_g
                    f = new_g + heuristic(neighbor, goal)
                    heapq.heappush(pq, (f, neighbor))
                    parent[neighbor] = current
    return None

Complexity

• Depends on heuristic quality
• Worst case similar to Dijkstra
• Typically much faster in practice

---

Summary

Algorithm	Purpose
Topological Sort	Orders tasks in DAGs
SCC (Kosaraju)	Finds strongly connected groups
Floyd–Warshall	All-pairs shortest paths
A* Search	Fast goal-directed shortest path

These algorithms are fundamental in real-world systems involving dependencies, routing, optimization, and AI-based navigation.