Algoritma Grafik Untuk Menemukan Semua Koneksi Antara Dua Simpul Sewenang-wenang

117

Saya mencoba untuk menentukan algoritma efisien waktu terbaik untuk menyelesaikan tugas yang dijelaskan di bawah ini.

Saya memiliki satu set catatan. Untuk kumpulan rekaman ini saya memiliki data koneksi yang menunjukkan bagaimana pasangan rekaman dari kumpulan ini terhubung satu sama lain. Ini pada dasarnya mewakili grafik yang tidak diarahkan, dengan catatan menjadi simpul dan data koneksi sebagai tepinya.

Semua catatan dalam set memiliki informasi koneksi (yaitu tidak ada catatan yatim piatu yang ada; setiap catatan dalam set terhubung ke satu atau lebih catatan lain dalam set).

Saya ingin memilih dua rekaman dari set dan dapat menunjukkan semua jalur sederhana antara rekaman yang dipilih. Yang saya maksud dengan "jalur sederhana" adalah jalur yang tidak memiliki rekaman berulang dalam jalur (yaitu jalur terbatas saja).

Catatan: Dua record yang dipilih akan selalu berbeda (yaitu simpul awal dan akhir tidak akan pernah sama; tidak ada siklus).

Sebagai contoh:

    Jika saya memiliki catatan berikut:
        A, B, C, D, E

    dan yang berikut ini mewakili koneksi: 
        (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)

        [di mana (A, B) berarti record A terhubung ke record B]

Jika saya memilih B sebagai rekaman awal saya dan E sebagai rekaman akhir saya, saya ingin menemukan semua jalur sederhana melalui koneksi rekaman yang akan menghubungkan rekaman B ke rekaman E.

   Semua jalur yang menghubungkan B ke E:
      B-> E
      B-> F-> E
      B-> F-> C-> E
      B-> A-> C-> E
      B-> A-> C-> F-> E

Ini adalah contoh, dalam praktiknya saya mungkin memiliki set yang berisi ratusan ribu rekaman.

Robert Groves
sumber
Sambungan disebut siklus , dan jawaban ini memiliki banyak informasi untuk Anda.
elhoim
3
Silakan katakan apakah Anda menginginkan daftar terbatas dari koneksi bebas loop, atau aliran koneksi tak terbatas dengan semua kemungkinan loop. Cf. Jawaban Blorgbeard.
Charles Stewart
adakah yang bisa membantu dengan ini ??? stackoverflow.com/questions/32516706/…
tejas3006

Jawaban:

116

Tampaknya hal ini dapat dilakukan dengan penelusuran grafik yang paling dalam. Pencarian kedalaman-pertama akan menemukan semua jalur non-siklus antara dua node. Algoritme ini harus sangat cepat dan berskala ke grafik besar (Struktur data grafik jarang sehingga hanya menggunakan memori sebanyak yang diperlukan).

Saya perhatikan bahwa grafik yang Anda tentukan di atas hanya memiliki satu sisi yang terarah (B, E). Apakah ini salah ketik atau benar-benar grafik berarah? Solusi ini berhasil. Maaf saya tidak bisa melakukannya di C, saya agak lemah di daerah itu. Saya berharap Anda dapat menerjemahkan kode Java ini tanpa terlalu banyak masalah.

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

Keluaran Program:

B E 
B A C E 
B A C F E 
B F E 
B F C E 
Casey Watson
sumber
5
Harap dicatat bahwa ini bukan traversal luas-pertama. Dengan luas, pertama-tama Anda mengunjungi semua node dengan jarak 0 ke root, lalu node dengan jarak 1, lalu 2, dll.
mweerden
14
Benar, ini adalah DFS. BFS perlu menggunakan antrian, mengantre node level- (N + 1) untuk diproses setelah semua node level-N. Namun, untuk tujuan OP, BFS atau DFS akan berfungsi, karena tidak ada urutan jalur yang dipilih yang ditentukan.
Matt J
1
Casey, saya sudah lama mencari solusi untuk masalah ini. Saya baru-baru ini menerapkan DFS ini di C ++ dan bekerja dengan baik.
AndyUK
6
Kerugian dari rekursi adalah jika Anda memiliki grafik yang dalam (A-> B-> C -> ...-> N) Anda bisa memiliki StackOverflowError di java.
Rrr
1
Saya telah menambahkan versi iteratif di C # di bawah ini.
batta
23

