بيثون: كيف تجد ما إذا كان هناك مسار بين العقدتين في الرسم البياني؟

Question

أنا أستخدم حزمة NetworkX من Python.

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

للتحقق مما إذا كان هناك طريق بين العقدتين في رسم بياني -

>>> 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

Answer 3

باستخدام بنية بيانات مجموعة مفككة:

قم بإنشاء مجموعة Singleton لكل قمة في الرسم البياني ، ثم اتحاد المجموعات التي تحتوي على كل زوج من الرؤوس لكل حافة في الرسم البياني.

أخيرًا ، أنت تعرف أن هناك مسارًا بين رؤمين إذا كانا في نفس المجموعة.

انظر ويكيبيديا صفحة على بنية البيانات المنفصلة.

هذا أكثر كفاءة من استخدام خوارزمية العثور على المسار.

Answer 4

يستخدم

shortest_path(G, source, target)

أو واحدة من أقصر طرق المسار. ابق على الطرق التي تعيد مساراتها بين جميع العقد ولكن إذا كان لديك فقط عقدتين محددين لاختبار الاتصال.

Answer 5

• dijkstra_path(G, source, target)

  إرجاع أقصر مسار من المصدر إلى الهدف في رسم بياني مرجح G.