एक निर्देशित ग्राफ

Question

पर ब्रेडथ-पहली खोज के दौरान एज वर्गीकरण मुझे निर्देशित ग्राफ पर चौड़ाई-पहली खोज के दौरान किनारों को उचित रूप से वर्गीकृत करने का कोई तरीका ढूंढने में कठिनाई हो रही है।

एक चौड़ाई-पहले या गहराई-पहले खोज के दौरान, आप वर्गीकृत कर सकते हैं किनारों 4 वर्गों के साथ मुलाकात की:

• वृक्ष
• वापस
• आगे क्रॉस

स्कीनिया [1] एक कार्यान्वयन देता है। यदि आप v1 से v2 तक किनारे के साथ आगे बढ़ते हैं, तो संदर्भ में जावा में डीएफएस के दौरान कक्षा को वापस करने का एक तरीका है। माता-पिता का नक्शा वर्तमान खोज के लिए पैरेंट वर्टेक्स देता है, और timeOf() विधि, जिस समय पर कशेरुक की खोज की गई है।

if (v1.equals(parents.get(v2))) { return EdgeClass.TREE; } 
    if (discovered.contains(v2) && !processed.contains(v2)) { return EdgeClass.BACK; } 
    if (processed.contains(v2)) 
    { 
     if (timeOf(v1) < timeOf(v2)) 
     { 
      return EdgeClass.FORWARD; 
     } 
     else 
     { 
      return EdgeClass.CROSS; 
     } 
    } 
    return EdgeClass.UNCLASSIFIED; 

मेरे समस्या यह है कि मैं यह सही एक निर्देशित ग्राफ पर एक चौड़ाई पहले खोज के लिए नहीं मिल सकता है। उदाहरण के लिए:

निम्नलिखित ग्राफ - एक पाश है कि - ठीक है: एक से

A -> B 
A -> C 
B -> C 

BFSing, बी की खोज की जाएगी, तो सी किनारों EAB और पूर्वी वायु कमान वृक्ष किनारों हैं, और जब EBC आखिरी पार हो गया है, बी और सी संसाधित और खोजे जाते हैं, और इस किनारे को सही ढंग से क्रॉस के रूप में वर्गीकृत किया जाता है।

लेकिन एक सादे पाश काम नहीं करता:

A -> B 
B -> C 
C -> A 

जब किनारे ईसीए पिछले पार कर जाता है, एक संसाधित और खोज की है। तो इस किनारे को गलत रूप से क्रॉस के रूप में लेबल किया गया है, भले ही यह एक बैक एज हो।

दो मामलों के इलाज के तरीके में वास्तव में कोई अंतर नहीं है, भले ही दोनों किनारों के अलग-अलग वर्ग हों।

आप निर्देशित ग्राफ पर बीएफएस के लिए उचित किनारे वर्गीकरण को कैसे कार्यान्वित करते हैं?

[1] http://www.algorist.com/

---

संपादित

यहाँ एक कार्यान्वयन @redtuna जवाब से ली गई। मैंने अभी रूट के माता-पिता को लाने के लिए एक चेक जोड़ा है। मैं JUnits परीक्षण पता चलता है कि यह निर्देशित किया गया और अनिर्दिष्ट रेखांकन के लिए काम करता है, एक पाश, एक सीधी रेखा, एक कांटा, एक मानक उदाहरण के लिए, एक एकल बढ़त, आदि के मामले में .... है

@Override 
public EdgeClass edgeClass(final V from, final V to) 
{ 
    if (!discovered.contains(to)) { return EdgeClass.TREE; } 

    int toDepth = depths.get(to); 
    int fromDepth = depths.get(from); 

    V b = to; 
    while (toDepth > 0 && fromDepth < toDepth) 
    { 
     b = parents.get(b); 
     toDepth = depths.get(b); 
    } 

    V a = from; 
    while (fromDepth > 0 && toDepth < fromDepth) 
    { 
     a = parents.get(a); 
     fromDepth = depths.get(a); 
    } 

    if (a.equals(b)) 
    { 
     return EdgeClass.BACK; 
    } 
    else 
    { 
     return EdgeClass.CROSS; 
    } 

} 

Answer 1

निर्देशित ग्राफ पर बीएफएस के लिए उचित किनारे वर्गीकरण को आप कैसे कार्यान्वित करते हैं?

जैसा कि आप पहले ही स्थापित कर चुके हैं, पहली बार नोड को एक पेड़ के किनारे बनाता है। डीएफएस के बजाए बीएफएस के साथ समस्या, क्योंकि डेविड ईइसेनस्टैट ने मेरे सामने कहा था, कि पिछली किनारों को ट्रैवर्सल ऑर्डर के आधार पर क्रॉस वाले लोगों से अलग नहीं किया जा सकता है।

