العثور على جميع subgraphs قطع في الرسم البياني

Question

ولدي الرسم البياني الذي يحتوي على عدد غير معروف من subgraphs قطع. ما هو خوارزمية جيدة (أو مكتبة جافا) للعثور عليهم جميعا؟

Answer 1

وأعتقد أن ما كنت تبحث عن ما يسمى عموما الفيضانات التعبئة . والأمر متروك لكم ما اذا كنت اجتياز الرسم البياني من خلال BFS أو DFS.

واساسا كنت تأخذ تحمل اسما (uncoloured AKA) العقدة وتعيين تسمية جديدة له. تعيين نفس التسمية إلى كافة العقد المجاورة لأحد، وهلم جرا إلى كل العقد التي يمكن الوصول إليها من تلك العقدة.

عند يمكن أن توصف أي عقد أكثر يمكن الوصول إليها، عليك أن تبدأ على طريق التقاط عقدة غير المسماة آخر. لاحظ أن حقيقة أن لا تحمل اسما هذه العقدة الجديدة يعني أنها غير قابلة للوصول من العقدة السابقة لدينا، وبالتالي في مكون قطع مختلفة.

وعندما لا يكون هناك عقد أكثر تحمل اسما، وعدد من العلامات المميزة كان لديك لاستخدام هو عدد عناصر الرسم البياني. تسمية كل عقدة يخبرك العقدة التي هي جزء من أي مكون.

Answer 2

وليس تطبيق جافا ولكن ربما يكون مفيدا لشخص ما، وهنا هو كيف نفعل ذلك في بيثون:

import networkx as nx
g = nx.Graph()
# add nodes/edges to graph
d = list(nx.connected_component_subgraphs(g))
# d contains disconnected subgraphs
# d[0] contains the biggest subgraph

هنا .

Answer 3

وهناك العديد من جوانب هذه المسألة التي لم يتم شرحها بشكل كامل، لذلك أنا ذاهب لإعطاء إجابة وافية إلى حد ما. بلدي الميل إلى نشر الجدران من النص على الرغم من. : / لاحظ أيضا أن أفترض هذا هو السؤال السؤال الواجبات المنزلية أو التعليم الذاتي، لذلك أنا لا أذهب لإعطاء إجابة مباشرة المتابعة

والخوارزميات الأساسيين للكشف عن اتصال من الرسم البياني هي عمق البحث الأولى و < وأ href = "http://en.wikipedia.org/wiki/Breadth-first_search" يختلط = "noreferrer"> اتساع البحث الأول . تلك هي الحقيقة 2 ابتداء من النقاط التي تريد أن ننظر إلى. كلا سوف تحصل على الحل، ولكن بطرق مختلفة، ومن الصعب القول الذي هو "أفضل" من دون النظر في بعض جوانب جميلة في عمق المشكلة. ولكن دعنا ننتقل.

وكما ذكرت من قبل، تركت بعض التفاصيل المهمة، وسوف أتطرق إلى بعض الاحتمالات هنا.

هل الرسم البياني الخاص بك موجهة أو غير موجهة؟ وهل تعتبر الربط بمعنى "قوية" (في هذه الحالة، انظر oggy في الجواب)، أو الاتصال في "ضعيف" معنى؟ اعتمادا على إجابتك، سيكون لديك للتعامل الخوارزمية الخاصة بك بطريقة مختلفة بمهارة. لاحظ أنه لبياني صليات، والربط الضعيف والقوي وتعادل، بحيث لطيفة. ولكن سيكون لديك للحفاظ على هيكل الرسم البياني في الاعتبار بغض النظر، في حين أن تنفيذ أو إيجاد خوارزمية.

وعلاوة على ذلك، هناك مسألة ما تقصد ب "العثور على subgraphs" (إعادة صياغة). عادة الربط الرسم البياني مشكلة القرار - ببساطة "هناك واحد الرسم البياني المتصل" أو "هناك اثنين أو أكثر من الرسوم البيانية الفرعية (الملقب، انها قطع)". وجود خوارزمية لذلك يتطلب أقل قدر من bookwork، التي هي لطيفة. :) الخطوة التالية تصل سيكون <م> العد الرسوم البيانية، حرفيا عدد منهم، وذلك bookwork هي أيضا ليست سيئة للغاية. Penultimately، قد ترغب في قائمة العقد في كل الرسم البياني الفرعي. وأخيرا، قد ترغب في نسخ حرفيا إلى الرسوم البيانية الفرعية، وحواف وكل (ما نوع الإرجاع ستكون قائمة الرسوم البيانية، على ما اعتقد، مع ثابتة ضمني أن كل رسم بياني متصل). فإن أيا من هذه مختلفة نتيجة-أنواع تتطلب خوارزمية مختلفة، ولكن بالتأكيد تتطلب نهجا مختلفا إلى bookwork.

كل هذا قد يبدو وكأنه مبلغ سخيف من مبالغة لما هو السؤال الأساسي جدا، ولكنني اعتقدت أن مجرد تسليط الضوء على جميع الجوانب التي ينطوي عليها حتى مثل هذا السؤال بياني بسيط. كنوع من التشويق، لاحظ كيف لا شيء من هذا يمس حتى بعد على وقت التشغيل أو استخدام الذاكرة! :) - AGOR

Answer 4

JGraphT هو مصدر مفتوح لطيف الرسوم البيانية مكتبة مرخص تحت رخصة LGPL. لقد استخدمت في الماضي للتعامل مع الرسوم البيانية ودورات كشف في الرسوم البيانية. بل هو أيضا من السهل نسبيا للاستعمال، ويمكنك استخدام JGraph لتصور الرسوم البيانية.

Answer 5

وأفترض أنك تريد أن تجد جميع المكونات (بقوة) متصلة؟ لذلك يمكنك استخدام Tarjan في خوارزمية (والبديل من DFS)

Answer 6

وماذا عن البحث الأول اتساع للعثور على كافة العقد متصلة؟ وبمجرد الانتهاء من قائمة العقد متصلة، تقوم بطرح هذه القائمة من قائمة كافة العقد. ينتهي بك الأمر مع قائمة العقد قطع

Answer 7

وأنا واجهت مشكلة مماثلة حيث كنت أرغب جميع subgraphs اتصال ضعيف من مخطط موجه. أنا كتبت عن ذلك هنا . لقد استخدمت JUNG API والمقارنة بين النهج. توجهي الأول يمكن أن تستخدم كنموذج لحل مشكلتك.