Kamus Algoritme dan Struktur Data National Institute of Standards and Technology (NIST) online mencantumkan masalah ini sebagai " semua jalur sederhana" dan merekomendasikan penelusuran mendalam-pertama . CLRS memasok algoritme yang relevan.

Teknik pintar menggunakan Petri Nets ditemukan di sini

Michael Dorfman
sumber
2
Bisakah Anda membantu saya dengan solusi yang lebih baik? DFS mengambil selamanya untuk menjalankan: stackoverflow.com/q/8342101/632951
Pacerier
Perhatikan bahwa mudah untuk membuat grafik yang DFS-nya sangat tidak efisien, meskipun kumpulan semua jalur sederhana antara dua node kecil dan mudah ditemukan. Sebagai contoh, pertimbangkan grafik yang tidak diarahkan di mana node awal A memiliki dua tetangga: node tujuan B (yang tidak memiliki tetangga selain A), dan node C yang merupakan bagian dari klik yang sepenuhnya terhubung dari n + 1 node. Meskipun jelas hanya ada satu jalur sederhana dari A ke B, DFS yang naif akan membuang-buang waktu O ( n !) Dengan sia-sia menjelajahi klik. Contoh serupa (satu solusi, DFS membutuhkan waktu eksponensial) dapat ditemukan di antara DAG juga.
Ilmari Karonen
NIST mengatakan: "Paths dapat dihitung dengan pencarian mendalam-pertama."
chomp
13

Ini adalah pseudocode yang saya buat. Ini bukan dialek pseudocode tertentu, tetapi harus cukup sederhana untuk diikuti.

Ada yang ingin memisahkan ini.

  • [p] adalah daftar simpul yang mewakili jalur saat ini.

  • [x] adalah daftar jalur yang memenuhi kriteria

  • [s] adalah puncak sumber

  • [d] adalah puncak tujuan

  • [c] adalah simpul saat ini (argumen ke rutin PathFind)

Asumsikan ada cara yang efisien untuk mencari simpul yang berdekatan (baris 6).

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

     4 PathFind (Vertex [c])
     5 Tambahkan [c] ke akhir daftar [p]
     6 Untuk setiap Puncak [v] yang berdekatan dengan [c]
     7 Jika [v] sama dengan [d] maka
     8 Simpan daftar [p] di [x]
     9 Lain Jika [v] tidak ada dalam daftar [p]
    10 PathFind ([v])
    11 Selanjutnya Untuk
    12 Hapus ekor dari [p]
    13 Kembali
Robert Groves
sumber
Bisakah Anda menjelaskan langkah 11 dan langkah 12
pengguna bozo
Baris 11 hanya menunjukkan blok akhir yang mengikuti perulangan For yang dimulai pada baris 6. Baris 12 berarti menghapus elemen terakhir dari daftar jalur sebelum kembali ke pemanggil.
Robert Groves
Apa panggilan awal ke PathFind - apakah Anda meneruskan di simpul sumber?
pengguna bozo
Dalam contoh ini ya, tetapi perlu diingat bahwa Anda mungkin tidak ingin menulis kode nyata yang memetakan satu-ke-satu dengan kodesemu ini. Ini lebih berarti untuk menggambarkan proses pemikiran daripada kode yang dirancang dengan baik.
Robert Groves
8

Karena implementasi DFS non-rekursif yang ada yang diberikan dalam jawaban ini tampaknya rusak, izinkan saya memberikan yang benar-benar berfungsi.

Saya telah menulis ini dengan Python, karena saya merasa cukup mudah dibaca dan tidak berantakan oleh detail implementasi (dan karena memiliki yieldkata kunci yang berguna untuk mengimplementasikan generator ), tetapi seharusnya cukup mudah untuk di-port ke bahasa lain.

