Алгоритм графа для поиска всех связей между двумя произвольными вершинами

    If I have the following records:
        A, B, C, D, E

    and the following represents the connections:
        (A,B),(A,C),(B,A),(B,D),(B,E),(B,F),(C,A),(C,E),
        (C,F),(D,B),(E,C),(E,F),(F,B),(F,C),(F,E)

        [where (A,B) means record A connects to record B]

   All paths connecting B to E:
      B->E
      B->F->E
      B->F->C->E
      B->A->C->E
      B->A->C->F->E

import java.util.HashMap;
import java.util.LinkedHashSet;
import java.util.LinkedList;
import java.util.Map;
import java.util.Set;

public class Graph {
    private Map<String, LinkedHashSet<String>> map = new HashMap();

    public void addEdge(String node1, String node2) {
        LinkedHashSet<String> adjacent = map.get(node1);
        if(adjacent==null) {
            adjacent = new LinkedHashSet();
            map.put(node1, adjacent);
        }
        adjacent.add(node2);
    }

    public void addTwoWayVertex(String node1, String node2) {
        addEdge(node1, node2);
        addEdge(node2, node1);
    }

    public boolean isConnected(String node1, String node2) {
        Set adjacent = map.get(node1);
        if(adjacent==null) {
            return false;
        }
        return adjacent.contains(node2);
    }

    public LinkedList<String> adjacentNodes(String last) {
        LinkedHashSet<String> adjacent = map.get(last);
        if(adjacent==null) {
            return new LinkedList();
        }
        return new LinkedList<String>(adjacent);
    }
}

import java.util.LinkedList;

public class Search {

    private static final String START = "B";
    private static final String END = "E";

    public static void main(String[] args) {
        // this graph is directional
        Graph graph = new Graph();
        graph.addEdge("A", "B");
        graph.addEdge("A", "C");
        graph.addEdge("B", "A");
        graph.addEdge("B", "D");
        graph.addEdge("B", "E"); // this is the only one-way connection
        graph.addEdge("B", "F");
        graph.addEdge("C", "A");
        graph.addEdge("C", "E");
        graph.addEdge("C", "F");
        graph.addEdge("D", "B");
        graph.addEdge("E", "C");
        graph.addEdge("E", "F");
        graph.addEdge("F", "B");
        graph.addEdge("F", "C");
        graph.addEdge("F", "E");
        LinkedList<String> visited = new LinkedList();
        visited.add(START);
        new Search().depthFirst(graph, visited);
    }

    private void depthFirst(Graph graph, LinkedList<String> visited) {
        LinkedList<String> nodes = graph.adjacentNodes(visited.getLast());
        // examine adjacent nodes
        for (String node : nodes) {
            if (visited.contains(node)) {
                continue;
            }
            if (node.equals(END)) {
                visited.add(node);
                printPath(visited);
                visited.removeLast();
                break;
            }
        }
        for (String node : nodes) {
            if (visited.contains(node) || node.equals(END)) {
                continue;
            }
            visited.addLast(node);
            depthFirst(graph, visited);
            visited.removeLast();
        }
    }

    private void printPath(LinkedList<String> visited) {
        for (String node : visited) {
            System.out.print(node);
            System.out.print(" ");
        }
        System.out.println();
    }
}

B E
B A C E
B A C F E
B F E
B F C E

Ответ 2 · рейтинг 24 · Michael Dorfman

В онлайн-словаре алгоритмов и структур данных Национального института стандартов и технологий (NIST) эта проблема указана как "все простые пути " и рекомендует использовать поиск в глубину. CLRS предоставляет соответствующие алгоритмы.

Умную технику с использованием сетей Петри можно найти здесь

Ответ 3 · рейтинг 13 · Robert Groves

Вот псевдокод, который я придумал. Это не какой-то конкретный диалект псевдокода, но он должен быть достаточно простым, чтобы следовать ему.

Кто угодно хочет разобрать это на части.

• [p] - это список вершин, представляющих текущий путь.

• [x] - это список путей, удовлетворяющих критериям

• [s] - исходная вершина

• [d] - конечная вершина

• [c] - текущая вершина (аргумент подпрограммы PathFind)

Предположим, существует эффективный способ поиска соседних вершин (строка 6).

     1 PathList [p]
     2 ListOfPathLists [x]
     3 Vertex [s], [d]

     4 PathFind ( Vertex [c] )
     5     Add [c] to tail end of list [p]
     6     For each Vertex [v] adjacent to [c]
     7         If [v] is equal to [d] then
     8             Save list [p] in [x]
     9         Else If [v] is not in list [p]
    10             PathFind([v])
    11     Next For
    12     Remove tail from [p]
    13 Return

