[ad_1]
Hola a todos ,
Quiero asegurarme de que cuando una subregión esté conectada a otra a través de
linkedSubregions, y esa otra subregión está conectada a una tercera, las tres se concatenan en un solo grupo.
Por ejemplo:
“987” está conectado con “Schwerverkehr”.
“Schwerverkehr” está conectado con “975”.
Por lo tanto, “975”, “987” y “Schwerverkehr” deben concatenarse en un solo grupo.
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: [] }, ], };
el resultado debe ser:
subRegions: [ { key: 1, name: '975,987,Schwerverkehr'}, { key: 3, name: 'Aschaffenburg,Aschaffenburg-Land,Marktheidenfeld'} ],
Lo que he probado:
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" } ]
Solución 2
Mira a Algoritmo de componentes fuertemente conectados de Tarjan[^].
El problema con el algoritmo recursivo es que puede provocar un desbordamiento de pila en gráficos grandes. También existe un algoritmo iterativo que no tiene este problema.
[ad_2]
コメント