Найти пути между двумя заданными узлами? - PullRequest
Новая
       51

Найти пути между двумя заданными узлами?

43 голосов
/ 03 апреля 2009

Скажем, у меня есть узлы, подключенные описанным ниже способом, как мне узнать количество путей, существующих между заданными точками, и сведения о пути? 

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

alt text

реализация найдена здесь хорошо, я собираюсь использовать тот же

Вот фрагмент вышеуказанной ссылки в python 

# 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']

Ответы [ 8 ]

33 голосов
/ 03 апреля 2009

Поиск в ширину пересекает график и фактически находит все пути от начального узла. Однако обычно BFS не поддерживает все пути. Вместо этого он обновляет предшествующую функцию π, чтобы сохранить кратчайший путь. Вы можете легко изменить алгоритм так, чтобы π(n) не только сохранял один предшественник, но и список возможных предшественников.

Тогда все возможные пути кодируются в этой функции, и рекурсивно обходя π, вы получаете все возможные комбинации путей.

Один хороший псевдокод, использующий эти обозначения, можно найти в Введение в алгоритмы Кормена и др. и впоследствии был использован во многих университетских сценариях по этому вопросу. Поиск Google «BFS псевдокод предшественник π» выкорчевывает этот удар по стеку Exchange .

23 голосов
/ 04 июня 2012

Для тех, кто не является экспертом 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 ]


*/
7 голосов
/ 03 апреля 2009

Алгоритм Дейкстры больше применяется к взвешенным путям, и похоже, что постер хотел найти все пути, а не только самые короткие.

Для этого приложения я бы построил график (ваше приложение звучит так, будто его не нужно направлять) и использовал ваш любимый метод поиска. Звучит так, будто вам нужны все пути, а не только предположение о самом коротком, поэтому используйте простой рекурсивный алгоритм по вашему выбору.

Единственная проблема с этим, если график может быть циклическим.

Со связями:

  • 1, 2
  • 1, 3
  • 2, 3
  • 2, 4

При поиске пути от 1-> 4, вы можете иметь цикл 1 -> 2 -> 3 -> 1.

В таком случае, я бы оставил стек как обход узлов. Вот список шагов для этого графика и полученного стека (извините за форматирование - без таблицы):

текущий узел (возможные следующие узлы минус, откуда мы пришли) [стек]

  1. 1 (2, 3) [1]
  2. 2 (3, 4) [1, 2]
  3. 3 (1) [1, 2, 3]
  4. 1 (2, 3) [1, 2, 3, 1] // ошибка - дубликат числа в стеке - обнаружен цикл
  5. 3 () [1, 2, 3] // отступили на третий узел и вытолкнули 1 из стека. Здесь больше нет узлов для исследования
  6. 2 (4) [1, 2] // отступили к узлу 2 и вытолкнули 1 из стека.
  7. 4 () [1, 2, 4] // Целевой узел найден - стек записей для пути. Здесь больше нет узлов для исследования
  8. 2 () [1, 2] // отступили к узлу 2 и вытолкнули 4 из стека. Здесь больше нет узлов для исследования
  9. 1 (3) [1] // вернулись назад к узлу 1 и вытолкнули 2 из стека.
  10. 3 (2) [1, 3]
  11. 2 (1, 4) [1, 3, 2]
  12. 1 (2, 3) [1, 3, 2, 1] // ошибка - дубликат числа в стеке - обнаружен цикл
  13. 2 (4) [1, 3, 2] // отступили к узлу 2 и вытолкнули 1 из стека
  14. 4 () [1, 3, 2, 4] Найден целевой узел - стек записей для пути. Здесь больше нет узлов для исследования
  15. 2 () [1, 3, 2] // отступили к узлу 2 и вытолкнули 4 из стека. Нет больше узлов
  16. 3 () [1, 3] // отступили к узлу 3 и вытолкнули 2 из стека. Нет больше узлов
  17. 1 () [1] // возвращаемся назад к узлу 1 и выталкиваем 3 из стека. Нет больше узлов
  18. Совершено с 2 записанными путями [1, 2, 4] и [1, 3, 2, 4]
3 голосов
/ 15 сентября 2016

In Пролог (в частности, SWI-Пролог) 

:- 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.
3 голосов
/ 20 июля 2009

Исходный код немного громоздок, и вы можете вместо этого использовать collection.deque, если хотите использовать 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)
2 голосов
/ 23 августа 2012

с учетом матрицы смежности:

{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 = {}; дерево = {{initNode}}; builtTree [initNode, matrix];

путей: {{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,2,5}} корень: 4 --- узлы: {2,3,6}

путей: {{1,2,5}, {1,3,2,5}, {1,4,6}, {1,2,4,6}, {1,3,4,6 }, {1,2,3,4,6}, {1,3,2,4,6}, {1,4,2,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, 6}, {1, 4, 3, 2, 5, 6}}

... К сожалению, я не могу загрузить изображения для лучшего отображения результатов: (

http://textanddatamining.blogspot.com

2 голосов
/ 03 апреля 2009

Если вы хотите все пути, используйте рекурсию.

Используя список смежности, предпочтительно, создайте функцию 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 ( ) вручную.

Еще одна вещь: если у графа есть циклы, это не сработает. (Я предполагаю, что в этом случае вы захотите найти все простые пути, затем.) Прежде чем добавлять что-либо в предыдущий вектор, сначала проверьте, уже там ли оно.

Если вам нужны все кратчайшие пути, используйте предложение Конрада с этим алгоритмом.

0 голосов
/ 03 апреля 2009

То, что вы пытаетесь сделать, это, по сути, найти путь между двумя вершинами (направленного?) Графа. Проверьте Алгоритм Дейкстры , если вам нужен кратчайший путь, или напишите простую рекурсивную функцию, если вам нужно какие бы пути ни существовали.

...