# 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

Kode ini mempertahankan dua tumpukan paralel: satu berisi node sebelumnya di jalur saat ini, dan satu lagi berisi indeks tetangga saat ini untuk setiap node dalam tumpukan node (sehingga kita dapat melanjutkan iterasi melalui tetangga node saat kita memunculkannya kembali tumpukan). Saya bisa saja menggunakan satu tumpukan (node, indeks) pasangan dengan sama baiknya, tetapi saya pikir metode dua tumpukan akan lebih mudah dibaca, dan mungkin lebih mudah diimplementasikan untuk pengguna bahasa lain.

Kode ini juga menggunakan visitedset terpisah , yang selalu berisi node saat ini dan node apa pun di stack, agar saya dapat memeriksa secara efisien apakah node sudah menjadi bagian dari jalur saat ini. Jika bahasa Anda kebetulan memiliki struktur data "kumpulan berurutan" yang menyediakan operasi push / pop mirip tumpukan yang efisien dan kueri keanggotaan yang efisien, Anda dapat menggunakannya untuk tumpukan node dan membuang visitedkumpulan terpisah .

Alternatifnya, jika Anda menggunakan kelas / struktur kustom yang bisa berubah untuk node Anda, Anda bisa menyimpan bendera boolean di setiap node untuk menunjukkan apakah itu telah dikunjungi sebagai bagian dari jalur pencarian saat ini. Tentu saja, metode ini tidak akan membiarkan Anda menjalankan dua pencarian pada grafik yang sama secara paralel, jika Anda karena suatu alasan ingin melakukannya.

Berikut beberapa kode uji yang menunjukkan cara kerja fungsi yang diberikan di atas:

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

Menjalankan kode ini pada grafik contoh yang diberikan menghasilkan keluaran sebagai berikut:

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

Perhatikan bahwa, meskipun grafik contoh ini tidak diarahkan (semua tepinya mengarah ke dua arah), algoritme juga berfungsi untuk grafik berarah sembarang. Misalnya, menghapus C -> Btepi (dengan menghapus Bdari daftar tetangga C) menghasilkan keluaran yang sama kecuali untuk jalur ketiga ( A -> C -> B -> D), yang tidak lagi memungkinkan.


Ps. Sangat mudah untuk membuat grafik dimana algoritma pencarian sederhana seperti ini (dan algoritma lainnya yang diberikan dalam utas ini) berkinerja sangat buruk.

Misalnya, pertimbangkan tugas untuk menemukan semua jalur dari A ke B pada grafik yang tidak diarahkan di mana node awal A memiliki dua tetangga: node target B (yang tidak memiliki tetangga selain A) dan node C yang merupakan bagian dari sebuah klik dari n +1 node, seperti ini:

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

Sangat mudah untuk melihat bahwa satu-satunya jalur antara A dan B adalah jalur langsung, tetapi DFS naif yang dimulai dari node A akan membuang waktu O ( n !) Dengan sia-sia untuk menjelajahi jalur dalam klik, meskipun jelas (bagi manusia) bahwa tak satu pun dari jalur itu yang mungkin mengarah ke B.

Seseorang juga dapat membangun DAG dengan properti serupa, misalnya dengan memiliki simpul awal A menghubungkan simpul target B dan ke dua simpul lain C 1 dan C 2 , keduanya terhubung ke simpul D 1 dan D 2 , keduanya terhubung ke E 1 dan E 2 , dan seterusnya. Untuk n lapisan node yang diatur seperti ini, pencarian naif untuk semua jalur dari A ke B akan menghabiskan O (2 n ) untuk memeriksa semua kemungkinan jalan buntu sebelum menyerah.

Tentu saja, menambahkan tepi ke node target B dari salah satu node dalam klik (selain C), atau dari lapisan terakhir DAG, akan membuat sejumlah besar kemungkinan jalur secara eksponensial dari A ke B, dan Algoritma pencarian lokal murni tidak dapat benar-benar memberi tahu sebelumnya apakah ia akan menemukan keunggulan seperti itu atau tidak. Jadi, dalam arti tertentu, sensitivitas keluaran yang buruk dari penelusuran naif tersebut disebabkan oleh kurangnya kesadaran mereka tentang struktur global grafik.

