Bu görev aşağıda belirtilen gerçekleştirmek için belirlemek için çalışıyorum.

Kayıtları bir dizi var. Kayıtlar bu dizi için bu kümesinden kayıtları çiftleri birbirine nasıl bağlandığını gösteren bağlantı veri var. Bu temelde yönlendirilmemiş bir grafik, kayıtlar, köşeler ve Bağlantı kenarları verileri temsil eder.

Kümesindeki tüm kayıtları bağlantı bilgilerini (örneğin, yetim kayıtları mevcut, set her kayıt kümesi, bir veya daha fazla diğer kayıtları bağlanır).

Kümesinden herhangi iki kayıtları seçmek istiyorum ve seçilen kayıtları arasında basit yolları göstermek. "Basit yolları" yol (yani sonlu yolları) tekrarlanan kaydı olmayan yollar yani.

Not: iki seçilmiş kayıtları her zaman farklı (yani başlangıç ve bitiş köşe asla eskisi gibi olmayacak; hiçbir devir) edilecektir.

Örneğin:

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

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

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

Eğer E rekorumu son olarak benim başlangıç kaydı olarak ve B seçtim, kayıt e kayıt B bağlayacak kayıt bağlantıları üzerinden tüm basit yollar bulmak isterim

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

Bu bir örnek, uygulamada ayarlar yüz binlerce kayıt içeren olabilirim.

Robert,

Bu grafiğin derinlik öncelikli arama ile yapılabilir gibi görünüyor.Derinlik ilk arama iki düğüm arasında olmayan döngüsel tüm yollar bulacaktır.Bu algoritma çok hızlı ve büyük grafikler (grafik veri yapısı sadece ihtiyacı kadar bellek kullanır çok seyrek) için ölçekli olmalıdır.

Grafiği yukarıda belirtilen yönlü tek kenar (B,E) sahip olduğunu fark ettim. Bu bir yazım hatası ya da yönlendirilmiş bir grafik mi? Bu çözüm ne olursa olsun çalışır. Üzgünüm C bunu yapmak mümkün, biraz o bölgede hala zayıfım. Çok fazla sorun olmadan bu Java kod olsa çevirmek mümkün olacağını umuyorum.

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().breadthFirst(graph, visited);
    }

    private void breadthFirst(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;
            }
        }
        // in breadth-first, recursion needs to come after visiting adjacent nodes
        for (String node : nodes) {
            if (visited.contains(node) || node.equals(END)) {
                continue;
            }
            visited.addLast(node);
            breadthFirst(graph, visited);
            visited.removeLast();
        }
    }

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

Program Çıktı

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