एल्गोरिथ्म एक निर्देशित ग्राफ

Question

मैं दो सूचियों प्रकार अर्थात् नोड्स के साथ एक कक्षा ग्राफ़ है और किनारों

मैं एक समारोह

List<int> GetNodesInRange(Graph graph, int Range) 

है जब मैं इन मानकों पाने में नोड्स के एक विशिष्ट श्रेणी वापस जाने के लिए उपयोग करने के लिए मुझे एक एल्गोरिदम की आवश्यकता है जो ग्राफ के माध्यम से चलेगा और नोड्स की सूची को केवल गहराई (स्तर) के रूप में रेंज के रूप में वापस कर देगा। एल्गोरिदम बड़ी संख्या में नोड्स और बड़ी श्रेणियों को समायोजित करने में सक्षम होना चाहिए।

इस के ऊपर, मैं एक समान कार्य

List<int> GetNodesInRange(Graph graph, int Range, int selected) 

मैं निर्दिष्ट नोड्स की संख्या के बाहर (रेंज) के लिए यह से बाहर की ओर खोज करने के लिए, सक्षम होना चाहते हैं का उपयोग करना चाहिए।

alt text http://www.freeimagehosting.net/uploads/b110ccba58.png

तो सबसे पहले समारोह में, मैं नोड्स गुजरती हैं और एक सीमा की आवश्यकता के 2 कहना चाहिए, मैं परिणाम नोड्स नीले बॉक्स में दिखाई गई लौटने की उम्मीद है।

अन्य फ़ंक्शन, यदि मैं 1 की श्रेणी के साथ ग्राफ में नोड्स पास करता हूं और यह नोड 5 पर शुरू होता है, तो मैं चाहता हूं कि यह नोड्स की सूची लौटाए जो इस मानदंड को पूरा करते हैं (नारंगी बॉक्स में रखा गया है)

Answer 1

यह चाहिए एक पुनरावर्ती समारोह हो, कि पड़ोसियों पाता हैं चयनित के बाद, तब तक प्रत्येक पड़ोसी के पड़ोसियों को सीमा तक 0 मिल जाता है। डीएफएस इस तरह कुछ खोजता है:

List<int> GetNodesInRange(Graph graph, int Range, int selected){ 
    var result = new List<int>(); 
    result.Add(selected); 
    if (Range > 0){ 
    foreach (int neighbour in GetNeighbours(graph, selected)){ 
     result.AddRange(GetNodesInRange(graph, Range-1, neighbour)); 
    } 
    } 
    return result; 
} 

यदि संभव हो तो आपको चक्रों की भी जांच करनी चाहिए। यह कोड वृक्ष संरचना के लिए है।

Answer 2

किनारे की दिशा को अनदेखा करने के विकल्प के साथ आपको केवल एक गहराई-सीमित breadth-first search या depth-first search लगता है।

• मैं अपने आप को से लेकर 1 का केवल एक ही कर रहा हूँ:

  ---

  यहाँ है कि आप मदद कर सकते हैं एक पुनरावर्ती परिभाषा है।

• मुझे पता है कि मेरे तत्काल पड़ोसियों कौन हैं।
• तो N > 1, तो अपने आप से सीमा N के उन
  • कि सभी के मिलन रेंज N-1 की है मेरे पड़ोसी

से

Answer 3

// get all the nodes that are within Range distance of the root node of graph 
Set<int> GetNodesInRange(Graph graph, int Range) 
{ 
    Set<int> out = new Set<int>(); 
    GetNodesInRange(graph.root, int Range, out); 
    return out; 
} 

// get all the nodes that are within Range successor distance of node 
// accepted nodes are placed in out 
void GetNodesInRange(Node node, int Range, Set<int> out) 
{ 
    boolean alreadyVisited = out.add(node.value); 
    if (alreadyVisited) return; 
    if (Range == 0) return; 
    // for each successor node 
    { 
     GetNodesInRange(successor, Range-1, out); 
    } 
} 


// get all the nodes that are within Range distance of selected node in graph 
Set<int> GetNodesInRange(Graph graph, int Range, int selected) 
{ 
    Set<int> out = new Set<int>(); 
    GetNodesInRange(graph, Range, selected, out); 
    return out; 
} 

// get all the nodes that are successors of node and within Range distance 
//  of selected node 
// accepted nodes are placed in out 
// returns distance to selected node 
int GetNodesInRange(Node node, int Range, int selected, Set<int> out) 
{ 
    if (node.value == selected) 
    { 
     GetNodesInRange(node, Range-1, out); 
     return 1; 
    } 
    else 
    { 
     int shortestDistance = Range + 1; 
     // for each successor node 
     { 
      int distance = GetNodesInRange(successor, Range, selected, out); 
      if (distance < shortestDistance) shortestDistance = distance; 
     } 
     if (shortestDistance <= Range) 
     { 
      out.add(node.value); 
     } 
     return shortestDistance + 1; 
    } 
} 

मैं अपनी आवश्यकताओं को कुछ हद तक संशोधित एक List के बजाय एक Set वापस जाने के लिए।

GetNodesInRange(Graph, int, int) विधि ग्राफ़ वाले चक्रों को संभाल नहीं पाएगी। इसे नोड्स का संग्रह बनाए रखने से दूर किया जा सकता है जो पहले ही देखे जा चुके हैं। GetNodesInRange(Graph, int) विधि इस तथ्य का उपयोग करती है कि out सेट चक्रों को पार करने के लिए विज़िट किए गए नोड्स का संग्रह है।

नोट: यह नहीं किसी भी तरह से परीक्षण किया गया है।