पेड़ पर चक्रीय ग्राफ को कम करें (निर्भरता ग्राफ -> पेड़)

Question

मैं इसकी निर्भरताओं के लिए कुछ कोड का विश्लेषण कर रहा हूं।

    F 
     A   /| 
     |  /| 
     |  /| 
     V  < V 
     B<--->C--->E 
     \ / | 
     > <  | 
     D<------+ 

बी ए पर निर्भर करता है और सी सी बी और एफ ई सी और एफ डी बी पर निर्भर करता है और सी और ई

पर निर्भर करता है पर निर्भर करता है: मान लें कि कुछ interwoven निर्भरता, देखते हैं तो पसंद आता है

हमें बी और सी के साथ समस्या है, वे एक-दूसरे पर निर्भर हैं। उन्हें एक सुपर-नोड में जोड़ा जाना चाहिए। हमें सी और ई और एफ के साथ समस्या है, उनके पास एक चक्र है। उन्हें एक सुपर-नोड में जोड़ा जाना चाहिए।

आप

A 
    | 
    V 
super 
node 
    | 
    | 
    D 

के साथ खत्म होगा वहाँ एक अच्छा पुस्तकालय या एल्गोरिथ्म स्रोत (जावा पसंद है, लेकिन सुझाव के लिए खुले) कि इस तरह के कम करने के लिए अनुमति देता है है?

चक्र में किसी भी नोड को एक नोड में जोड़ा जाता है। किसी भी नोड जो नए नोड में किसी भी नोड को इंगित करता है उसे नये नोड को इंगित करना चाहिए। नए नोड में किसी भी नोड द्वारा इंगित कोई भी नोड उस नोड को इंगित करने के लिए नए नोड का कारण बनना चाहिए।

धन्यवाद!

Answer 1

मेरा मानना ​​है कि आप ग्राफ के strongly connected components को गठबंधन करने के लिए कह रहे हैं। हाँ?

मुझे एल्गोरिदम याद नहीं है, इसे देखने का प्रयास करेंगे।

संपादित करें: हमने जो सीखा वह तर्जन है। मुझे यह सिखाने के लिए पर्याप्त नहीं है, लेकिन here is the Wikipedia page।

मैं मूलभूत विचार देने की कोशिश करूंगा। प्रत्येक नोड को इंडेक्स # दें। फिर प्रत्येक नोड को कम लिंक दें #। लोअरलिंक हमारे द्वारा रूट पर नोड की अनुक्रमणिका है: पहला नोड माना जाना चाहिए जो हमारे लिए पथ पा सकता है। यदि हमारी लोअरलिंक == हमारी अनुक्रमणिका है, तो हम दृढ़ता से जुड़े घटक की जड़ हैं। अन्यथा, हम उसी घटक में हैं जैसे हमारी लोअरलिंक है। पूरे ग्राफ पर ऐसा करके, हम यह निर्धारित कर सकते हैं कि कौन से नोड्स दृढ़ता से जुड़े घटक हैं।