Meskipun ada berbagai metode preprocessing (seperti menghilangkan node daun secara berulang, mencari pemisah simpul simpul tunggal, dll.) Yang dapat digunakan untuk menghindari beberapa "jalan buntu waktu eksponensial" ini, saya tidak tahu ada yang umum trik preprocessing yang bisa menghilangkannya dalam semua kasus. Solusi umum adalah memeriksa di setiap langkah pencarian apakah node target masih dapat dijangkau (menggunakan sub-pencarian), dan mundur lebih awal jika tidak - tapi sayangnya, itu akan sangat memperlambat pencarian (paling buruk , sebanding dengan ukuran grafik) untuk banyak grafik yang tidak mengandung jalan buntu patologis tersebut.

Ilmari Karonen
sumber
1
Itulah yang saya cari, Terima kasih :)
arslan
Terima kasih atas solusi non-rekursif DFS Anda. Perhatikan saja baris terakhir yang mencetak hasilnya memiliki kesalahan sintaks, seharusnya for path in find_simple_paths(graph, "A", "D"): print(" -> ".join(path)), printtanda kurung tidak ada.
David Oliván Ubieto
1
@ DavidOlivánUbieto: Ini adalah kode Python 2, itulah mengapa tidak ada tanda kurung. :)
Ilmari Karonen
5

Ini adalah versi rekursif yang secara logis terlihat lebih baik dibandingkan dengan lantai dua.

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

Keluaran Program

B A C E 

B A C F E 

B E

B F C E

B F E 
Haibin Liu
sumber
4

Solusi dalam kode C. Ini didasarkan pada DFS yang menggunakan memori minimum.

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

}
Leon Chang
sumber
2

Ini mungkin terlambat, tapi berikut adalah versi C # algoritma DFS yang sama di Java dari Casey untuk melintasi semua jalur antara dua node menggunakan tumpukan. Keterbacaan lebih baik dengan rekursif seperti biasa.

    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();
        }
    }
Ini adalah contoh grafik untuk diuji:

    // Contoh grafik. Angka adalah id tepi
    // 1 3       
    // A --- B --- C ----
    // | | 2 |
    // | 4 ----- D |
    // ------------------
batta
sumber
1
excellent - tentang bagaimana Anda mengganti rekursi dengan iterasi berbasis stack.
Siddhartha Ghosh
Saya masih tidak mengerti, apa itu neighbours.Reverse()? Apakah itu List<T>.Reverse ?
Saya memeriksa versi non-rekursif ini, tetapi sepertinya tidak benar. versi rekursif baik-baik saja. mungkin ketika diubah menjadi non-rekursif, kesalahan kecil terjadi
arslan
@alim: Setuju, kode ini rusak begitu saja. (Itu tidak benar menghapus node dari set yang dikunjungi saat mundur, dan penanganan tumpukan tampaknya kacau juga. Saya mencoba untuk melihat apakah itu bisa diperbaiki, tetapi pada dasarnya akan membutuhkan penulisan ulang yang lengkap.) Saya baru saja menambahkan jawaban dengan solusi non-rekursif yang benar dan berfungsi (dengan Python, tetapi seharusnya relatif mudah untuk ditransfer ke bahasa lain).
Ilmari Karonen
@llmari Karonen, Bagus, saya akan memeriksa, Kerja bagus.
arslan
1

Saya telah memecahkan masalah yang mirip dengan ini baru-baru ini, alih-alih semua solusi, saya hanya tertarik pada yang terpendek.

Saya menggunakan pencarian berulang 'luas pertama' yang menggunakan antrian status 'yang masing-masing memegang catatan yang berisi titik saat ini pada grafik dan jalur yang diambil untuk sampai ke sana.

Anda mulai dengan satu catatan dalam antrian, yang memiliki simpul awal dan jalur kosong.

