Próbuję określić najlepszy czasowo algorytm do wykonania opisanego poniżej zadania.

Mam zestaw rekordów. Dla tego zestawu rekordów mam dane połączeń, które wskazują, jak pary rekordów z tego zestawu łączą się ze sobą. Zasadniczo reprezentuje to wykres nie skierowany, z rekordami będącymi wierzchołkami, a danymi połączenia krawędziami.

Wszystkie rekordy w zestawie zawierają informacje o połączeniu (tj. Nie ma żadnych osieroconych rekordów; każdy rekord w zestawie łączy się z jednym lub kilkoma innymi rekordami w zestawie).

Chcę wybrać dowolne dwa rekordy z zestawu i móc pokazać wszystkie proste ścieżki między wybranymi rekordami. Przez „proste ścieżki” rozumiem ścieżki, które nie mają powtarzających się zapisów na ścieżce (tj. Tylko ścieżki skończone).

Uwaga: dwa wybrane rekordy zawsze będą różne (tj. Wierzchołek początkowy i końcowy nigdy nie będą takie same; bez cykli).

Na przykład:

    Jeśli mam następujące rekordy:
        A, B, C, D, E.

    a następujący przedstawia połączenia: 
        (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)

        [gdzie (A, B) oznacza, że ​​rekord A łączy się z rekordem B]

Gdybym wybrał B jako mój rekord początkowy i E jako rekord końcowy, chciałbym znaleźć wszystkie proste ścieżki przez połączenia rekordów, które łączyłyby rekord B z rekordem E.

   Wszystkie ścieżki łączące B z E:
      B-> E
      B-> F-> E
      B-> F-> C-> E
      B-> A-> C-> E
      B-> A-> C-> F-> E

To jest przykład, w praktyce mogę mieć zestawy zawierające setki tysięcy rekordów.

Wydaje się, że można to osiągnąć, przeszukując wykres najpierw w głąb. Przeszukiwanie w głąb znajdzie wszystkie niecykliczne ścieżki między dwoma węzłami. Ten algorytm powinien być bardzo szybki i skalowany do dużych wykresów (struktura danych wykresu jest rzadka, więc zużywa tylko tyle pamięci, ile potrzebuje).

Zauważyłem, że wykres, który wskazałeś powyżej, ma tylko jedną krawędź, która jest kierunkowa (B, E). Czy to była literówka, czy naprawdę jest to wykres skierowany? To rozwiązanie działa niezależnie. Przepraszam, że nie mogłem tego zrobić w C, jestem trochę słaby w tej dziedzinie. Spodziewam się jednak, że będziesz w stanie przetłumaczyć ten kod Java bez większych problemów.

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

Wyjście programu:

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

Internetowy Słownik Algorytmów i Struktur Danych Narodowego Instytutu Standardów i Technologii (NIST) wymienia ten problem jako „ wszystkie proste ścieżki” i zaleca przeszukiwanie w głąb . CLRS dostarcza odpowiednie algorytmy.

Sprytny technika przy użyciu sieci Petriego znajduje się tutaj

Oto pseudokod, który wymyśliłem. Nie jest to żaden szczególny dialekt pseudokodu, ale powinien być na tyle prosty do naśladowania.

Każdy chce to rozebrać.

• [p] to lista wierzchołków reprezentujących bieżącą ścieżkę.

• [x] to lista ścieżek spełniających kryteria

• [s] jest wierzchołkiem źródłowym

• [d] jest wierzchołkiem docelowym

• [c] to bieżący wierzchołek (argument do procedury PathFind)

Załóżmy, że istnieje skuteczny sposób wyszukiwania sąsiednich wierzchołków (wiersz 6).

     1 PathList [p]
     2 ListOfPathLists [x]
     3 wierzchołek [s], [d]

     4 PathFind (wierzchołek [c])
     5 Dodaj [c] na końcu listy [p]
     6 Dla każdego wierzchołka [v] sąsiadującego z [c]
     7 Jeśli [v] jest równe [d], to
     8 Zapisz listę [p] w [x]
     9 W przeciwnym razie, jeśli [v] nie znajduje się na liście [p]
    10 PathFind ([v])
    11 Następna dla
    12 Usuń ogon z [p]
    13 Powrót