Ответ 4 · рейтинг 8 · Ilmari Karonen

Поскольку существующая нерекурсивная реализация DFS, указанная в этот ответ кажется неверным, позвольте предложить тот, который действительно работает.

Я написал это на Python, потому что считаю его довольно читаемым и не загроможденным деталями реализации (и потому что в нем есть удобное ключевое слово yield для реализации генераторы), но его будет довольно легко перенести на другие языки.

# a generator function to find all simple paths between two nodes in a
# graph, represented as a dictionary that maps nodes to their neighbors
def find_simple_paths(graph, start, end):
    visited = set()
    visited.add(start)

    nodestack = list()
    indexstack = list()
    current = start
    i = 0

    while True:
        # get a list of the neighbors of the current node
        neighbors = graph[current]

        # find the next unvisited neighbor of this node, if any
        while i < len(neighbors) and neighbors[i] in visited: i += 1

        if i >= len(neighbors):
            # we've reached the last neighbor of this node, backtrack
            visited.remove(current)
            if len(nodestack) < 1: break  # can't backtrack, stop!
            current = nodestack.pop()
            i = indexstack.pop()
        elif neighbors[i] == end:
            # yay, we found the target node! let the caller process the path
            yield nodestack + [current, end]
            i += 1
        else:
            # push current node and index onto stacks, switch to neighbor
            nodestack.append(current)
            indexstack.append(i+1)
            visited.add(neighbors[i])
            current = neighbors[i]
            i = 0

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

Этот код также использует отдельный набор visited, который всегда содержит текущий узел и любые узлы в стеке, чтобы я мог эффективно проверять, является ли узел уже частью текущего пути. Если ваш язык имеет структуру данных "упорядоченный набор", которая обеспечивает как эффективные, подобные стеку, операции push / pop и эффективные запросы членства, вы можете использовать это для стека узлов и избавиться от отдельных visited набор.

В качестве альтернативы, если вы используете настраиваемый изменяемый класс / структуру для своих узлов, вы можете просто сохранить логический флаг в каждом узле, чтобы указать, был ли он посещен как часть текущего пути поиска. Конечно, этот метод не позволит вам запустить два поиска на одном и том же графике параллельно, если вы по какой-то причине захотите это сделать.

Вот тестовый код, демонстрирующий, как работает приведенная выше функция:

# test graph:
#     ,---B---.
#     A   |   D
#     `---C---'
graph = {
    "A": ("B", "C"),
    "B": ("A", "C", "D"),
    "C": ("A", "B", "D"),
    "D": ("B", "C"),
}

# find paths from A to D
for path in find_simple_paths(graph, "A", "D"): print " -> ".join(path)

Запуск этого кода на приведенном примере графа дает следующий результат:

A -> B -> C -> D
A -> B -> D
A -> C -> B -> D
A -> C -> D

Обратите внимание, что хотя этот пример графа неориентированный (т.е. все его ребра идут в обе стороны), алгоритм также работает для произвольных ориентированных графов. Например, удаление края C -> B (путем удаления B из списка соседей C) дает тот же результат, за исключением третьего пути (A -> C -> B -> D), который больше невозможен.

---

Ps. Легко построить графики, для которых простые алгоритмы поиска, подобные этому (и другим, приведенным в этой теме), работают очень плохо.

Например, рассмотрим задачу поиска всех путей от A до B на неориентированном графе, где у начального узла A есть два соседа: целевой узел B (у которого нет других соседей, кроме A) и узел C, который является частью клика из n +1 узлов, например:

