4. 图数据结构实现：用Go实现邻接表与邻接矩阵，支持有向图存储与遍历

在DAG调度引擎中，图是核心抽象。选择合适的数据结构来存储有向图，直接影响调度器的内存开销、拓扑排序性能以及依赖查询效率。本节将深入剖析邻接矩阵与邻接表两种经典实现，并给出Go语言的生产级代码。

4.1 两种存储结构的核心差异

邻接矩阵与邻接表在空间复杂度、边查询速度、遍历效率上存在本质区别。下表从DAG调度场景出发，对比两者的关键指标：

4.2 邻接矩阵实现：紧凑但受限

邻接矩阵使用二维布尔数组或整型数组表示顶点间的连接关系。对于有向图，matrix[u][v] = 1 表示存在从 u 到 v 的边。

// AdjMatrix 邻接矩阵有向图
type AdjMatrix struct {
    vertexCount int
    matrix      [][]bool
    vertexNames []string
}

// NewAdjMatrix 初始化 V x V 的零矩阵
func NewAdjMatrix(vertices int) *AdjMatrix {
    m := make([][]bool, vertices)
    for i := range m {
        m[i] = make([]bool, vertices)
    }
    return &AdjMatrix{
        vertexCount: vertices,
        matrix:      m,
        vertexNames: make([]string, vertices),
    }
}

// AddEdge 添加有向边 u → v
func (g *AdjMatrix) AddEdge(u, v int) {
    if u < 0 || u >= g.vertexCount || v < 0 || v >= g.vertexCount {
        return
    }
    g.matrix[u][v] = true
}

// HasEdge 查询是否存在 u → v
func (g *AdjMatrix) HasEdge(u, v int) bool {
    if u < 0 || u >= g.vertexCount || v < 0 || v >= g.vertexCount {
        return false
    }
    return g.matrix[u][v]
}

// OutEdges 获取顶点 u 的所有出边目标
func (g *AdjMatrix) OutEdges(u int) []int {
    var edges []int
    for v := 0; v < g.vertexCount; v++ {
        if g.matrix[u][v] {
            edges = append(edges, v)
        }
    }
    return edges
}

4.3 邻接表实现：DAG调度的工业标准

邻接表为每个顶点维护一个出边列表。在Go中，使用 map[int][]int 或切片数组实现，支持动态扩展。

// AdjList 邻接表有向图
type AdjList struct {
    outEdges map[int][]int // 出边表
    inEdges  map[int][]int // 入边表（可选，加速反向遍历）
}

// NewAdjList 创建邻接表
func NewAdjList() *AdjList {
    return &AdjList{
        outEdges: make(map[int][]int),
        inEdges:  make(map[int][]int),
    }
}

// AddVertex 添加顶点（惰性初始化）
func (g *AdjList) AddVertex(v int) {
    if _, ok := g.outEdges[v]; !ok {
        g.outEdges[v] = []int{}
        g.inEdges[v] = []int{}
    }
}

// AddEdge 添加有向边 u → v
func (g *AdjList) AddEdge(u, v int) {
    g.AddVertex(u)
    g.AddVertex(v)
    g.outEdges[u] = append(g.outEdges[u], v)
    g.inEdges[v] = append(g.inEdges[v], u)
}

// OutEdges 获取出边
func (g *AdjList) OutEdges(u int) []int {
    return g.outEdges[u]
}

// InEdges 获取入边（用于反向拓扑）
func (g *AdjList) InEdges(v int) []int {
    return g.inEdges[v]
}

// VertexCount 返回顶点数量
func (g *AdjList) VertexCount() int {
    return len(g.outEdges)
}

4.4 有向图遍历：DFS与BFS

基于邻接表实现深度优先搜索（DFS）和广度优先搜索（BFS），是后续拓扑排序和可达性分析的基础。

// DFS 深度优先遍历，返回遍历顺序
func (g *AdjList) DFS(start int) []int {
    visited := make(map[int]bool)
    result := []int{}
    var dfs func(v int)
    dfs = func(v int) {
        if visited[v] {
            return
        }
        visited[v] = true
        result = append(result, v)
        for _, next := range g.outEdges[v] {
            dfs(next)
        }
    }
    dfs(start)
    return result
}

// BFS 广度优先遍历，返回遍历顺序
func (g *AdjList) BFS(start int) []int {
    visited := make(map[int]bool)
    queue := []int{start}
    result := []int{}
    visited[start] = true

    for len(queue) > 0 {
        v := queue[0]
        queue = queue[1:]
        result = append(result, v)
        for _, next := range g.outEdges[v] {
            if !visited[next] {
                visited[next] = true
                queue = append(queue, next)
            }
        }
    }
    return result
}

4.5 邻接表与邻接矩阵的结构对比

下面的SVG图直观展示了两种结构在存储有向图 A→B, A→C, B→D, C→D 时的差异：

4.6 性能基准与选型建议

在DAG调度引擎中，邻接表是绝对主流。以下基准数据基于Go 1.21，测试环境为 8核16G 虚拟机：

4.7 生产级优化：邻接表的进阶设计

在百万级DAG调度中，基础邻接表仍有优化空间。以下列出三个关键方向：

1. 切片预分配：若已知顶点平均出度，可在 AddVertex 时预分配 make([]int, 0, avgDegree)，减少切片扩容带来的内存拷贝。
2. 并发安全：调度器多协程并发读取DAG结构时，使用 sync.RWMutex 保护邻接表，或采用 sync.Map 存储顶点。
3. 紧凑存储：对于静态DAG（构建后不再修改），可将所有出边连续存储在一个大切片中，每个顶点只记录起始索引和长度，减少指针开销。

// CompactAdjList 紧凑存储的邻接表（只读优化）
type CompactAdjList struct {
    edges    []int   // 所有出边连续存储
    offsets  []int   // 每个顶点的出边起始索引
    lengths  []int   // 每个顶点的出边数量
}

// OutEdges 通过切片操作直接返回出边
func (g *CompactAdjList) OutEdges(v int) []int {
    start := g.offsets[v]
    return g.edges[start : start+g.lengths[v]]
}