Ответ 1

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

Я заметил, что приведенный выше график имеет только одно ребро, которое является направленным (B, E). Это опечатка или это действительно ориентированный граф? Это решение работает независимо. Извините, я не смог сделать это на C, я немного слаб в этой области. Я ожидаю, что вы сможете перевести этот код Java без особых проблем.

Graph.java:

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);
    }
}

Search.java:

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

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

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

Ответ 3

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

Кто-то хочет выделить это отдельно.

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

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

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

# 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

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

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

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

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

# 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 на неориентированном графе, где стартовый node A имеет два соседства: цель node B (у которой нет других соседей, чем A), и a node C, который является частью clique из 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, начинающийся с node, будет тратить время O (n!), бесполезно исследуя пути в клике, хотя это очевидно ( человеку), что ни один из этих путей не может привести к B.

Можно также построить DAG со схожими свойствами, например. путём запуска node A target target node B и двух других узлов C ₁ и C ₂, которые соединяются с узлами D ₁ и D ₂, оба из которых подключаются к E ₁ и E ₂ и т.д. Для n слоев узлов, расположенных таким образом, наивный поиск всех путей от A до B закончится тратой времени O (2 ⁿ), исследуя все возможные мертвые точки перед тем, как отказаться.

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

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

Ответ 5

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

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

Решение в коде 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

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

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

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

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

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

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

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

Ответ 8

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

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

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

Использование рекурсии:

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
}

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

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

Ответ 9

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

• Быстрый поиск
• Quick Union
• Улучшенный алгоритм (сочетание обоих)

Вот код 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;
}

Ответ 10

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

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

Ответ 11

find_paths [s, t, d, k]

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

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

• s является стартовым node
• t - цель node
• 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] получает список смежных вершин в ориентированном графе - соответствующим образом отрегулируйте.
• предполагается, что вы предварительно обработали, чтобы удалить "пряжки" (self-loops), циклы и многогранники

Ответ 12

Вот мысль с головы:

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

Ответ 13

Насколько я могу судить о решениях Райана Фокса (58343, Christian (58444), и вы сами (58461) примерно так же хороши, как и получается. Я не верю, что в этом случае помощь в первом порядке помогает, поскольку вы не будет получать все пути. Например, с ребрами (A,B), (A,C), (B,C), (B,D) и (C,D) вы получите пути ABD и ACD, но не ABCD.

Ответ 14

Я нашел способ перечислить все пути, включая бесконечные, содержащие циклы.

http://blog.vjeux.com/2009/project/project-shortest-path.html

Поиск атомных путей и циклов

Definition

Мы хотим найти все возможные пути, идущие от точки A до точки B. Поскольку задействованы циклы, вы не можете просто пройти и перечислить их все. Вместо этого вам придется найти атомный путь, который не будет содержать петли и наименьшие возможные циклы (вы не хотите, чтобы ваш цикл повторялся).

Первое определение, которое я выбрал для атомарного пути, - это путь, который не проходит через тот же самый node дважды. Однако я узнал, что это не все возможности. После некоторой рефлексии я понял, что узлы не важны, однако края есть! Таким образом, путь атома - это путь, который не проходит через один и тот же край дважды.

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

Реализация

Atomic Paths A -> B

Чтобы получить весь путь, начинающийся с точки A, мы будем рекурсивно пересекать график из точки A. Пройдя через дочерний элемент, мы собираемся создать дочерний элемент child → parent, чтобы знать все края, которые мы уже пересекли. Прежде чем мы перейдем к этому ребенку, мы должны пройти этот связанный список и убедиться, что указанный край еще не прошел.

Когда мы дойдем до точки назначения, мы можем сохранить найденный путь.

Freeing the list

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

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

Atomic Cycle A

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

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

Сочетание атомных путей и циклов

В этот момент у нас есть все пути атома, идущие от A до B и все атомные циклы каждого node, оставленные нам для организации всего, чтобы получить кратчайший путь. Отныне мы будем изучать, как найти наилучшую комбинацию атомных циклов в атомном пути.

Ответ 15

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

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

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

I blogged об этой самой теме совсем недавно, опубликовав пример реализации на С++ в этом процессе.

Ответ 16

Добавив к Кейси Уотсону ответ, вот еще одна реализация Java. Инициализация посещенного node с началом node.

private void getPaths(Graph graph, LinkedList<String> visitedNodes) {
                LinkedList<String> adjacent = graph.getAdjacent(visitedNodes.getLast());
                for(String node : adjacent){
                    if(visitedNodes.contains(node)){
                        continue;
                    }
                    if(node.equals(END)){
                        visitedNodes.add(node);
                        printPath(visitedNodes);
                        visitedNodes.removeLast();
                    }
                    visitedNodes.add(node);
                    getPaths(graph, visitedNodes);
                    visitedNodes.removeLast();  
                }
            }