وظيفة العودية للحصول على الكائنات المتصلة

[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

ينظر الى خوارزمية المكونات المتصلة بقوة لتارجان[^].

المشكلة في الخوارزمية العودية هي أنها يمكن أن تتسبب في تجاوز سعة المكدس على الرسوم البيانية الكبيرة. توجد أيضًا خوارزمية تكرارية، والتي لا تحتوي على هذه المشكلة.

[ad_2]

コメント

タイトルとURLをコピーしました