如何在PowerShell中实现拓扑排序（模块构建依赖场景）

为实现自定义Build-Module功能，需要对包含函数、类的对象数组按依赖关系排序，确保被依赖项优先加载。以下是最小可复现的数据集：

$Array = ConvertFrom-Json @'
[
  { "Name": "Function1", "Dependency": ["Function3"] },
  { "Name": "Function2", "Dependency": ["Function3", "Function4", "Function5"] },
  { "Name": "Function3", "Dependency": [] },
  { "Name": "Function4", "Dependency": ["Function1", "Function5"] },
  { "Name": "Function5", "Dependency": ["Function1"] }
]
'@

任务目标 #

将数组排序为被依赖项优先的顺序，预期输出如下：

Name      Dependency
----      ----------
Function3 {}
Function1 {Function3}
Function5 {Function1}
Function4 {Function1, Function5}
Function2 {Function3, Function4, Function5}

实现方案一：基于Kahn算法的拓扑排序 #

Kahn算法通过维护入度为0的节点队列，逐步移除依赖关系完成排序，适合处理较大规模的依赖结构：

# 构建包含反向依赖的节点集合
$nodes = $Array | ForEach-Object {
    [PSCustomObject]@{
        Name       = $_.Name
        Dependency = $_.Dependency.Clone()
        DependedBy = @()
    }
}

# 生成反向依赖关系（记录每个节点被哪些节点依赖）
foreach ($node in $nodes) {
    foreach ($dep in $node.Dependency) {
        $depNode = $nodes | Where-Object Name -eq $dep
        $depNode.DependedBy += $node.Name
    }
}

# 初始化队列：入度为0（无依赖）的节点
$queue = $nodes | Where-Object { $_.Dependency.Count -eq 0 }

$sortedResult = @()
while ($queue.Count -gt 0) {
    $currentNode = $queue[0]
    $queue = $queue[1..($queue.Count-1)]
    $sortedResult += $currentNode | Select-Object Name, Dependency

    # 移除当前节点对依赖它的节点的影响
    foreach ($dependedNodeName in $currentNode.DependedBy) {
        $dependedNode = $nodes | Where-Object Name -eq $dependedNodeName
        $dependedNode.Dependency = $dependedNode.Dependency | Where-Object { $_ -ne $currentNode.Name }
        # 若该节点依赖已全部处理，加入队列
        if ($dependedNode.Dependency.Count -eq 0) {
            $queue += $dependedNode
        }
    }
}

# 输出排序结果
$sortedResult

实现方案二：基于DFS的递归拓扑排序 #

通过深度优先递归，优先处理节点的所有依赖项，确保依赖项先被加入结果集，代码简洁直观：

$visitedNodes = @{}
$sortedResult = @()

function Invoke-TopologicalSort {
    param($targetName)
    # 已处理过的节点直接返回
    if ($visitedNodes.ContainsKey($targetName)) {
        return
    }
    $visitedNodes[$targetName] = $true
    $targetNode = $Array | Where-Object Name -eq $targetName

    # 先递归处理所有依赖项
    foreach ($dependency in $targetNode.Dependency) {
        Invoke-TopologicalSort -targetName $dependency
    }

    # 依赖全部处理完成后，将当前节点加入结果
    $sortedResult += $targetNode
}

# 遍历所有节点启动排序
foreach ($item in $Array) {
    Invoke-TopologicalSort -targetName $item.Name
}

# 输出排序结果
$sortedResult

内容的提问来源于stack exchange，提问作者iRon