递归函数获取连接对象

[ad_1]

大家好 ,
我想确保当一个子区域通过连接到另一个子区域时
linkedSubRegions,并且另一个子区域连接到第三个子区域,所有三个子区域都连接成一个组。

例如:

“987”与“Schwerverkehr”相连。
“Schwerverkehr”与“975”相连。
因此,“975”、“987”和“Schwerverkehr”应连接成一组。

 const region1: Region = {
    key: 1,
    name: 'Nahverkehr',
    subRegions: [
        { key: 1, name: '975', linkedSubRegions: [{ key: 25, name: 'Schwerverkehr' }] },
        { key: 2, name: '987', linkedSubRegions: [{ key: 25, name: 'Schwerverkehr' }] },
        { key: 3, name: 'Aschaffenburg', linkedSubRegions: [] },
        { key: 4, name: 'Aschaffenburg-Land', linkedSubRegions: [{ key: 3, name: 'Aschaffenburg' }] },
        { key: 5, name: 'Marktheidenfeld', linkedSubRegions: [{ key: 4, name: 'Aschaffenburg-Land' }] },
        { key: 25, name: 'Schwerverkehr', linkedSubRegions: [] },
    ],
};

结果应该是:

subRegions: [
       { key: 1, name: '975,987,Schwerverkehr'},
       { key: 3, name: 'Aschaffenburg,Aschaffenburg-Land,Marktheidenfeld'}
   ],

我尝试过的:

mergeConnectedSubregions(region: Region): SubRegion[] {
    const subregionsMap: Map<number, SubRegion> = new Map();
    const visited: Set<number> = new Set();

    // Build a map of subregions for easy access
    for (const subregion of region.subRegions!) {
        subregionsMap.set(subregion.key!, subregion);
    }

    const mergedSubregions: SubRegion[] = [];
            const connectedSubregions: SubRegion[] = [];

    // Perform DFS for each subregion to identify connected subregions
    for (const subregion of region.subRegions!) {
        if (!visited.has(subregion.key!)) {
            dfs(subregion);
            // Merge the connected subregions
            const mergedNames = connectedSubregions.map(sub => sub.name).join(',');
            const mergedSubregion: SubRegion = {
                key: -1,
                name: mergedNames
            };
            mergedSubregions.push(mergedSubregion);
        }
    }

    return mergedSubregions;

    function dfs(subregion: SubRegion) {
        if (visited.has(subregion.key!)) return;
        visited.add(subregion.key!);
        connectedSubregions.push(subregion);
        for (const model of subregion.linkedSubRegions!) {
            const connectedSubregion = subregionsMap.get(model.key!);
            if (connectedSubregion) {
                dfs(connectedSubregion);
            }
        }
    }
  }

result was :
[
    {
        "key": -1,
        "name": "975,Schwerverkehr",

    },
    {
        "key": -1,
        "name": "975,Schwerverkehr,987",
    },
    {
        "key": -1,
        "name": "975,Schwerverkehr,987,Aschaffenburg",
    },
    {
        "key": -1,
        "name": "975,Schwerverkehr,987,Aschaffenburg,Aschaffenburg-Land",
    },
    {
        "key": -1,
        "name": "975,Schwerverkehr,987,Aschaffenburg,Aschaffenburg-Land,Marktheidenfeld"
 
    }
]

解决方案2

看着 Tarjan 的强连通分量算法[^]。

递归算法的问题是它可能会导致大型图上的堆栈溢出。 还有一种迭代算法,不存在这个问题。

[ad_2]

コメント

标题和URL已复制