Ponieważ istniejąca nierekurencyjna implementacja DFS podana w tej odpowiedzi wydaje się być zepsuta, pozwólcie, że przedstawię taką, która faktycznie działa.

Napisałem to w Pythonie, ponieważ uważam, że jest dość czytelny i niezakłócony szczegółami implementacji (i ponieważ zawiera przydatne yieldsłowo kluczowe do implementacji generatorów ), ale powinno być dość łatwe do przeniesienia na inne języki.

# 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

Ten kod utrzymuje dwa równoległe stosy: jeden zawierający wcześniejsze węzły w bieżącej ścieżce i jeden zawierający bieżący indeks sąsiadów dla każdego węzła w stosie węzłów (abyśmy mogli wznowić iterację przez sąsiadów węzła, gdy go wycofamy stos). Równie dobrze mogłem użyć pojedynczego stosu par (węzeł, indeks), ale pomyślałem, że metoda z dwoma stosami byłaby bardziej czytelna i być może łatwiejsza do wdrożenia dla użytkowników innych języków.

Ten kod używa również oddzielnego visitedzestawu, który zawsze zawiera bieżący węzeł i wszystkie węzły na stosie, aby umożliwić mi efektywne sprawdzenie, czy węzeł jest już częścią bieżącej ścieżki. Jeśli zdarzy się, że Twój język ma strukturę danych „uporządkowanego zestawu”, która zapewnia zarówno wydajne operacje push / pop podobne do stosu, jak i wydajne zapytania członkostwa, możesz użyć tego dla stosu węzłów i pozbyć się oddzielnego visitedzestawu.

Alternatywnie, jeśli używasz niestandardowej mutowalnej klasy / struktury dla swoich węzłów, możesz po prostu przechowywać flagę logiczną w każdym węźle, aby wskazać, czy został odwiedzony jako część bieżącej ścieżki wyszukiwania. Oczywiście ta metoda nie pozwoli ci przeprowadzić równolegle dwóch wyszukiwań na tym samym wykresie, jeśli z jakiegoś powodu chcesz to zrobić.

Oto kod testowy demonstrujący działanie funkcji podanej powyżej:

# 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)

Uruchomienie tego kodu na podanym przykładowym wykresie daje następujące dane wyjściowe:

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

Zauważ, że chociaż ten przykładowy graf jest nieukierunkowany (tj. Wszystkie jego krawędzie idą w obie strony), algorytm działa również dla dowolnie ukierunkowanych grafów. Na przykład usunięcie C -> Bkrawędzi (przez usunięcie Bz listy sąsiadów C) daje takie same wyniki, z wyjątkiem trzeciej ścieżki ( A -> C -> B -> D), która nie jest już możliwa.

Ps. Łatwo jest skonstruować wykresy, dla których proste algorytmy wyszukiwania, takie jak ten (i inne podane w tym wątku), działają bardzo słabo.

Na przykład rozważmy zadanie znalezienia wszystkich ścieżek od A do B na grafie niekierowanym, gdzie węzeł początkowy A ma dwóch sąsiadów: węzeł docelowy B (który nie ma innych sąsiadów niż A) i węzeł C będący częścią kliki. z n +1 węzłów, na przykład:

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"),
}

Łatwo zauważyć, że jedyna ścieżka między A i B jest bezpośrednia, ale naiwny DFS uruchomiony z węzła A zmarnuje O ( n !) Czas bezużytecznie eksplorując ścieżki wewnątrz kliki, mimo że jest oczywiste (dla człowieka), że żadna z tych ścieżek nie może prowadzić do B.

Można również konstruować DAG o podobnych właściwościach, np. Poprzez połączenie węzła początkowego A węzła docelowego B i dwóch innych węzłów C ₁ i C ₂ , z których oba łączą się z węzłami D ₁ i D ₂ , z których oba łączą się z E ₁ i E ₂ i tak dalej. Dla n warstw węzłów ułożonych w ten sposób naiwne poszukiwanie wszystkich ścieżek od A do B zakończy się marnowaniem O (2 ⁿ ) czasu na zbadanie wszystkich możliwych ślepych uliczek, zanim się poddaje.

