Solving Dependencies

[!NOTE] This module explores the core principles of Topological Sorting, deriving solutions from first principles and hardware constraints to build world-class, production-ready expertise.

1. Concept Definition

Problem: You have tasks with dependencies. Task A must be done before Task B. Find a valid order to complete all tasks.

• Structure: Directed Acyclic Graph (DAG).
• Result: Linear ordering of vertices such that for every edge u -> v, u comes before v.

Algorithms:

1. Kahn’s Algorithm (BFS): Uses Indegrees.
2. DFS: Uses recursion and a stack.

---

2. Interactive Analysis: Kahn’s Algorithm

1. Calculate Indegree (number of incoming edges) for all nodes.
2. Add nodes with Indegree 0 to Queue.
3. Process Queue: Remove u, add to result, decrement neighbors’ indegree. If neighbor hits 0, add to Queue.

Ready.

Order: []

---

3. Implementation

Kahn’s Algorithm (BFS)

Java

Go

public int[] findOrder(int numCourses, int[][] prerequisites) {
    int[] indegree = new int[numCourses];
    List<List<Integer>> adj = new ArrayList<>();
    for(int i=0; i<numCourses; i++) adj.add(new ArrayList<>());

    for(int[] edge : prerequisites) {
        adj.get(edge[1]).add(edge[0]);
        indegree[edge[0]]++;
    }

    Queue<Integer> q = new LinkedList<>();
    for(int i=0; i<numCourses; i++) {
        if(indegree[i] == 0) q.offer(i);
    }

    int[] res = new int[numCourses];
    int idx = 0;
    while(!q.isEmpty()) {
        int u = q.poll();
        res[idx++] = u;
        for(int v : adj.get(u)) {
            indegree[v]--;
            if(indegree[v] == 0) q.offer(v);
        }
    }

    return idx == numCourses ? res : new int[0]; // Cycle check
}

func findOrder(numCourses int, prerequisites [][]int) []int {
    indegree := make([]int, numCourses)
    adj := make([][]int, numCourses)

    for _, edge := range prerequisites {
        adj[edge[1]] = append(adj[edge[1]], edge[0])
        indegree[edge[0]]++
    }

    q := []int{}
    for i, deg := range indegree {
        if deg == 0 {
            q = append(q, i)
        }
    }

    res := []int{}
    for len(q) > 0 {
        u := q[0]
        q = q[1:]
        res = append(res, u)

        for _, v := range adj[u] {
            indegree[v]--
            if indegree[v] == 0 {
                q = append(q, v)
            }
        }
    }

    if len(res) == numCourses {
        return res
    }
    return []int{}
}

---

4. Complexity Analysis

Strategy	Time	Space	Notes
Kahn’s (BFS)	O(V + E)	O(V + E)	Detects cycles naturally (result size < V).
DFS	O(V + E)	O(V + E)	Needs separate recursion stack tracking for cycles.