Fonction récursive pour récupérer des objets connectés

la programmation

[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]

コメント

Titre et URL copiés