इसके बजाय, आपको उन्हें अलग करने के लिए थोड़ा अतिरिक्त काम करने की आवश्यकता है। कुंजी, जैसा कि आप देखेंगे, एक क्रॉस एज की परिभाषा का उपयोग करना है।

सबसे आसान (लेकिन स्मृति-गहन) तरीका अपने पूर्ववर्तियों के सेट के साथ प्रत्येक नोड को जोड़ना है। जब आप नोड्स पर जाते हैं तो यह तुच्छ रूप से किया जा सकता है। नोड्स ए और बी के बीच एक गैर-पेड़ किनारे को ढूंढते समय, अपने पूर्ववर्ती सेट पर विचार करें। यदि कोई दूसरे का उचित सबसेट है, तो आपके पास पिछला किनारा है। अन्यथा, यह एक क्रॉस एज है। यह सीधे क्रॉस एज की परिभाषा से आता है: यह नोड्स के बीच एक धार है जहां न तो पूर्वजों और न ही पेड़ पर दूसरे के वंशज हैं।

एक बेहतर तरीका एक सेट के बजाय प्रत्येक नोड के साथ केवल "गहराई" संख्या को जोड़ना है। फिर, जब आप नोड्स जाते हैं तो यह आसानी से किया जाता है। अब जब आप ए और बी के बीच एक गैर-पेड़ का किनारा पाते हैं, तो दो नोड्स के गहरे से शुरू करें और पेड़ किनारों को पीछे की तरफ घुमाएं जब तक कि आप दूसरी गहराई तक वापस न जाएं। तो उदाहरण के लिए मान लीजिए कि गहरा था। फिर आप गहराई से ए = पैरेंट (ए) की गहराई से गणना करते हैं (ए) = गहराई (बी)।

यदि इस बिंदु पर ए = बी तो आप किनारे को पीछे की ओर वर्गीकृत कर सकते हैं क्योंकि परिभाषा के अनुसार, नोड्स में से एक पेड़ पर दूसरे का पूर्वज है। अन्यथा आप इसे क्रॉस एज के रूप में वर्गीकृत कर सकते हैं क्योंकि हम जानते हैं कि न तो नोड एक पूर्वज या दूसरे का वंशज है।

स्यूडोकोड:

foreach edge(a,b) in BFS order: 
    if !b.known then: 
     b.known = true 
     b.depth = a.depth+1 
     edge type is TREE 
     continue to next edge 
    while (b.depth > a.depth): b=parent(b) 
    while (a.depth > b.depth): a=parent(a) 
    if a==b then: 
     edge type is BACK 
    else: 
     edge type is CROSS 

Answer 2

यहां डीएफएस की प्रमुख संपत्ति यह है कि, दो नोड्स यू और वी दिए गए हैं, अंतराल [u.discovered, u.processed] [v.discovered, v.processed] का एक उपनिवेश है यदि केवल और यदि आप v के वंशज हैं। बीएफएस के समय में यह संपत्ति नहीं है; आपको कुछ और करना है, उदाहरण के लिए, बीएफएस द्वारा उत्पादित पेड़ पर डीएफएस के माध्यम से अंतराल की गणना करें। फिर वर्गीकरण छद्म कोड 1 है। पेड़ (पेड़ के किनारे) में सदस्यता की जांच करें 2. सिर के अंतराल की जांच में पूंछ (पिछला किनारा) होता है 3. पूंछ के अंतराल की जांच में सिर (आगे बढ़त) होता है 4. अन्यथा, एक क्रॉस एज घोषित करें।

Answer 3

के बजाय timeof(), आप एक अन्य शीर्ष संपत्ति है, जो जड़ से दूरी शामिल की जरूरत है। नाम दें कि distance।

आप निम्नलिखित तरीके से एक v शिखर प्रसंस्करण के लिए है:

for (v0 in v.neighbours) { 
    if (!v0.discovered) { 
     v0.discovered = true; 
     v0.parent = v; 
     v0.distance = v.distance + 1; 
    } 
} 
v.processed = true; 

आप एक शीर्ष एक v शिखर संसाधित करने के बाद आप निम्नलिखित कलन विधि हर बढ़त के लिए (v1 से v2 करने के लिए) को चला सकते हैं v की :

if (!v1.discovered) return EdgeClass.BACK; 
else if (!v2.discovered) return EdgeClass.FORWARD; 
else if (v1.distance == v2.distance) return EdgeClass.CROSS; 
else if (v1.distance > v2.distance) return EdgeClass.BACK; 
else { 
    if (v2.parent == v1) return EdgeClass.TREE; 
    else return EdgeClass.FORWARD; 
}