العثور على المسارات بين عقدين معينين؟
https://stackoverflow.com/questions/713508
-
23-08-2019 - |
italiano
english
français
española
中国
日本の
العربية
Deutsch
한국어
Português
Russianسؤال
قل لدي عقد متصل بالأزياء أدناه، كيف أتصل إلى عدد المسارات الموجودة بين النقاط المحددة، وتفاصيل المسار؟
1,2 //node 1 and 2 are connected
2,3
2,5
4,2
5,11
11,12
6,7
5,6
3,6
6,8
8,10
8,9
ابحث عن المسارات من 1 إلى 7:
الجواب: وجدت 2 مسارات وهم
1,2,3,6,7
1,2,5,6,7
وجد التنفيذ هنا هو لطيف أنا ذاهب لاستخدام نفسه
هنا هو مقتطف من الرابط أعلاه في بيثون
# a sample graph
graph = {'A': ['B', 'C','E'],
'B': ['A','C', 'D'],
'C': ['D'],
'D': ['C'],
'E': ['F','D'],
'F': ['C']}
class MyQUEUE: # just an implementation of a queue
def __init__(self):
self.holder = []
def enqueue(self,val):
self.holder.append(val)
def dequeue(self):
val = None
try:
val = self.holder[0]
if len(self.holder) == 1:
self.holder = []
else:
self.holder = self.holder[1:]
except:
pass
return val
def IsEmpty(self):
result = False
if len(self.holder) == 0:
result = True
return result
path_queue = MyQUEUE() # now we make a queue
def BFS(graph,start,end,q):
temp_path = [start]
q.enqueue(temp_path)
while q.IsEmpty() == False:
tmp_path = q.dequeue()
last_node = tmp_path[len(tmp_path)-1]
print tmp_path
if last_node == end:
print "VALID_PATH : ",tmp_path
for link_node in graph[last_node]:
if link_node not in tmp_path:
#new_path = []
new_path = tmp_path + [link_node]
q.enqueue(new_path)
BFS(graph,"A","D",path_queue)
-------------results-------------------
['A']
['A', 'B']
['A', 'C']
['A', 'E']
['A', 'B', 'C']
['A', 'B', 'D']
VALID_PATH : ['A', 'B', 'D']
['A', 'C', 'D']
VALID_PATH : ['A', 'C', 'D']
['A', 'E', 'F']
['A', 'E', 'D']
VALID_PATH : ['A', 'E', 'D']
['A', 'B', 'C', 'D']
VALID_PATH : ['A', 'B', 'C', 'D']
['A', 'E', 'F', 'C']
['A', 'E', 'F', 'C', 'D']
VALID_PATH : ['A', 'E', 'F', 'C', 'D']
المحلول
البحث أولا في البحث اجتياز الرسم البياني وفي الواقع يجد جميع المسارات من عقدة البدء. عادة، BFS لا يحتفظ بكل المسارات. بدلا من ذلك، يقوم بتحديث دالة بريدية لحفظ أقصر المسار. يمكنك بسهولة تعديل الخوارزمية بحيث π(n) لا تخزن فقط واحد سلف ولكن قائمة من سابقات.
ثم يتم ترميز جميع المسارات الممكنة في هذه الوظيفة، وتجاوز π متكرر تحصل على جميع مجموعات المسار الممكنة.
يمكن العثور على pseudoodocode جيدة التي تستخدم هذه التدوين مقدمة في الخوارزميات بواسطة cormen. وآخرون. وقد استخدم فيما بعد في العديد من البرامج النصية الجامعية حول هذا الموضوع. بحث Google عن "BFS Pseudocode سلف π" هذا ضرب على تبادل المكدس.
نصائح أخرى
بالنسبة لأولئك الذين ليسوا خبير Python، نفس الكود في C ++
//@Author :Ritesh Kumar Gupta
#include <stdio.h>
#include <vector>
#include <algorithm>
#include <vector>
#include <queue>
#include <iostream>
using namespace std;
vector<vector<int> >GRAPH(100);
inline void print_path(vector<int>path)
{
cout<<"[ ";
for(int i=0;i<path.size();++i)
{
cout<<path[i]<<" ";
}
cout<<"]"<<endl;
}
bool isadjacency_node_not_present_in_current_path(int node,vector<int>path)
{
for(int i=0;i<path.size();++i)
{
if(path[i]==node)
return false;
}
return true;
}
int findpaths(int source ,int target ,int totalnode,int totaledge )
{
vector<int>path;
path.push_back(source);
queue<vector<int> >q;
q.push(path);
while(!q.empty())
{
path=q.front();
q.pop();
int last_nodeof_path=path[path.size()-1];
if(last_nodeof_path==target)
{
cout<<"The Required path is:: ";
print_path(path);
}
else
{
print_path(path);
}
for(int i=0;i<GRAPH[last_nodeof_path].size();++i)
{
if(isadjacency_node_not_present_in_current_path(GRAPH[last_nodeof_path][i],path))
{
vector<int>new_path(path.begin(),path.end());
new_path.push_back(GRAPH[last_nodeof_path][i]);
q.push(new_path);
}
}
}
return 1;
}
int main()
{
//freopen("out.txt","w",stdout);
int T,N,M,u,v,source,target;
scanf("%d",&T);
while(T--)
{
printf("Enter Total Nodes & Total Edges\n");
scanf("%d%d",&N,&M);
for(int i=1;i<=M;++i)
{
scanf("%d%d",&u,&v);
GRAPH[u].push_back(v);
}
printf("(Source, target)\n");
scanf("%d%d",&source,&target);
findpaths(source,target,N,M);
}
//system("pause");
return 0;
}
/*
Input::
1
6 11
1 2
1 3
1 5
2 1
2 3
2 4
3 4
4 3
5 6
5 4
6 3
1 4
output:
[ 1 ]
[ 1 2 ]
[ 1 3 ]
[ 1 5 ]
[ 1 2 3 ]
The Required path is:: [ 1 2 4 ]
The Required path is:: [ 1 3 4 ]
[ 1 5 6 ]
The Required path is:: [ 1 5 4 ]
The Required path is:: [ 1 2 3 4 ]
[ 1 2 4 3 ]
[ 1 5 6 3 ]
[ 1 5 4 3 ]
The Required path is:: [ 1 5 6 3 4 ]
*/
تنطبق خوارزمية Dijkstra أكثر على المسارات المرونة، وغالبا ما يبدو أن الملصق هو الرغبة في العثور على جميع المسارات، وليس فقط الأقصر.
لهذا التطبيق، سأبني رسم بياني (يبدو أن تطبيقك يبدو أنه لن يحتاج إلى توجيهه) واستخدم طريقة البحث المفضلة لديك. يبدو أنك تريد كل المسارات، وليس مجرد تخمين في أقصر واحد، لذلك استخدم خوارزمية متكررة بسيطة من اختيارك.
المشكلة الوحيدة في هذا إذا كان الرسم البياني يمكن أن يكون دائريا.
مع الاتصالات:
- 1, 2
- 1, 3
- 2, 3
- 2, 4
أثناء البحث عن طريق من 1-> 4، هل يمكن أن يكون لديك دورة من 1 -> 2 -> 3 -> 1.
في هذه الحالة، ثم أحتفظ بمكدسة كعقد العقد. إليك قائمة مع خطوات هذا الرسم البياني والمكدس الناتج (آسف للتنسيق - خيار الجدول):
العقدة الحالية (العقد المقبلة ممكنة ناقص حيث وصلنا من) [كومة
- 1 (2, 3) [1]
- 2 (3, 4) [1, 2]
- 3 (1) [1, 2, 3]
- 1 (2، 3) [1، 2، 3، 1] // خطأ - رقم مكرر على المكدس - الدورة المكتشفة
- 3 () [1، 2، 3] // الخلفية إلى العقدة ثلاثة وبعد 1 قبالة المكدس. لا مزيد من العقد لاستكشاف من هنا
- 2 (4) [1، 2] / / صعد إلى العقدة 2 وبرز 1 قبالة المكدس.
- 4 () [1، 2، 4] / / وجدت العقدة المستهدفة - سجل كومة للمسار. لا مزيد من العقد لاستكشاف من هنا
- 2 () [1، 2] // خلع مرة أخرى إلى العقدة 2 وانفزت 4 قبالة المكدس. لا مزيد من العقد لاستكشاف من هنا
- 1 (3) [1] / / خرجت إلى الوراء إلى العقدة 1 وبرز 2 قبالة المكدس.
- 3 (2) [1, 3]
- 2 (1, 4) [1, 3, 2]
- 1 (2، 3) [1، 3، 2، 1] // خطأ - رقم مكرر على المكدس - الدورة المكتشفة
- 2 (4) [1، 3، 2] / / صعدت إلى العقدة 2 وانزفت 1 قبالة المكدس
- 4 () [1، 3، 2، 4] وجدت العقدة المستهدفة - قيادة كومة للمسار. لا مزيد من العقد لاستكشاف من هنا
- 2 () [1، 3، 2] // الخلفية إلى العقدة 2 وتفزف 4 قبالة المكدس. لا مزيد من العقد
- 3 () [1، 3] // خلع مرة أخرى إلى العقدة 3 وبرز 2 قبالة المكدس. لا مزيد من العقد
- 1 () [1] // الخلفية إلى العقدة 1 وتفتيت 3 قبالة المكدس. لا مزيد من العقد
- القيام به مع 2 مسارات مسجلة من [1، 2، 4] و [1، 3، 2، 4
الكود الأصلي مرهقة قليلا وقد ترغب في استخدام المجموعات. بدلا من ذلك، إذا كنت ترغب في استخدام BFS للعثور على ما إذا كان المسار موجود بين 2 نقطة على الرسم البياني. فيما يلي حلا سريعا اخترقته:
ملاحظة: قد تستمر هذه الطريقة بلا حدود إذا كان هناك أي مسار بين العقدتين. لم أختبر جميع الحالات، YMMV.
from collections import deque
# a sample graph
graph = {'A': ['B', 'C','E'],
'B': ['A','C', 'D'],
'C': ['D'],
'D': ['C'],
'E': ['F','D'],
'F': ['C']}
def BFS(start, end):
""" Method to determine if a pair of vertices are connected using BFS
Args:
start, end: vertices for the traversal.
Returns:
[start, v1, v2, ... end]
"""
path = []
q = deque()
q.append(start)
while len(q):
tmp_vertex = q.popleft()
if tmp_vertex not in path:
path.append(tmp_vertex)
if tmp_vertex == end:
return path
for vertex in graph[tmp_vertex]:
if vertex not in path:
q.append(vertex)
في PROLOG (على وجه التحديد، SWI-PROLOG)
:- use_module(library(tabling)).
% path(+Graph,?Source,?Target,?Path)
:- table path/4.
path(_,N,N,[N]).
path(G,S,T,[S|Path]) :-
dif(S,T),
member(S-I, G), % directed graph
path(G,I,T,Path).
اختبار:
paths :- Graph =
[ 1- 2 % node 1 and 2 are connected
, 2- 3
, 2- 5
, 4- 2
, 5-11
,11-12
, 6- 7
, 5- 6
, 3- 6
, 6- 8
, 8-10
, 8- 9
],
findall(Path, path(Graph,1,7,Path), Paths),
maplist(writeln, Paths).
?- paths.
[1,2,3,6,7]
[1,2,5,6,7]
true.
إذا كنت تريد كل المسارات، استخدم العودية.
باستخدام قائمة مجاورة، يفضل إنشاء وظيفة F () التي تحاول ملء قائمة حالية من القمم الزائرة. مثل ذلك:
void allPaths(vector<int> previous, int current, int destination)
{
previous.push_back(current);
if (current == destination)
//output all elements of previous, and return
for (int i = 0; i < neighbors[current].size(); i++)
allPaths(previous, neighbors[current][i], destination);
}
int main()
{
//...input
allPaths(vector<int>(), start, end);
}
نظرا لحقيقة أن هذا المتجه يتم تمريره حسب القيمة (وبالتالي فإن أي تغييرات تم إجراؤها في الإجراءات المتكررة ليست دائمة)، يتم تعداد جميع المجموعات الممكنة.
يمكنك الحصول على القليل من الكفاءة من خلال تمرير السابق ناقل حسب المرجع (وبالتالي لا يحتاج إلى نسخ متجه مرارا وتكرارا) ولكن عليك التأكد من أن الأمور تحصل على popped_back () يدويا.
شيء آخر: إذا كان الرسم البياني له دورات، فلن يعمل هذا. (أفترض في هذه الحالة، سترغب في العثور على جميع بسيط المسارات، ثم) قبل إضافة شيء إلى السابق ناقلات، تحقق أولا مما إذا كان هناك بالفعل هناك.
إذا كنت تريد كل شيء أقصر المسارات، استخدم اقتراح Konrad مع هذه الخوارزمية.
بالنظر إلى المصفوفة المجاورة:
{0, 1, 3, 4, 0, 0}
{0, 0, 2, 1, 2, 0}
{0, 1, 0, 3, 0, 0}
{0, 1, 1, 0, 0, 1}
{0, 0, 0, 0, 0, 6}
{0, 1, 0, 1, 0, 0}
يحل رمز Wolfram Mathematica التالي المشكلة للعثور على جميع المسارات البسيطة بين عقدين من الرسم البياني. لقد استخدمت العودية البسيطة، واثنين من VAR العالمية لتتبع الدورات وتخزين الإخراج المطلوب. لم يتم تحسين الكود فقط من أجل وضوح التعليمات البرمجية. يجب أن يكون "الطباعة" مفيدا لتوضيح كيفية عمله.
cycleQ[l_]:=If[Length[DeleteDuplicates[l]] == Length[l], False, True];
getNode[matrix_, node_]:=Complement[Range[Length[matrix]],Flatten[Position[matrix[[node]], 0]]];
builtTree[node_, matrix_]:=Block[{nodes, posAndNodes, root, pos},
If[{node} != {} && node != endNode ,
root = node;
nodes = getNode[matrix, node];
(*Print["root:",root,"---nodes:",nodes];*)
AppendTo[lcycle, Flatten[{root, nodes}]];
If[cycleQ[lcycle] == True,
lcycle = Most[lcycle]; appendToTree[root, nodes];,
Print["paths: ", tree, "\n", "root:", root, "---nodes:",nodes];
appendToTree[root, nodes];
];
];
appendToTree[root_, nodes_] := Block[{pos, toAdd},
pos = Flatten[Position[tree[[All, -1]], root]];
For[i = 1, i <= Length[pos], i++,
toAdd = Flatten[Thread[{tree[[pos[[i]]]], {#}}]] & /@ nodes;
(* check cycles!*)
If[cycleQ[#] != True, AppendTo[tree, #]] & /@ toAdd;
];
tree = Delete[tree, {#} & /@ pos];
builtTree[#, matrix] & /@ Union[tree[[All, -1]]];
];
];
لاستدعاء الرمز: InitNode = 1؛ endnode = 6؛ lcycle = {}؛ شجرة = {{internode}}؛ الماسة [internode، مصفوفة]؛
المسارات: {{1}} الجذر: 1 --- العقد: {2،3،4}
المسارات: {{1،2}، {1،3}، {1،4}} الجذر: 2 --- العقد: {3،4،5}
المسارات: {{1،3}، {1،4}، {1،2،3}، {1،2،4}، {1،2،5}} الجذر: 3 --- العقد: {2، 4}
المسارات: {{1،4}، {1،2،4}، {1،2،5}، {1،3،4}، {1،2،3،4}، {1،3،2، 4}، {1،3،3،2،5}} الجذر: 4 --- العقد: {2،3،6}
المسارات: {{1،2،5}، {1،3،3،2،5}، {1،4،6}، {1،2،4،6}، {1،3،3،4،6}، { 1،2،3،4،6}، {1،3،2،4،6}، {1،4،2،5،5}، {1،3،4،2،5}، {1،4، 3،2،5}} الجذر: 5 --- العقد: {6}
النتائج: {{1، 4، 6}، {1، 2، 4، 6}، {1، 2، 5، 6}، {1، 3، 4، 6}، {1، 2، 3، 4، 6}، {1، 3، 2، 4، 6}، {1، 3، 2، 5، 6}، {1، 4، 2، 5، 6}، {1، 3، 4، 2، 5، 5، 5، 6}، {1، 4، 3، 2، 5، 6}}
... لسوء الحظ، لا يمكنني تحميل الصور لإظهار النتائج بطريقة أفضل :(
ما تحاول القيام به هو أساسا للعثور على مسار بين رأسين في الرسم البياني (موجه؟) تسجيل المغادرة خوارزمية dijkstra إذا كنت بحاجة إلى أقصر مسار أو كتابة وظيفة متكررة بسيطة إذا كنت بحاجة إلى وجود مسارات.