graph = {
    "A": ("B", "C"),
    "B": ("A"),
    "C": ("A", "D", "E", "F", "G", "H", "I", "J", "K", "L", "M", "N", "O"),
    "D": ("C", "E", "F", "G", "H", "I", "J", "K", "L", "M", "N", "O"),
    "E": ("C", "D", "F", "G", "H", "I", "J", "K", "L", "M", "N", "O"),
    "F": ("C", "D", "E", "G", "H", "I", "J", "K", "L", "M", "N", "O"),
    "G": ("C", "D", "E", "F", "H", "I", "J", "K", "L", "M", "N", "O"),
    "H": ("C", "D", "E", "F", "G", "I", "J", "K", "L", "M", "N", "O"),
    "I": ("C", "D", "E", "F", "G", "H", "J", "K", "L", "M", "N", "O"),
    "J": ("C", "D", "E", "F", "G", "H", "I", "K", "L", "M", "N", "O"),
    "K": ("C", "D", "E", "F", "G", "H", "I", "J", "L", "M", "N", "O"),
    "L": ("C", "D", "E", "F", "G", "H", "I", "J", "K", "M", "N", "O"),
    "M": ("C", "D", "E", "F", "G", "H", "I", "J", "K", "L", "N", "O"),
    "N": ("C", "D", "E", "F", "G", "H", "I", "J", "K", "L", "M", "O"),
    "O": ("C", "D", "E", "F", "G", "H", "I", "J", "K", "L", "M", "N"),
}

Легко видеть, что единственный путь между A и B является прямым, но наивная DFS, запущенная с узла A, будет тратить O (n!) Времени на бесполезное исследование путей внутри клики, даже если это очевидно (для человека), что ни один из этих путей не может привести к B.

Также можно создавать DAG с аналогичными свойствами, например имея начальный узел A, соединяющий целевой узел B и два других узла C ₁ и C ₂, оба из которых подключаются к узлам D _{1 sub > и D 2, оба из которых подключаются к E 1 и E 2 и так далее. Для n слоев узлов, расположенных таким образом, наивный поиск всех путей от A до B приведет к потере O (2 ⁿ) времени. прежде чем сдаться, изучите все возможные тупики.}

Конечно, добавление ребра к целевому узлу B из одного из узлов в клике (кроме C) или из последнего уровня DAG создаст экспоненциально большое количество возможных путей. от A до B, и алгоритм чисто локального поиска не может заранее сказать, найдет он такое ребро или нет. Таким образом, в некотором смысле низкая чувствительность вывода таких наивных поисков незнание глобальной структуры графа.

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

Ответ 5 · рейтинг 5 · Haibin Liu

Вот логически более красивый рекурсивный вариант по сравнению со вторым этажом.

public class Search {

private static final String START = "B";
private static final String END = "E";

public static void main(String[] args) {
    // this graph is directional
    Graph graph = new Graph();
    graph.addEdge("A", "B");
    graph.addEdge("A", "C");
    graph.addEdge("B", "A");
    graph.addEdge("B", "D");
    graph.addEdge("B", "E"); // this is the only one-way connection
    graph.addEdge("B", "F");
    graph.addEdge("C", "A");
    graph.addEdge("C", "E");
    graph.addEdge("C", "F");
    graph.addEdge("D", "B");
    graph.addEdge("E", "C");
    graph.addEdge("E", "F");
    graph.addEdge("F", "B");
    graph.addEdge("F", "C");
    graph.addEdge("F", "E");
    List<ArrayList<String>> paths = new ArrayList<ArrayList<String>>();
    String currentNode = START;
    List<String> visited = new ArrayList<String>();
    visited.add(START);
    new Search().findAllPaths(graph, seen, paths, currentNode);
    for(ArrayList<String> path : paths){
        for (String node : path) {
            System.out.print(node);
            System.out.print(" ");
        }
        System.out.println();
    }
}

private void findAllPaths(Graph graph, List<String> visited, List<ArrayList<String>> paths, String currentNode) {
    if (currentNode.equals(END)) {
        paths.add(new ArrayList(Arrays.asList(visited.toArray())));
        return;
    }
    else {
        LinkedList<String> nodes = graph.adjacentNodes(currentNode);
        for (String node : nodes) {
            if (visited.contains(node)) {
                continue;
            }
            List<String> temp = new ArrayList<String>();
            temp.addAll(visited);
            temp.add(node);
            findAllPaths(graph, temp, paths, node);
        }
    }
}
}

Программный вывод

B A C E

B A C F E

B E

B F C E

B F E

Ответ 6 · рейтинг 4 · Leon Chang

Решение в коде C. Он основан на DFS, который использует минимум памяти.

#include <stdio.h>
#include <stdbool.h>

#define maxN    20

struct  nodeLink
{

    char node1;
    char node2;

};

struct  stack
{
    int sp;
    char    node[maxN];
};

void    initStk(stk)
struct  stack   *stk;
{
    int i;
    for (i = 0; i < maxN; i++)
        stk->node[i] = ' ';
    stk->sp = -1;
}

