Función recursiva para conectar objetos.

programación

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

コメント

Título y URL copiados