Oczywiście dodanie krawędzi do węzła docelowego B z jednym z węzłów w klika (inne niż C) lub od ostatniej warstwy DAG, by utworzyć wykładniczo dużą liczbę możliwych ścieżek z A do B, a czysto lokalny algorytm wyszukiwania nie jest w stanie z góry powiedzieć, czy znajdzie taką krawędź, czy nie. Zatem w pewnym sensie niska wrażliwość wyników takich naiwnych wyszukiwań wynika z braku świadomości globalnej struktury wykresu.

Chociaż istnieją różne metody przetwarzania wstępnego (takie jak iteracyjne eliminowanie węzłów liści, wyszukiwanie separatorów wierzchołków pojedynczych węzłów itp.), Których można by użyć do uniknięcia niektórych z tych „ślepych zaułków w czasie wykładniczym”, nie znam żadnych ogólnych sztuczka z przetwarzaniem wstępnym, która może je wyeliminować we wszystkich przypadkach. Ogólnym rozwiązaniem byłoby sprawdzenie na każdym etapie wyszukiwania, czy węzeł docelowy jest nadal osiągalny (za pomocą wyszukiwania podrzędnego) i cofnięcie się wcześniej, jeśli tak nie jest - ale niestety, to znacznie spowolniłoby wyszukiwanie (w najgorszym przypadku proporcjonalnie do wielkości wykresu) dla wielu wykresów, które nie zawierają takich patologicznych ślepych zaułków.

Oto logicznie lepiej wyglądająca wersja rekurencyjna w porównaniu z drugim piętrem.

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

Wyjście programu

B A C E 

B A C F E 

B E

B F C E

B F E 

Rozwiązanie w kodzie C. Opiera się na systemie plików DFS, który wykorzystuje minimalną ilość pamięci.

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

}

To może być późno, ale oto ta sama wersja C # algorytmu DFS w Javie z Casey do przechodzenia dla wszystkich ścieżek między dwoma węzłami przy użyciu stosu. Czytelność jest lepsza w przypadku rekurencji, jak zawsze.

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

Oto przykładowy wykres do przetestowania:

    // Przykładowy wykres. Liczby to identyfikatory krawędzi
    // 1 3       
    // A --- B --- C ----
    // | | 2 |
    // | 4 ----- D |
    // ------------------

Podobny problem rozwiązałem ostatnio, zamiast wszystkich rozwiązań interesowało mnie tylko najkrótsze.

Użyłem wyszukiwania iteracyjnego „najpierw wszerz”, które wykorzystywało kolejkę statusu ”, z których każdy zawierał rekord zawierający bieżący punkt na wykresie i ścieżkę prowadzącą do niego.

zaczynasz od pojedynczego rekordu w kolejce, który ma węzeł początkowy i pustą ścieżkę.

Każda iteracja po kodzie zdejmuje pozycję z nagłówka listy i sprawdza, czy jest to rozwiązanie (otrzymany węzeł to ten, który chcesz, jeśli tak, to skończymy), w przeciwnym razie konstruuje nowy element kolejki z węzłami łączącymi się z bieżącym węzłem i zmienione ścieżki oparte na ścieżce poprzedniego węzła, z nowym skokiem dołączonym na końcu.

Teraz możesz użyć czegoś podobnego, ale kiedy znajdziesz rozwiązanie, zamiast się zatrzymywać, dodaj to rozwiązanie do swojej „listy znalezionych” i kontynuuj.

Musisz śledzić listę odwiedzonych węzłów, aby nigdy nie cofać się do siebie, w przeciwnym razie masz nieskończoną pętlę.

jeśli chcesz trochę więcej pseudokodu, napisz komentarz lub coś, a ja rozwinę.

Myślę, że powinieneś opisać swój prawdziwy problem, który za tym stoi. Mówię to, ponieważ prosisz o coś efektywnego czasowo, ale odpowiedź na problem wydaje się rosnąć wykładniczo!

Dlatego nie spodziewałbym się lepszego algorytmu niż czegoś wykładniczego.

Wycofywałbym się i przeglądał cały wykres. Aby uniknąć cykli, po drodze zapisuj wszystkie odwiedzane węzły. Kiedy wrócisz, odznacz węzeł.

Korzystanie z rekursji:

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
}

Czy to źle?

edit: Aha, i zapomniałem: Powinieneś wyeliminować wywołania rekurencyjne, wykorzystując ten stos węzłów