void    pushIn(stk, node)
struct  stack   *stk;
char    node;
{

    stk->sp++;
    stk->node[stk->sp] = node;

}

void    popOutAll(stk)
struct  stack   *stk;
{

    char    node;
    int i, stkN = stk->sp;

    for (i = 0; i <= stkN; i++)
    {
        node = stk->node[i];
        if (i == 0)
            printf("src node : %c", node);
        else if (i == stkN)
            printf(" => %c : dst node.\n", node);
        else
            printf(" => %c ", node);
    }

}


/* Test whether the node already exists in the stack    */
bool    InStack(stk, InterN)
struct  stack   *stk;
char    InterN;
{

    int i, stkN = stk->sp;  /* 0-based  */
    bool    rtn = false;

    for (i = 0; i <= stkN; i++)
    {
        if (stk->node[i] == InterN)
        {
            rtn = true;
            break;
        }
    }

    return     rtn;

}

char    otherNode(targetNode, lnkNode)
char    targetNode;
struct  nodeLink    *lnkNode;
{

    return  (lnkNode->node1 == targetNode) ? lnkNode->node2 : lnkNode->node1;

}

int entries = 8;
struct  nodeLink    topo[maxN]    =
    {
        {'b', 'a'},
        {'b', 'e'},
        {'b', 'd'},
        {'f', 'b'},
        {'a', 'c'},
        {'c', 'f'},
        {'c', 'e'},
        {'f', 'e'},
    };

char    srcNode = 'b', dstN = 'e';

int reachTime;

void    InterNode(interN, stk)
char    interN;
struct  stack   *stk;
{

    char    otherInterN;
    int i, numInterN = 0;
    static  int entryTime   =   0;

    entryTime++;

    for (i = 0; i < entries; i++)
    {

        if (topo[i].node1 != interN  && topo[i].node2 != interN)
        {
            continue;
        }

        otherInterN = otherNode(interN, &topo[i]);

        numInterN++;

        if (otherInterN == stk->node[stk->sp - 1])
        {
            continue;
        }

        /*  Loop avoidance: abandon the route   */
        if (InStack(stk, otherInterN) == true)
        {
            continue;
        }

        pushIn(stk, otherInterN);

        if (otherInterN == dstN)
        {
            popOutAll(stk);
            reachTime++;
            stk->sp --;   /*    back trace one node  */
            continue;
        }
        else
            InterNode(otherInterN, stk);

    }

        stk->sp --;

}


int    main()

{

    struct  stack   stk;

    initStk(&stk);
    pushIn(&stk, srcNode);

    reachTime = 0;
    InterNode(srcNode, &stk);

    printf("\nNumber of all possible and unique routes = %d\n", reachTime);

}

Ответ 7 · рейтинг 3 · batta

Это может быть поздно, но вот та же версия C # алгоритма DFS на Java от Кейси для обхода всех путей между двумя узлами с использованием стека. Читаемость лучше с рекурсивным, как всегда.

    void DepthFirstIterative(T start, T endNode)
    {
        var visited = new LinkedList<T>();
        var stack = new Stack<T>();

        stack.Push(start);

        while (stack.Count != 0)
        {
            var current = stack.Pop();

            if (visited.Contains(current))
                continue;

            visited.AddLast(current);

            var neighbours = AdjacentNodes(current);

            foreach (var neighbour in neighbours)
            {
                if (visited.Contains(neighbour))
                    continue;

                if (neighbour.Equals(endNode))
                {
                    visited.AddLast(neighbour);
                    printPath(visited));
                    visited.RemoveLast();
                    break;
                }
            }

            bool isPushed = false;
            foreach (var neighbour in neighbours.Reverse())
            {
                if (neighbour.Equals(endNode) || visited.Contains(neighbour) || stack.Contains(neighbour))
                {
                    continue;
                }

                isPushed = true;
                stack.Push(neighbour);
            }

            if (!isPushed)
                visited.RemoveLast();
        }
    }

This is a sample graph to test:

    // Sample graph. Numbers are edge ids
    //       1     3
    //    A --- B --- C ----
    //    |     |  2       |
    //    | 4   ----- D    |
    //    ------------------

Ответ 8 · рейтинг 1 · Community

Недавно я решил аналогичную проблему, вместо всех решений, которые меня интересовали только самые короткие.

Я использовал итеративный поиск "в ширину", в котором использовалась очередь состояний, каждая из которых содержала запись, содержащую текущую точку на графике и путь, пройденный для ее достижения.

