拓扑排序

1from collections import deque2
3
4def topological_sort(graph):5    # Kahn's algorithm: repeatedly remove nodes with no incoming edges6    in_degree = {node: 0 for node in graph}7    for node in graph:8        for neighbor in graph[node]:9            in_degree[neighbor] += 110    queue = deque(node for node in graph if in_degree[node] == 0)11    order = []12    while queue:13        node = queue.popleft()14        order.append(node)15        for neighbor in graph[node]:16            in_degree[neighbor] -= 117            if in_degree[neighbor] == 0:18                queue.append(neighbor)19    if len(order) != len(graph):20        raise ValueError("Graph has a cycle, no topological order")21    return order22
23
24graph = {25    "shirt": ["tie", "jacket"],26    "tie": ["jacket"],27    "pants": ["shoes", "jacket"],28    "socks": ["shoes"],29    "shoes": [],30    "jacket": [],31}32
33print(" -> ".join(topological_sort(graph)))

1const graph = {2    A: ["C"],3    B: ["C", "D"],4    C: ["E"],5    D: ["F"],6    E: ["F"],7    F: [],8};9
10// Kahn algorithm: repeatedly take a node with no incoming edges11function topologicalSort() {12    const inDegree = {};13    for (const node in graph) inDegree[node] = 0;14    for (const node in graph) {15        for (const next of graph[node]) inDegree[next]++;16    }17    const queue = Object.keys(inDegree).filter((n) => inDegree[n] === 0);18    const order = [];19    while (queue.length > 0) {20        const node = queue.shift();21        order.push(node);22        for (const next of graph[node]) {23            if (--inDegree[next] === 0) queue.push(next);24        }25    }26    if (order.length !== Object.keys(graph).length) {27        throw new Error("Graph has a cycle");28    }29    return order;30}31
32console.log("Topological order:", topologicalSort().join(" -> "));

1import java.util.ArrayDeque;2import java.util.List;3import java.util.Queue;4
5public class Main {6    public static void main(String[] args) {7        int n = 6;8        // DAG: an edge u -> v means u must come before v9        List<List<Integer>> adj = List.of(10            List.of(2),11            List.of(2, 3),12            List.of(4),13            List.of(4),14            List.of(5),15            List.of()16        );17        int[] inDegree = new int[n];18        for (List<Integer> next : adj) {19            for (int v : next) inDegree[v]++;20        }21
22        // Kahn: start from every node with no prerequisites23        Queue<Integer> queue = new ArrayDeque<>();24        for (int i = 0; i < n; i++) {25            if (inDegree[i] == 0) queue.add(i);26        }27
28        StringBuilder order = new StringBuilder("Topological order:");29        while (!queue.isEmpty()) {30            int node = queue.poll();31            order.append(" ").append(node);32            for (int next : adj.get(node)) {33                if (--inDegree[next] == 0) queue.add(next);34            }35        }36        System.out.println(order);37    }38}

1#include <iostream>2#include <queue>3#include <vector>4
5int main() {6    // Directed acyclic graph: adj[u] lists nodes that depend on u7    std::vector<std::vector<int>> adj = {8        {},      // 09        {},      // 110        {3},     // 2 -> 311        {1},     // 3 -> 112        {0, 1},  // 4 -> 0, 113        {0, 2},  // 5 -> 0, 214    };15    int n = static_cast<int>(adj.size());16    std::vector<int> inDegree(n, 0);17    for (const auto& neighbors : adj) {18        for (int v : neighbors) ++inDegree[v];19    }20    // Kahn's algorithm: start from nodes with no incoming edges21    std::queue<int> ready;22    for (int u = 0; u < n; ++u) {23        if (inDegree[u] == 0) ready.push(u);24    }25    std::cout << "Topological order: ";26    while (!ready.empty()) {27        int u = ready.front();28        ready.pop();29        std::cout << u << " ";30        // Removing u unlocks neighbors whose in-degree drops to 031        for (int v : adj[u]) {32            if (--inDegree[v] == 0) ready.push(v);33        }34    }35    std::cout << "\n";36    return 0;37}

1#include <stdio.h>2
3#define N 64
5int main(void) {6    // Directed acyclic graph: adj[u][v] = 1 means an edge u -> v7    int adj[N][N] = {0};8    adj[2][3] = 1;9    adj[3][1] = 1;10    adj[4][0] = 1;11    adj[4][1] = 1;12    adj[5][0] = 1;13    adj[5][2] = 1;14    int inDegree[N] = {0};15    for (int u = 0; u < N; u++) {16        for (int v = 0; v < N; v++) inDegree[v] += adj[u][v];17    }18    // Kahn's algorithm: start from nodes with no incoming edges19    int queue[N];20    int head = 0, tail = 0;21    for (int u = 0; u < N; u++) {22        if (inDegree[u] == 0) queue[tail++] = u;23    }24    printf("Topological order: ");25    while (head < tail) {26        int u = queue[head++];27        printf("%d ", u);28        // Removing u unlocks neighbors whose in-degree drops to 029        for (int v = 0; v < N; v++) {30            if (adj[u][v] && --inDegree[v] == 0) queue[tail++] = v;31        }32    }33    printf("\n");34    return 0;35}