निर्देशित ग्राफ़ में चक्रों के साथ सभी पथ खोजें, स्रोत vertex

Question

दिए गए मुझे इस समस्या को हल करने में समस्या हो रही है। मुझे सभी सरल स्रोत स्रोत वर्टेक्स s से शुरू होने वाले पथों को एक निर्देशित ग्राफ़ में सरल चक्र से प्राप्त करना होगा। यानी दोहराए जाने वाले वर्टेक्स के लिए पाठ्यक्रम को छोड़कर, दोहराव की अनुमति नहीं दी जाती है, जहां चक्र पथ पर वापस आ जाता है।

मुझे पता है कि ग्राफ के चक्र होने के लिए डीएफएस विज़िट का उपयोग कैसे करें, लेकिन मुझे s से शुरू होने वाले सभी पथ खोजने के लिए इसका उपयोग करने का कोई तरीका नहीं मिल रहा है।

उदाहरण के लिए, इस ग्राफ

 +->B-+ 
     | v 
s-->T-->A<---C 
     | ^
     +->D-+ 

s से शुरू में, पथ एस टी ए-बी-सी-एक सही ढंग से मिल जाएगा। लेकिन पथ एस-टी-ए-डी-सी-ए नहीं मिलेगा, क्योंकि कशेरुका सी को डीएफएस द्वारा देखा गया है।

क्या कोई मुझे इस समस्या को हल करने का संकेत दे सकता है? धन्यवाद

Answer 1

पर यह वास्तव में काफी आसान एल्गोरिदम है, जो डीएफएस से सरल है। आप बस एक अनुभवहीन पुनरावर्ती खोज में सभी पथ की गणना, नहीं याद किसी भी आगे किसी भी समय पथ पर ही लूप बैक recurse करने:

(यह सिर्फ एक अजगर से प्रेरित स्यूडोकोड है मुझे आशा है कि यह काफी स्पष्ट है।।)

def find_paths_with_cycles(path_so_far): 
     node_just_added = path_so_far.back() 
     for neigh in out_neighbours(node_just_added): 
      if neigh in path_so_far: 
       # this is a cycle, just print it 
       print path_so_far + [neigh] 
      else: 
       find_paths_with_cycles(path_so_far + [neigh]) 


initial_path = list() 
initial_path.append(s) 
find_paths_with_cycles(initial_path) 

Answer 2

यह कचरा संग्रहण एल्गोरिदम के लिए एक आम समस्या है।

एक .NET प्रशिक्षण में, मैंने सीखा कि .NET कचरा कलेक्टर ग्राफ में दो पॉइंटर्स से शुरू करके चक्र का पता लगाता है, जिसमें से एक दूसरे की गति से दोगुनी गति से आगे बढ़ता है। यदि तेजी से आगे बढ़ने से पीछे की ओर धीमा हो जाता है, तो आपको एक चक्र मिल जाता है। यह जटिल ग्राफ के लिए अधिक शामिल होगा, लेकिन यह नोड्स लेबल किए बिना काम करेगा।

Answer 3

जब आपको कोई चक्र मिल जाए, तो वापस जाएं और चिह्नित किए गए शीर्षकों को चिह्नित करें जैसे आप उन्हें पीछे हटाना चाहते हैं।

मान लीजिए कि आपने SABCA पाया है और अगले चक्र को ढूंढना चाहते हैं। ए आपका अंतिम नोड है, आपको इसे अनमार्क नहीं करना चाहिए। सी पर वापस जाओ क्या सी से बाहर एक और किनारा जा रहा है? नहीं, तो अनमार्क C और बी पर वापस जाएं। क्या बी का एक और किनारा जा रहा है? नहीं, बी को अनमार्क करें और ए पर वापस जाएं क्या ए के बाहर एक और किनारा जा रहा है? हाँ! वहां एक है जो डी पर जाता है। तो वहां जाएं, डी चिह्नित करें, सी पर जाएं जो अब अनमार्कित है, फिर ए को यहां, आपको एक और चक्र मिला है। आप फिर से ए पर वापस आते हैं, लेकिन अब ए से बाहर निकलने वाले कोई और पथ नहीं हैं, इसलिए आप ए को अनमार्क करते हैं और एस

Answer 4

मैं आगे बढ़ गया और सी # में हारून के एल्गोरिदम लागू किया। DirectedGraphHelper.FindSimpleCycles

क्योंकि यह IEnumerable, जो lazily प्रगणित है का उपयोग करता है, तो आप उपयोग कर सकते हैं (रों) प्रथम() यदि आप केवल चाहते हैं पहले चक्र पाया जा सकता है:

public static class DirectedGraphHelper 
{ 
    public static IEnumerable<Node[]> FindSimpleCycles(Node startNode) 
    { 
     return FindSimpleCyclesCore(new Stack<Node>(new[] { startNode })); 
    } 

    private static IEnumerable<Node[]> FindSimpleCyclesCore(Stack<Node> pathSoFar) 
    { 
     var nodeJustAdded = pathSoFar.Peek(); 
     foreach (var target in nodeJustAdded.Targets) 
     { 
      if (pathSoFar.Contains(target)) 
      { 
       yield return pathSoFar.Reverse().Concat(new[] { target }).ToArray(); 
      } 
      else 
      { 
       pathSoFar.Push(target); 
       foreach (var simpleCycle in FindSimpleCyclesCore(pathSoFar)) 
       { 
        yield return simpleCycle; 
       } 
       pathSoFar.Pop(); 
      } 
     } 
    } 
} 

public class Node 
{ 
    public string Id { get; private set; } 
    public readonly List<Node> Targets = new List<Node>(); 

    public Node(string id) 
    { 
     this.Id = id; 
    } 
} 

और आप इसे का प्रयोग करेंगे इस तरह:

class Program 
{ 
    static void Main(string[] args) 
    { 
     var s = new Node("s"); 
     var t = new Node("t"); 
     var a = new Node("a"); 
     var b = new Node("b"); 
     var c = new Node("c"); 
     var d = new Node("d"); 

     s.Targets.Add(t); 
     t.Targets.Add(a); 
     a.Targets.AddRange(new[] { b, d }); 
     b.Targets.Add(c); 
     c.Targets.Add(a); 
     d.Targets.Add(c); 

     foreach (var cycle in DirectedGraphHelper.FindSimpleCycles(s)) 
     { 
      Console.WriteLine(string.Join(",", cycle.Select(n => n.Id))); 
     } 
     Console.Read(); 
    } 
}