如何修正算法以生成分支与汇聚路径的有向图？

我需要根据输入的每层节点数（例如[1,2,5,3,1]）生成特定结构的有向图，图中每个节点包含next数组和prev数组。目前循环逻辑存在问题，生成的图不符合预期，需要调整连接逻辑。

伪代码梗概 #

var node_layers = [1,2,5,3,1]
var prev_nodes = [start_node]
for i in range(1, len(node_layers)):
    var new_nodes = []
    for j in range(node_layers[i]):
        var new_node = Node()
        new_nodes.append(new_node)
        # 此处需要实现正确的前驱节点连接逻辑
        new_node.prev = ??

    prev_nodes = new_nodes

当前实现代码 #

start = FloorNode.new(0)
current = start

var node_layers = [1,2,5,3,1]
var prev_nodes = [start]
for i in range(1, len(node_layers)):
    var new_nodes = []
    for j in range(node_layers[i]):
        var new_node = FloorNode.new(0)
        new_nodes.append(new_node)
        # 连接合适的前驱节点到当前节点
        new_node.prev = []
        var prev_nodes_per_node = max(1.0, 1.0 * node_layers[i]/node_layers[i-1])
        print("per node: ", prev_nodes_per_node)
        var relative_index = j * node_layers[i-1] / node_layers[i]
        print("j, relative index: ", j, ", ", relative_index)
        for k in range(ceili(relative_index-prev_nodes_per_node/2), floori(relative_index+prev_nodes_per_node/2) + 1):
            if k >= 0 and k < len(prev_nodes):
                print("Connect ", i-1, "[", k, "] to ", i, "[", j, "]")
                FloorNode.link(prev_nodes[k], new_node)

    prev_nodes = new_nodes

问题分析 #

当前代码的前驱节点计算逻辑错误，导致生成的连接关系不符合预期。错误点在于用node_layers[i]/node_layers[i-1]计算每个节点对应的前驱数量，这会导致当当前层节点数多于前置层时，区间计算逻辑无法正确覆盖所有应该连接的前置节点，最终出现连接缺失或错位的情况。

修正方案 #

正确的逻辑应该是将前置层的节点范围均匀映射到当前层的每个节点上，每个当前节点对应前置层的一段连续区间，区间内的所有节点都作为其前驱。具体步骤如下：

1. 计算前置层节点总数 prev_count = node_layers[i-1]，当前层节点总数 curr_count = node_layers[i]
2. 对当前层的第j个节点，计算其对应的前置层区间：
   • 起始位置：start = j * prev_count / curr_count
   • 结束位置：end = (j + 1) * prev_count / curr_count
3. 找到所有索引k满足：k >= floor(start) 且 k < ceil(end)，同时确保k在前置层的索引范围内（0 <= k < prev_count）
4. 将这些k对应的前置节点连接到当前节点

修正后的代码如下：

start = FloorNode.new(0)
current = start

var node_layers = [1,2,5,3,1]
var prev_nodes = [start]
for i in range(1, len(node_layers)):
    var new_nodes = []
    prev_count = node_layers[i-1]
    curr_count = node_layers[i]
    for j in range(curr_count):
        var new_node = FloorNode.new(0)
        new_nodes.append(new_node)
        new_node.prev = []
        
        # 计算当前节点对应的前置层区间
        range_start = j * prev_count / curr_count
        range_end = (j + 1) * prev_count / curr_count
        
        # 确定需要连接的前置节点索引范围
        k_start = floor(range_start)
        k_end = ceil(range_end)
        
        # 遍历并连接所有符合条件的前置节点
        for k in range(int(k_start), int(k_end)):
            if k >= 0 and k < prev_count:
                print("Connect ", i-1, "[", k, "] to ", i, "[", j, "]")
                FloorNode.link(prev_nodes[k], new_node)

    prev_nodes = new_nodes

关键调整说明 #

• 替换了错误的prev_nodes_per_node计算逻辑，改为基于区间映射的方式，确保每个当前节点连接的前置节点连续且均匀分布
• 用(j+1)*prev_count/curr_count作为区间结束位置，保证前置层的所有节点都能被当前层节点覆盖
• 直接使用floor和ceil确定索引范围，避免了原逻辑中区间中心偏移导致的连接错误

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