[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]
コメント