Podstawową zasadą jest to, że nie musisz martwić się o wykresy - jest to standardowy problem znany jako problem z łącznością dynamiczną. Istnieją następujące typy metod, z których można uzyskać węzły są połączone lub nie:

1. Szybkie wyszukiwanie
2. Szybka Unia
3. Ulepszony algorytm (połączenie obu)

Oto kod C, który próbowałem z minimalną złożonością czasową O (log * n) Oznacza to, że dla 65536 listy krawędzi wymaga 4 wyszukiwań, a dla 2 ^ 65536 wymaga 5 wyszukiwań. Udostępniam swoją implementację z algorytmu: Algorithm Course z Uniwersytetu Princeton

WSKAZÓWKA: Możesz znaleźć rozwiązanie Java z linku udostępnionego powyżej z odpowiednimi wyjaśnieniami.

/* 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;
}

znajdź_ścieżki [s, t, d, k]

To pytanie jest stare i już na nie odpowiedział. Jednak żaden nie pokazuje być może bardziej elastycznego algorytmu do osiągnięcia tego samego. Więc wrzucę kapelusz do ringu.

Osobiście find_paths[s, t, d, k]przydaje mi się algorytm postaci , gdzie:

• s jest węzłem początkowym
• t jest węzłem docelowym
• d to maksymalna głębokość wyszukiwania
• k to liczba ścieżek do znalezienia

Korzystanie z nieskończoności w języku programowania dla dik zapewni Ci wszystkie ścieżki§.

§ oczywiście jeśli używasz skierowanego wykresu i chcesz, aby wszystko było nieukierunkowane ścieżki pomiędzys i ttrzeba będzie uruchomić to w obie strony:

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

Funkcja pomocnika

Osobiście lubię rekurencję, chociaż czasami może to być trudne, w każdym razie najpierw zdefiniujmy naszą funkcję pomocniczą:

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

Główna funkcja

Z tego powodu podstawowa funkcja jest trywialna:

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

Najpierw zwróćmy uwagę na kilka rzeczy:

• powyższy pseudokod to mash-up języków - ale najbardziej przypominający Pythona (ponieważ właśnie w nim kodowałem). Ścisłe kopiowanie i wklejanie nie będzie działać.
• [] jest listą niezainicjowaną, zamień ją na odpowiednik dla wybranego języka programowania
• paths_found jest omijany odniesienie . Jest jasne, że funkcja rekurencyjna nic nie zwraca. Zajmij się tym odpowiednio.
• tutaj graphprzyjmuje jakąś formę hashedstruktury. Istnieje wiele sposobów implementacji wykresu. Tak czy inaczej, graph[vertex]wyświetla listę sąsiednich wierzchołków w a skierowanym wykresie - odpowiednio dostosuj.
• przy założeniu, że zostały wstępnie przetworzone, aby usunąć „sprzączki” (pętle własne), cykle i wielokrotne krawędzie

Oto myśl z góry mojej głowy:

1. Znajdź jedno połączenie. (Przeszukiwanie w głąb jest prawdopodobnie dobrym algorytmem do tego celu, ponieważ długość ścieżki nie ma znaczenia).
2. Wyłącz ostatni segment.
3. Spróbuj znaleźć inne połączenie z ostatniego węzła przed poprzednio wyłączonym połączeniem.
4. Idź do 2, aż nie będzie więcej połączeń.

O ile wiem, rozwiązania podane przez Ryana Foxa ( 58343 , Christiana ( 58444 ) i Ciebie ( 58461 )) są prawie tak dobre, jak to tylko możliwe. nie wszystkie ścieżki. Na przykład z krawędziami(A,B) , (A,C), (B,C), (B,D)a (C,D)dostaniesz ścieżki ABDi ACD, ale nie ABCD.

Znalazłem sposób na wyliczenie wszystkich ścieżek, w tym nieskończonych zawierających pętle.

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

Znajdowanie ścieżek i cykli atomowych

Definition

Chcemy znaleźć wszystkie możliwe ścieżki prowadzące z punktu A do punktu B. Ponieważ w grę wchodzą cykle, nie można po prostu przejść i wyliczyć ich wszystkich. Zamiast tego będziesz musiał znaleźć ścieżkę atomową, która nie zapętla się i jak najmniejsze możliwe cykle (nie chcesz, aby cykl się powtarzał).

Pierwsza definicja ścieżki atomowej, którą przyjąłem, to ścieżka, która nie przechodzi dwukrotnie przez ten sam węzeł. Jednak okazało się, że nie wykorzystuje wszystkich możliwości. Po chwili zastanowienia doszedłem do wniosku, że węzły nie są ważne, ale krawędzie są! Tak więc ścieżka atomowa to ścieżka, która nie przechodzi dwukrotnie przez tę samą krawędź.

Ta definicja jest przydatna, działa również dla cykli: atomowy cykl punktu A to atomowa ścieżka, która biegnie od punktu A i kończy się do punktu A.

Realizacja

Atomic Paths A -> B

Aby uzyskać całą ścieżkę zaczynającą się od punktu A, będziemy rekurencyjnie przechodzić przez wykres od punktu A.Podczas przechodzenia przez dziecko utworzymy link child -> parent, aby poznać wszystkie krawędzie, które już przekroczyłem. Zanim przejdziemy do tego dziecka, musimy przejść przez tę połączoną listę i upewnić się, że określona krawędź nie została już przejęta.

Kiedy dotrzemy do punktu docelowego, możemy zapisać znalezioną ścieżkę.

Freeing the list

Problem pojawia się, gdy chcesz zwolnić połączoną listę. Zasadniczo jest to drzewo połączone łańcuchem w odwrotnej kolejności. Rozwiązaniem byłoby podwójne połączenie tej listy i po znalezieniu wszystkich atomowych ścieżek uwolnienie drzewa od punktu początkowego.

Ale sprytnym rozwiązaniem jest użycie liczenia referencji (zainspirowane Garbage Collection). Za każdym razem, gdy dodajesz łącze do rodzica, dodajesz jeden do jego liczby odwołań. Następnie, gdy dojdziesz do końca ścieżki, cofasz się i jesteś wolny, podczas gdy liczba odniesień wynosi 1. Jeśli jest wyższa, po prostu usuwasz jedną i zatrzymujesz się.

Atomic Cycle A

Szukanie atomowego cyklu A jest tym samym, co szukanie atomowej ścieżki od A do A. Jest jednak kilka optymalizacji, które możemy zrobić. Po pierwsze, kiedy docieramy do punktu docelowego, chcemy zapisać ścieżkę tylko wtedy, gdy suma kosztów krawędzi jest ujemna: chcemy tylko przejść przez cykle absorpcyjne.

Jak widzieliście wcześniej, podczas poszukiwania atomowej ścieżki przechodzi się przez cały wykres. Zamiast tego możemy ograniczyć obszar wyszukiwania do silnie połączonego komponentu zawierającego A. Znalezienie tych komponentów wymaga prostego przejścia grafu za pomocą algorytmu Tarjana.

Łączenie ścieżek i cykli atomowych

W tym momencie mamy wszystkie ścieżki atomowe, które biegną od A do B i wszystkie cykle atomowe każdego węzła, które zostały nam pozostawione do zorganizowania wszystkiego, aby uzyskać najkrótszą ścieżkę. Od teraz będziemy się uczyć, jak znaleźć najlepszą kombinację cykli atomowych na ścieżce atomowej.

Jak umiejętnie opisali niektórzy z innych plakatów, problem w skrócie polega na wykorzystaniu algorytmu przeszukiwania w głąb do rekurencyjnego przeszukiwania grafu pod kątem wszystkich kombinacji ścieżek między komunikującymi się węzłami końcowymi.

Sam algorytm rozpoczyna się od węzła początkowego, który mu podasz, bada wszystkie jego linki wychodzące i postępuje, rozszerzając pierwszy węzeł potomny drzewa wyszukiwania, które się pojawi, przeszukując coraz głębiej, aż do znalezienia węzła docelowego lub do momentu napotkania węzła która nie ma dzieci.

Wyszukiwanie jest następnie cofane, wracając do ostatniego węzła, którego jeszcze nie zakończyło.

Całkiem niedawno pisałem na ten temat na blogu , zamieszczając przykładową implementację C ++ w procesie.

Dodając do odpowiedzi Casey Watson, oto kolejna implementacja Java. Inicjowanie odwiedzonego węzła z węzłem początkowym.

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