[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]
コメント