Setiap iterasi melalui kode mengambil item dari kepala daftar, dan memeriksa untuk melihat apakah itu solusinya (node ​​tiba di adalah yang Anda inginkan, jika ya, kita selesai), jika tidak, itu membangun yang baru antrian item dengan node yang terhubung ke node saat ini, dan jalur yang diubah yang didasarkan pada jalur node sebelumnya, dengan lompatan baru terpasang di bagian akhir.

Sekarang, Anda dapat menggunakan sesuatu yang serupa, tetapi ketika Anda menemukan solusi, alih-alih berhenti, tambahkan solusi itu ke 'daftar yang ditemukan' dan lanjutkan.

Anda perlu melacak daftar node yang dikunjungi, sehingga Anda tidak pernah mundur pada diri Anda sendiri, jika tidak, Anda memiliki loop tak terbatas.

jika Anda ingin sedikit lebih pseudocode posting komentar atau sesuatu, dan saya akan menjelaskan.


sumber
6
Saya yakin jika Anda hanya tertarik pada jalur terpendek, maka Algoritma Dijkstra adalah "solusinya" :).
vicatcu
1

Saya pikir Anda harus menjelaskan masalah Anda yang sebenarnya di balik ini. Saya mengatakan ini karena Anda meminta sesuatu yang efisien waktu, namun jawaban yang ditetapkan untuk masalah tersebut tampaknya tumbuh secara eksponensial!

Oleh karena itu saya tidak akan mengharapkan algoritma yang lebih baik daripada sesuatu yang eksponensial.

Saya akan melakukan backtracking dan menelusuri seluruh grafik. Untuk menghindari siklus, simpan semua node yang dikunjungi di sepanjang jalan. Saat Anda kembali, hapus tanda pada node.

Menggunakan rekursi:

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
}

Atau apakah itu salah?

edit: Oh, dan saya lupa: Anda harus menghilangkan panggilan rekursif dengan memanfaatkan tumpukan node itu

Jason Plank
sumber
Masalah sebenarnya saya persis seperti yang saya jelaskan, hanya dengan set yang jauh lebih besar. Saya setuju ini tampaknya tumbuh secara eksponensial dengan ukuran himpunan.
Robert Groves
1

Prinsip dasarnya adalah Anda tidak perlu khawatir tentang grafik. Ini adalah masalah standar yang dikenal sebagai masalah konektivitas dinamis. Ada jenis metode berikut dari mana Anda dapat mencapai node terhubung atau tidak:

  1. Cari Cepat
  2. Quick Union
  3. Algoritma yang Ditingkatkan (Kombinasi keduanya)

Berikut adalah Kode C yang saya coba dengan kompleksitas waktu minimum O (log * n) Itu berarti untuk 65536 daftar edge, membutuhkan 4 pencarian dan untuk 2 ^ 65536, membutuhkan 5 pencarian. Saya membagikan implementasi saya dari algoritme: Kursus Algoritma dari universitas Princeton

TIP: Anda dapat menemukan solusi Java dari tautan yang dibagikan di atas dengan penjelasan yang tepat.

