如何改进多根到多叶子节点全路径查找的递归算法

架构老林

2026-9-24

多根节点到多叶子节点全路径查找问题

问题背景

我一直在尝试寻找更高效的树结构全路径查找方案，需求是获取从多个根节点到多个叶子节点的所有路径，目前成效有限。此前我使用可变字符串、首尾截断的逻辑（类似区块链）做了实现，但存在较多bug，我认为一定存在更合理高效的实现方式。

节点定义与存储

所有节点的父子关系预先存储在字典中，存储格式示例如下：
Parent1 = [child1, child2, child3]
Parent2 = [child1, child2, child4]
结合全节点列表，可将节点分为四类：

Elders：无父节点但有子节点的根节点
Younglings：有父节点但无子节点的叶子节点
中间节点：同时具备父节点和子节点的任意代节点
孤立节点：既无父节点也无子节点的节点

现有实现代码

我原本设想以Elders作为起点，使用BFS（广度优先搜索）计算到所有Younglings的全路径，但我之前认为BFS仅支持单根节点，因此需要适配多根、多叶子节点的算法，目前实现的代码如下：

NSMutableArray * ma = [NSMutableArray new];
NSArray * from = [NSArray arrayWithArray:[eldersSet allObjects]];
NSArray * to = [NSArray arrayWithArray:[youngSet allObjects]];
for (int n = 0; n < (int)from.count; n++){
    NSString * fromString = from[n];
    for (int k = 0; k < (int)to.count; k++){
        NSString * toString = to[k];
        NSString * toFrom = [NSString stringWithFormat:@"%@ -> %@", fromString, toString];
        NSArray * array = [self searchTreeFrom:fromString childID:toString runArray:[NSArray new]];
        if (array.count == 0){
            continue;
        }
        [ma addObject:@{@"path":toFrom, @"array":array}];
    }
}

NSLog(@"ma is %@", ma);


-(NSArray *)searchTreeFrom:(NSString *)parentID childID:(NSString *)childID runArray:(NSArray *)runArray{
    
    if ([parentID isEqualToString:childID]){
        NSMutableArray * ma = [NSMutableArray array];
        [ma addObjectsFromArray:runArray];
        [ma addObject:childID];
        return (NSArray *)ma;
    }
    
    NSMutableArray * result = [NSMutableArray new];
    if ([localR valueForKey:parentID]){
        NSArray * localArray = localR[parentID];
        for (int n = 0; n < (int)localArray.count; n++){
            result = [NSMutableArray arrayWithArray:[self searchTreeFrom:localArray[n] childID:childID runArray:result]];
            if (result.count > 0){
                [result insertObject:parentID atIndex:0];
                return result;
            }
        }
    }
    return result;
}

遇到的问题

上述代码在多数场景下运行正常，比如X形交叉路径场景（两个根节点、中间共享一个子节点、两个叶子节点）下可以正确计算出所有路径。但在<>形菱形路径场景下会出现问题：仅返回沿第一个子节点的上层路径，无法输出全部路径。
菱形结构本身存在两条路径，但此时仅查询单根到单叶子的路径，而X形场景下是查询2根2叶子的4条路径。我怀疑我的实现逻辑存在问题，因为菱形结构的路径总数无法提前预知，可能需要修改递归函数，不要在遍历到第一个子节点得到结果就返回，而是强制遍历完所有子节点。
我的需求不是查找最短路径，而是输出所有存在的路径。
补充说明：上述代码中的localR变量就是存储父子关系的字典，结构示意图如下：

解答

核心问题定位

你的判断完全正确，现有代码的问题主要有两个：

递归函数中存在提前返回逻辑：遍历子节点时，只要第一个子节点返回非空路径就直接return，终止了剩余子节点的遍历，自然会丢失其他分支的路径。
递归返回结构设计错误：当前递归只返回单条路径的数组，没有支持多条路径的存储结构，无法收集菱形场景下的多条路径。

优化方案

推荐改用非递归的BFS实现，天然支持多根节点，效率更高，也避免了递归栈溢出的风险：

队列中存储的不是单个节点，而是从根节点到当前节点的完整路径数组
初始化队列时直接把所有根节点的初始路径（仅包含根节点自己）全部放入队列
每次从队列取出一条路径，判断路径末尾的节点是不是叶子节点，如果是就直接加入结果集
如果不是叶子节点，就遍历该节点的所有子节点，拼接生成新路径后加入队列继续遍历

优化后参考代码

/// 多根节点到多叶子节点全路径查找
/// @param relationDict 父子关系字典，对应原代码中的localR
/// @param eldersSet 根节点集合
/// @param youngSet 叶子节点集合
- (NSArray<NSDictionary *> *)getAllFullPathsWithRelation:(NSDictionary *)relationDict
                                               eldersSet:(NSSet *)eldersSet
                                               youngSet:(NSSet *)youngSet {
    NSMutableArray *result = [NSMutableArray array];
    NSMutableArray *queue = [NSMutableArray array];
    // 初始化队列：所有根节点的初始路径
    for (NSString *rootNode in eldersSet) {
        [queue addObject:@[rootNode]];
    }
    while (queue.count > 0) {
        // 取出队首路径
        NSArray *currentPath = queue.firstObject;
        [queue removeObjectAtIndex:0];
        NSString *currentEndNode = currentPath.lastObject;
        // 路径末尾是叶子节点，加入结果
        if ([youngSet containsObject:currentEndNode]) {
            NSString *pathDesc = [NSString stringWithFormat:@"%@ -> %@", currentPath.firstObject, currentEndNode];
            [result addObject:@{
                @"path": pathDesc,
                @"array": [currentPath copy]
            }];
            continue;
        }
        // 遍历子节点生成新路径入队
        NSArray *children = relationDict[currentEndNode];
        if (!children) continue;
        for (NSString *childNode in children) {
            NSMutableArray *newPath = [currentPath mutableCopy];
            [newPath addObject:childNode];
            [queue addObject:newPath];
        }
    }
    return result;
}

额外说明

如果你的节点结构存在环的可能，只需要在生成新路径前判断子节点是否已经存在于当前路径中，存在则跳过即可避免死循环。

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

如何改进多根到多叶子节点全路径查找的递归算法

问题背景 #

节点定义与存储 #

现有实现代码 #

遇到的问题 #

核心问题定位 #

优化方案 #

优化后参考代码 #

额外说明 #