вы начинаете с единственной записи в очереди, которая имеет начальный узел и пустой путь.

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

Теперь вы можете использовать что-то подобное, но когда вы найдете решение, вместо того, чтобы останавливаться, добавьте это решение в свой "список найденных" и продолжайте.

Вам нужно отслеживать список посещенных узлов, чтобы никогда не отступать от себя, иначе у вас будет бесконечный цикл.

если вы хотите немного больше псевдокода, напишите комментарий или что-то в этом роде, и я уточню.

Ответ 9 · рейтинг 1 · Community

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

Поэтому я не ожидал лучшего алгоритма, чем экспоненциальный.

Я бы сделал возврат и просмотрел весь график. Во избежание циклов сохраняйте все посещенные узлы по пути. Когда вы вернетесь, снимите отметку с узла.

Используя рекурсию:

static bool[] visited;//all false
Stack<int> currentway; initialize empty

function findnodes(int nextnode)
{
if (nextnode==destnode)
{
  print currentway
  return;
}
visited[nextnode]=true;
Push nextnode to the end of currentway.
for each node n accesible from nextnode:
  findnodes(n);
visited[nextnode]=false;
pop from currenteay
}

Или это неправильно?

edit: О, и я забыл: вы должны устранить рекурсивные вызовы, используя этот стек узлов

Ответ 10 · рейтинг 1 · Avinash

Основной принцип - вам не нужно беспокоиться о графиках. Это стандартная проблема, известная как проблема динамического подключения. Существуют следующие типы методов, с помощью которых вы можете добиться, чтобы узлы были подключены или нет:

1. Быстрый поиск
2. Быстрый союз
3. Улучшенный алгоритм (комбинация обоих)

Вот код C, который я пробовал с минимальной временной сложностью O (log * n). Это означает, что для списка ребер 65536 требуется 4 поиска, а для 2 ^ 65536 требуется 5 поисков. Я делюсь своей реализацией алгоритма: Курс алгоритмов Принстонского университета

СОВЕТ. Вы можете найти решение для Java по приведенной выше ссылке с соответствующими пояснениями.

/* Checking Connection Between Two Edges */

#include<stdio.h>
#include<stdlib.h>
#define MAX 100

/*
  Data structure used

vertex[] - used to Store The vertices
size - No. of vertices
sz[] - size of child's
*/

/*Function Declaration */
void initalize(int *vertex, int *sz, int size);
int root(int *vertex, int i);
void add(int *vertex, int *sz, int p, int q);
int connected(int *vertex, int p, int q);

int main() //Main Function
{
char filename[50], ch, ch1[MAX];
int temp = 0, *vertex, first = 0, node1, node2, size = 0, *sz;
FILE *fp;


printf("Enter the filename - "); //Accept File Name
scanf("%s", filename);
fp = fopen(filename, "r");
if (fp == NULL)
{
    printf("File does not exist");
    exit(1);
}
while (1)
{
    if (first == 0) //getting no. of vertices
    {
        ch = getc(fp);
        if (temp == 0)
        {
            fseek(fp, -1, 1);
            fscanf(fp, "%s", &ch1);
            fseek(fp, 1, 1);
            temp = 1;
        }
        if (isdigit(ch))
        {
            size = atoi(ch1);
            vertex = (int*) malloc(size * sizeof(int));     //dynamically allocate size
            sz = (int*) malloc(size * sizeof(int));
            initalize(vertex, sz, size);        //initialization of vertex[] and sz[]
        }
        if (ch == '\n')
        {
            first = 1;
            temp = 0;
        }
    }
    else
    {
        ch = fgetc(fp);
        if (isdigit(ch))
            temp = temp * 10 + (ch - 48);   //calculating value from ch
        else
        {
            /* Validating the file  */

            if (ch != ',' && ch != '\n' && ch != EOF)
            {
                printf("\n\nUnkwown Character Detected.. Exiting..!");

                exit(1);
            }
            if (ch == ',')
                node1 = temp;
            else
            {
                node2 = temp;
                printf("\n\n%d\t%d", node1, node2);
                if (node1 > node2)
                {
                    temp = node1;
                    node1 = node2;
                    node2 = temp;
                }

                /* Adding the input nodes */

                if (!connected(vertex, node1, node2))
                    add(vertex, sz, node1, node2);
            }
            temp = 0;
        }

        if (ch == EOF)
        {
            fclose(fp);
            break;
        }
    }
}

do
{
    printf("\n\n==== check if connected ===");
    printf("\nEnter First Vertex:");
    scanf("%d", &node1);
    printf("\nEnter Second Vertex:");
    scanf("%d", &node2);

    /* Validating The Input */

    if( node1 > size || node2 > size )
    {
        printf("\n\n Invalid Node Value..");
        break;
    }

    /* Checking the connectivity of nodes */

    if (connected(vertex, node1, node2))
        printf("Vertex %d and %d are Connected..!", node1, node2);
    else
        printf("Vertex %d and %d are Not Connected..!", node1, node2);


    printf("\n 0/1:  ");

    scanf("%d", &temp);

} while (temp != 0);

free((void*) vertex);
free((void*) sz);


return 0;
}

