1
package depgraph
2

3
import (
4
    "fmt"
5
    "sort"
6
)
7

8
// DependencyGraph 用邻接表表示的有向无环图
9
type DependencyGraph struct {
10
    adj map[string][]string
11
}
12

13
func New() *DependencyGraph {
14
    return &DependencyGraph{adj: make(map[string][]string)}
15
}
16

17
// AddEdge 添加一条依赖边：from 必须在 to 之前完成
18
func (g *DependencyGraph) AddEdge(from, to string) {
19
    g.adj[from] = append(g.adj[from], to)
20
    // 确保目标节点也在图中
21
    if _, ok := g.adj[to]; !ok {
22
        g.adj[to] = nil
23
    }
24
}
25

26
// TopologicalSort 基于 Kahn 算法的拓扑排序，检测循环依赖
27
func (g *DependencyGraph) TopologicalSort() ([]string, error) {
28
    inDegree := make(map[string]int)
29
    for node := range g.adj {
30
        inDegree[node] = 0
31
    }
32
    for _, deps := range g.adj {
33
        for _, dep := range deps {
34
            inDegree[dep]++
35
        }
36
    }
37
    // 收集入度为 0 的节点作为起始
38
    var queue []string
39
    for node, deg := range inDegree {
40
        if deg == 0 {
41
            queue = append(queue, node)
42
        }
43
    }
44
    sort.Strings(queue) // 确定性输出
45

46
    var result []string
47
    for len(queue) > 0 {
48
        node := queue[0]
49
        queue = queue[1:]
50
        result = append(result, node)
51
        for _, dep := range g.adj[node] {
52
            inDegree[dep]--
53
            if inDegree[dep] == 0 {
54
                queue = append(queue, dep)
55
            }
56
        }
57
    }
58
    if len(result) != len(g.adj) {
59
        return nil, fmt.Errorf("检测到循环依赖")
60
    }
61
    return result, nil
62
}

1
// 依赖图：用邻接表管理任务间的依赖关系
2
class DependencyGraph<T> {
3
  private adjacency = new Map<T, Set<T>>();
4

5
  addNode(node: T): void {
6
    if (!this.adjacency.has(node)) {
7
      this.adjacency.set(node, new Set());
8
    }
9
  }
10

11
  // 添加依赖边：from 必须在 to 之前
12
  addEdge(from: T, to: T): void {
13
    this.addNode(from);
14
    this.addNode(to);
15
    this.adjacency.get(from)!.add(to);
16
  }
17

18
  // Kahn 算法拓扑排序，内置循环检测
19
  topologicalSort(): T[] {
20
    const inDegree = new Map<T, number>();
21
    for (const node of this.adjacency.keys()) inDegree.set(node, 0);
22
    for (const [, deps] of this.adjacency) {
23
      for (const dep of deps) {
24
        inDegree.set(dep, (inDegree.get(dep) ?? 0) + 1);
25
      }
26
    }
27
    const queue: T[] = [];
28
    for (const [node, degree] of inDegree) {
29
      if (degree === 0) queue.push(node);
30
    }
31
    const result: T[] = [];
32
    while (queue.length > 0) {
33
      const node = queue.shift()!;
34
      result.push(node);
35
      for (const dep of this.adjacency.get(node) ?? []) {
36
        const newDegree = inDegree.get(dep)! - 1;
37
        inDegree.set(dep, newDegree);
38
        if (newDegree === 0) queue.push(dep);
39
      }
40
    }
41
    if (result.length !== this.adjacency.size) {
42
      throw new Error("检测到循环依赖");
43
    }
44
    return result;
45
  }
46
}