पायथन: ग्राफ़ में 2 नोड्स के बीच कोई पथ मौजूद है या नहीं?

Question

मैं पाइथन के नेटवर्कएक्स पैकेज का उपयोग कर रहा हूं।

Answer 1

>>> import networkx as nx 
>>> G=nx.empty_graph() 
>>> G.add_edge(1,2) 
>>> G.add_edge(2,3) 
>>> G.add_edge(4,5) 
>>> nx.path.bidirectional_dijkstra(G,1,2) 
(1, [1, 2]) 
>>> nx.path.bidirectional_dijkstra(G,1,3) 
(2, [1, 2, 3]) 
>>> nx.path.bidirectional_dijkstra(G,1,4) 
False 
>>> nx.path.bidirectional_dijkstra(G,1,5) 
False 
>>> 

तुम भी एक बूलियन मान के रूप में परिणाम का उपयोग कर सकते

>>> if nx.path.bidirectional_dijkstra(G,1,2): print "path exists" 
... 
path exists 
>>> if nx.path.bidirectional_dijkstra(G,1,4): print "path exists" 
... 
>>> 

Answer 2

• dijkstra_path(G, source, target)

  जी एक भारित ग्राफ में लक्षित करने के लिए स्रोत से कम से कम पथ रिटर्न

Answer 3

उपयोग

shortest_path(G, source, target) 

या शोर्टेस्ट पाथ तरीकों में से एक। उन तरीकों से स्पष्ट रहें जो सभी नोड्स के बीच पथ लौटाते हैं, हालांकि यदि आपके पास कनेक्टिविटी के लिए परीक्षण करने के लिए केवल दो विशिष्ट नोड्स हैं।

Answer 4

एक असंबंधित समूह डेटा संरचना का उपयोग करना:

एक सिंगलटन ग्राफ में हर शिखर के लिए सेट बनाएं, फिर संघ सेट ग्राफ में हर बढ़त के लिए शीर्षों की इस जोड़ी में दोनों हैं।

अंत में, आप जानते हैं कि एक रास्ता दो कोने के बीच मौजूद है अगर वे एक ही सेट में हैं।

असंबंधित समूह डेटा संरचना पर wikipedia पेज देखें।

यह पथ खोज एल्गोरिदम का उपयोग करने से कहीं अधिक कुशल है।

Answer 5

वहाँ एक ग्राफ में दो नोड्स के बीच एक रास्ता है कि क्या जांच करने के लिए -

>>> import networkx as nx 
>>> G=nx.Graph() 
>>> G.add_edge(1,2) 
>>> G.add_edge(2,3) 
>>> nx.has_path(G,1,3) 
True 
>>> G.add_edge(4,5) 
>>> nx.has_path(G,1,5) 
False 

अधिक जानकारी के लिए कृपया उल्लेख has_path — NetworkX 1.7 documentation