[ad_1]
Bonjour à tous ,
Je veux m’assurer que lorsqu’une sous-région est connectée à une autre via
linkedSubRegions et que cette autre sous-région est connectée à une troisième, toutes les trois sont concaténées en un seul groupe.
Par exemple:
“987” est relié à “Schwerverkehr”.
“Schwerverkehr” est relié au “975”.
Par conséquent, « 975 », « 987 » et « Schwerverkehr » doivent être concaténés en un seul groupe.
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: [] }, ], };
le résultat devrait être :
subRegions: [ { key: 1, name: '975,987,Schwerverkehr'}, { key: 3, name: 'Aschaffenburg,Aschaffenburg-Land,Marktheidenfeld'} ],
Ce que j’ai essayé :
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" } ]
Solution 2
Regarder L’algorithme de composants fortement connectés de Tarjan[^].
Le problème avec l’algorithme récursif est qu’il peut provoquer un débordement de pile sur des graphiques volumineux. Un algorithme itératif existe également, qui ne pose pas ce problème.
[ad_2]
コメント