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

У меня есть набор рекордов. Для этого набора записей у меня есть данные соединения, которые показывают, как пары записей из этого набора соединяются друг с другом. Это в основном представляет собой неориентированный граф, в котором записи являются вершинами, а данные соединения - ребрами.

Все записи в наборе имеют информацию о соединении (т. Е. Отсутствуют потерянные записи; каждая запись в наборе соединяется с одной или несколькими другими записями в наборе).

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

Примечание: две выбранные записи всегда будут разными (т.е. начальная и конечная вершины никогда не будут одинаковыми; циклов нет).

Например:

    Если у меня есть следующие записи:
        A, B, C, D, E

    и следующее представляет соединения: 
        (А, В), (А, С), (В, А), (В, D), (В, Е), (В, F), (С, А), (С, Е),
        (C, F), (D, В), (Е, С), (Е, F), (Р, В), (Р, С), (F, Е)

        [где (A, B) означает, что запись A подключается к записи B]

Если бы я выбрал B в качестве начальной записи и E в качестве конечной записи, я бы хотел найти все простые пути через соединения записей, которые соединяли бы запись B с записью E.

   Все пути, соединяющие B и E:
      B-> E
      B-> F-> Е
      B-> F-> С-> Е
      В-> А-> С-> Е
      В-> А-> С-> F-> Е

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

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

Я заметил, что указанный вами график имеет только одно направленное ребро (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 

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

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

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

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

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

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

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

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

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

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

     1 PathList [p]
     2 ListOfPathLists [x]
     3 Вершина [s], [d]

     4 PathFind (вершина [c])
     5 Добавить [c] в конец списка [p]
     6 Для каждой вершины [v], смежной с [c]
     7 Если [v] равно [d], то
     8 Сохранить список [p] в [x]
     9 Иначе Если [v] нет в списке [p]
    10 PathFind ([v])
    11 Далее Для
    12 Удалить хвост из [p]
    13 Возврат

Поскольку существующая нерекурсивная реализация 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)

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

А -> В -> С -> D
А -> Б -> D
А -> С -> В -> D
А -> С -> 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 ₁ и D ₂ , оба из которых подключаются к E ₁ и E ₂ и так далее. Для n слоев узлов, расположенных таким образом, наивный поиск всех путей от A до B приведет к потере O (2 ⁿ ) времени на изучение всех возможных тупиков, прежде чем отказаться.

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

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

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

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 

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

}

Это может быть поздно, но вот та же версия 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();
        }
    }

Это образец графика для тестирования:

    // Пример графика. Числа - идентификаторы ребер
    // 1 3       
    // A --- B --- C ----
    // | | 2 |
    // | 4 ----- D |
    // ------------------

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

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

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

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

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

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

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

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

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

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

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

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: О, и я забыл: вы должны устранить рекурсивные вызовы, используя этот стек узлов

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

1. Быстрый поиск
2. Quick Union
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;
}

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

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

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

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

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

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

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

Definition

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

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

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

Реализация

Atomic Paths A -> B

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

По прибытии в пункт назначения мы можем сохранить найденный путь.

Freeing the list

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

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

Atomic Cycle A

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

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

Объединение атомных путей и циклов

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

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

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

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

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

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

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