/* 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;
}
Avinash
sumber
Ini sepertinya tidak menyelesaikan masalah seperti yang diminta. OP ingin menemukan semua jalur sederhana antara dua node, tidak hanya untuk memeriksa apakah ada jalur.
Ilmari Karonen
1

find_paths [s, t, d, k]

Pertanyaan ini sudah tua dan sudah terjawab. Namun, tidak ada yang mungkin menunjukkan algoritme yang lebih fleksibel untuk mencapai hal yang sama. Jadi saya akan melempar topi saya ke dalam ring.

Saya pribadi menemukan algoritme dalam bentuk yang find_paths[s, t, d, k]berguna, di mana:

  • s adalah simpul awal
  • t adalah node target
  • d adalah kedalaman pencarian maksimum
  • k adalah jumlah jalur yang akan ditemukan

Menggunakan bentuk infinity untuk ddan kakan memberi Anda semua path§.

§ jelas jika Anda menggunakan grafik terarah dan Anda ingin semua jalur tidak terarah di antaranyas dan tAnda harus menjalankan ini dengan dua cara:

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

Fungsi Pembantu

Saya pribadi suka rekursi, meskipun kadang-kadang bisa sulit, pertama-tama mari kita tentukan fungsi pembantu kita:

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

Fungsi utama

Dengan itu, fungsi intinya sepele:

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

Pertama, mari perhatikan beberapa hal:

  • pseudo-code di atas adalah gabungan bahasa - tetapi paling mirip dengan python (karena saya baru saja membuat kode di dalamnya). Salin-tempel yang ketat tidak akan berfungsi.
  • [] adalah daftar yang tidak diinisialisasi, ganti ini dengan yang setara untuk bahasa pemrograman pilihan Anda
  • paths_found dilewati referensi . Jelas bahwa fungsi rekursi tidak mengembalikan apa pun. Tangani ini dengan benar.
  • di sini graphmengasumsikan beberapa bentuk hashedstruktur. Ada banyak cara untuk mengimplementasikan grafik. Either way, graph[vertex]memberi Anda daftar simpul yang berdekatan di a diarahkan grafik - menyesuaikan sesuai.
  • ini mengasumsikan Anda memiliki pra-proses untuk melepaskan "gesper" (self-loop), siklus dan multi-tepi
SumNeuron
sumber
0

Inilah pemikiran di luar kepala saya:

  1. Temukan satu koneksi. (Pencarian paling dalam mungkin merupakan algoritma yang bagus untuk ini, karena panjang jalur tidak menjadi masalah.)
  2. Nonaktifkan segmen terakhir.
  3. Cobalah untuk mencari koneksi lain dari node terakhir sebelum koneksi yang sebelumnya dinonaktifkan.
  4. Goto 2 sampai tidak ada lagi koneksi.
Ryan Fox
sumber
Ini tidak akan bekerja secara umum: sangat mungkin untuk dua atau lebih jalur antara simpul memiliki tepi terakhir yang sama. Metode Anda hanya akan menemukan salah satu dari jalur tersebut.
Ilmari Karonen
0

Sejauh yang saya tahu, solusi yang diberikan oleh Ryan Fox ( 58343 , Christian ( 58444 ), dan diri Anda sendiri ( 58461 ) adalah yang terbaik. Saya tidak percaya bahwa penjelajahan luas pertama membantu dalam kasus ini, karena Anda akan melakukannya tidak mendapatkan semua jalan. misalnya, dengan tepi (A,B), (A,C), (B,C), (B,D)dan (C,D)Anda akan mendapatkan jalan ABDdan ACD, tapi tidak ABCD.

mweerden
sumber
mweerden, Traversal luas pertama yang saya kirimkan akan menemukan SEMUA jalur sambil menghindari siklus apa pun. Untuk grafik yang telah Anda tentukan, penerapannya menemukan ketiga jalur dengan benar.
Casey Watson
Saya tidak sepenuhnya membaca kode Anda dan berasumsi bahwa Anda menggunakan traversal luas pertama (karena Anda mengatakannya). Namun, pada pemeriksaan lebih dekat setelah komentar Anda, saya perhatikan bahwa sebenarnya tidak. Ini sebenarnya adalah traversal kedalaman pertama tanpa memori seperti yang dilakukan Ryan, Christian, dan Robert.
mweerden
0

Saya menemukan cara untuk menghitung semua jalur termasuk yang tak terbatas yang berisi loop.

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

Menemukan Jalur & Siklus Atom

Definition

Apa yang ingin kami lakukan adalah menemukan semua jalur yang memungkinkan dari titik A ke titik B. Karena ada siklus yang terlibat, Anda tidak bisa hanya melalui dan menghitung semuanya. Sebaliknya, Anda harus menemukan jalur atom yang tidak berulang dan siklus terkecil yang mungkin (Anda tidak ingin siklus Anda berulang).

Definisi pertama yang saya ambil dari jalur atom adalah jalur yang tidak melalui simpul yang sama dua kali. Namun, saya menemukan bahwa tidak mengambil semua kemungkinan. Setelah beberapa refleksi, saya menemukan bahwa node tidak penting, bagaimanapun tepinya! Jadi jalur atom adalah jalur yang tidak melewati sisi yang sama dua kali.

Definisi ini berguna, ini juga berfungsi untuk siklus: siklus atom titik A adalah jalur atom yang bergerak dari titik A dan berakhir ke titik A.

Penerapan

Atomic Paths A -> B

Untuk mendapatkan semua jalur mulai dari titik A, kita akan melintasi grafik secara rekursif dari titik A. Saat melalui anak, kita akan membuat tautan anak -> induk untuk mengetahui semua sisi yang kita miliki. sudah menyeberang. Sebelum kita pergi ke anak itu, kita harus melintasi daftar tertaut itu dan memastikan tepi yang ditentukan belum dilalui.

Saat kita sampai di titik tujuan, kita bisa menyimpan jalur yang kita temukan.

Freeing the list

Terjadi masalah saat Anda ingin membebaskan daftar tertaut. Ini pada dasarnya adalah pohon yang dirantai dalam urutan terbalik. Solusinya adalah dengan menautkan ganda daftar itu dan ketika semua jalur atom telah ditemukan, bebaskan pohon dari titik awal.

Tetapi solusi cerdas adalah dengan menggunakan referensi penghitungan (terinspirasi dari Pengumpulan Sampah). Setiap kali Anda menambahkan tautan ke induk, Anda menambahkan satu ke hitungan referensinya. Kemudian, ketika Anda tiba di ujung jalan, Anda mundur dan bebas sementara jumlah referensi sama dengan 1. Jika lebih tinggi, Anda cukup menghapus satu dan berhenti.

Atomic Cycle A

Mencari siklus atom A sama dengan mencari jalur atom dari A ke A. Namun ada beberapa optimasi yang bisa kita lakukan. Pertama, ketika kita tiba di titik tujuan, kita ingin menyimpan jalur hanya jika jumlah biaya sisi negatif: kita hanya ingin melalui siklus penyerapan.

Seperti yang Anda lihat sebelumnya, seluruh grafik sedang dilintasi saat mencari jalur atom. Sebagai gantinya, kita dapat membatasi area pencarian ke komponen yang sangat terhubung yang mengandung A. Menemukan komponen-komponen ini memerlukan lintasan grafik yang sederhana dengan algoritma Tarjan.

Menggabungkan Jalur dan Siklus Atom

Pada titik ini, kita memiliki semua jalur atom yang bergerak dari A ke B dan semua siklus atom dari setiap node, diserahkan kepada kita untuk mengatur semuanya untuk mendapatkan jalur terpendek. Mulai sekarang kita akan mempelajari bagaimana menemukan kombinasi terbaik dari siklus atom di jalur atom.

Vjeux
sumber
Ini sepertinya tidak menjawab pertanyaan seperti yang ditanyakan.
Ilmari Karonen
0

Seperti yang dijelaskan dengan cakap oleh beberapa poster lain, masalah singkatnya adalah penggunaan algoritma pencarian kedalaman pertama untuk secara rekursif mencari grafik untuk semua kombinasi jalur antara node akhir yang berkomunikasi.

Algoritme itu sendiri dimulai dengan simpul awal yang Anda berikan, memeriksa semua tautan keluarnya dan berkembang dengan memperluas simpul anak pertama dari pohon pencarian yang muncul, mencari secara progresif lebih dalam dan lebih dalam sampai simpul target ditemukan, atau sampai ia menemukan sebuah simpul yang tidak memiliki anak.

Pencarian kemudian menelusuri kembali, kembali ke simpul terbaru yang belum selesai dijelajahi.

Saya membuat blog tentang topik ini baru-baru ini, memposting contoh implementasi C ++ dalam prosesnya.

AndyUK
sumber
0

Menambah jawaban Casey Watson, berikut adalah implementasi Java lainnya. Memulai node yang dikunjungi dengan node awal.

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