void initalize(int *vertex, int *sz, int size) //Initialization of graph
{
int i;
for (i = 0; i < size; i++)
{
    vertex[i] = i;
    sz[i] = 0;
}
}
int root(int *vertex, int i)    //obtaining the root
{
while (i != vertex[i])
{
    vertex[i] = vertex[vertex[i]];
    i = vertex[i];
}
return i;
}

/* Time Complexity for Add --> logn */
void add(int *vertex, int *sz, int p, int q) //Adding of node
{
int i, j;
i = root(vertex, p);
j = root(vertex, q);

/* Adding small subtree in large subtree  */

if (sz[i] < sz[j])
{
    vertex[i] = j;
    sz[j] += sz[i];
}
else
{
    vertex[j] = i;
    sz[i] += sz[j];
}

}

/* Time Complexity for Search -->lg* n */

int connected(int *vertex, int p, int q) //Checking of  connectivity of nodes
{
/* Checking if root is same  */

if (root(vertex, p) == root(vertex, q))
    return 1;

return 0;
}

Ответ 11 · рейтинг 1 · SumNeuron

find_paths [s, t, d, k]

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

Я лично считаю полезным алгоритм вида find_paths[s, t, d, k], где:

• s - начальный узел
• t - целевой узел
• d - максимальная глубина поиска
• k - количество путей, которые нужно найти

Использование бесконечной формы вашего языка программирования для d и k даст вам все пути§.

§ очевидно, что если вы используете ориентированный граф и вам нужны все неориентированные пути между s и t, вам придется выполнить это в обоих направлениях:

find_paths[s, t, d, k] <join> find_paths[t, s, d, k]

---

Вспомогательная функция

Мне лично нравится рекурсия, хотя иногда это может быть сложно, но сначала давайте определим нашу вспомогательную функцию:

def find_paths_recursion(graph, current, goal, current_depth, max_depth, num_paths, current_path, paths_found)
  current_path.append(current)

  if current_depth > max_depth:
    return

  if current == goal:
    if len(paths_found) <= number_of_paths_to_find:
      paths_found.append(copy(current_path))

    current_path.pop()
    return

  else:
    for successor in graph[current]:
    self.find_paths_recursion(graph, successor, goal, current_depth + 1, max_depth, num_paths, current_path, paths_found)

  current_path.pop()

Основная функция

После этого основная функция тривиальна:

def find_paths[s, t, d, k]:
  paths_found = [] # PASSING THIS BY REFERENCE
  find_paths_recursion(s, t, 0, d, k, [], paths_found)

---

Во-первых, отметим несколько моментов:

• приведенный выше псевдокод представляет собой смесь языков, но наиболее сильно напоминает python (так как я просто кодировал на нем). Строгий копипаст не подойдет.
• [] - это неинициализированный список, замените его эквивалентом для выбранного вами языка программирования.
• paths_found передается по ссылке. Понятно, что функция рекурсии ничего не возвращает. Обращайтесь с этим соответствующим образом.
• здесь graph принимает некоторую форму hashed структуры. Есть множество способов реализовать граф. В любом случае graph[vertex] дает вам список смежных вершин в ориентированном графе - скорректируйте его соответствующим образом.
• это предполагает, что у вас есть предварительная обработка для удаления "пряжек" (петель), циклов и многогранников.

Ответ 12 · Ryan Fox

Вот такая мысль пришла мне в голову:

1. Найдите одно соединение. (Поиск в глубину, вероятно, является хорошим алгоритмом для этого, поскольку длина пути не имеет значения.)
2. Отключить последний сегмент.
3. Попробуйте найти другое соединение с последнего узла перед ранее отключенным соединением.
4. Идите к 2, пока не исчезнут соединения.