[解決済み] 任意の2頂点間の全接続を求めるグラフアルゴリズム

質問

私は以下のタスクを達成するために、最も時間効率の良いアルゴリズムを決定しようとしている。

私はレコードのセットを持っています。このレコードのセットに対して、このセットからのレコードのペアがどのように互いに接続するかを示す接続データを持っています。これは基本的に無向グラフを表しており、レコードを頂点、接続データを辺とする。

セット内のすべてのレコードが接続情報を持っています (つまり、孤立したレコードは存在しません。セット内の各レコードはセット内の 1 つ以上の他のレコードに接続します)。

セットから任意の 2 つのレコードを選択し、選択したレコード間のすべての単純なパスを表示できるようにしたいと思います。単純なパスとは、パスの中に繰り返されるレコードがないパス（つまり、有限のパスのみ）を意味します。

注：選択された2つのレコードは常に異なるものとする（すなわち、始点と終点が同じになることはない；サイクルはない）。

例えば

    以下のようなレコードがあった場合
        A, B, C, D, E

    というレコードがあり、以下はその接続を表しています。
        (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)

        [ここで、(A,B)はレコードAがレコードBに接続することを意味する] 。

Bを開始レコード、Eを終了レコードとして選んだ場合、レコードBをレコードEに接続するレコード接続を通るすべての単純なパスを見つけたいと思うでしょう。

   BからEにつながるすべてのパス
      B->E
      B->F->E
      B->F->C->E
      B->A->C->E
      B->A->C->F->E

これは例で、実際には何十万件ものレコードを含むセットがあるかもしれません。

どのように解決するのですか？

グラフの深さ優先探索で実現できるようです。 深さ優先探索では、2つのノード間の非循環パスをすべて見つけることができます。 このアルゴリズムは非常に高速で、大きなグラフにもスケールするはずです（グラフのデータ構造は疎なので、必要な分だけメモリを使用します）。

私は、あなたが上で指定したグラフは、方向性を持つ1つのエッジ（B,E）だけを持っていることに気づきました。これはタイプミスなのでしょうか、それとも本当に有向グラフなのでしょうか。この解決策は関係なく動作します。C言語でできなくてすみません、ちょっと苦手です。しかし、このJavaコードを翻訳するのは、それほど問題なくできると思います。

Graph.javaです。

import java.util.HashMap;
import java.util.LinkedHashSet;
import java.util.LinkedList;
import java.util.Map;
import java.util.Set;

public class Graph {
    private Map<String, LinkedHashSet<String>> map = new HashMap();

    public void addEdge(String node1, String node2) {
        LinkedHashSet<String> adjacent = map.get(node1);
        if(adjacent==null) {
            adjacent = new LinkedHashSet();
            map.put(node1, adjacent);
        }
        adjacent.add(node2);
    }

    public void addTwoWayVertex(String node1, String node2) {
        addEdge(node1, node2);
        addEdge(node2, node1);
    }

    public boolean isConnected(String node1, String node2) {
        Set adjacent = map.get(node1);
        if(adjacent==null) {
            return false;
        }
        return adjacent.contains(node2);
    }

    public LinkedList<String> adjacentNodes(String last) {
        LinkedHashSet<String> adjacent = map.get(last);
        if(adjacent==null) {
            return new LinkedList();
        }
        return new LinkedList<String>(adjacent);
    }
}

Search.java:

import java.util.LinkedList;

public class Search {

    private static final String START = "B";
    private static final String END = "E";

    public static void main(String[] args) {
        // this graph is directional
        Graph graph = new Graph();
        graph.addEdge("A", "B");
        graph.addEdge("A", "C");
        graph.addEdge("B", "A");
        graph.addEdge("B", "D");
        graph.addEdge("B", "E"); // this is the only one-way connection
        graph.addEdge("B", "F");
        graph.addEdge("C", "A");
        graph.addEdge("C", "E");
        graph.addEdge("C", "F");
        graph.addEdge("D", "B");
        graph.addEdge("E", "C");
        graph.addEdge("E", "F");
        graph.addEdge("F", "B");
        graph.addEdge("F", "C");
        graph.addEdge("F", "E");
        LinkedList<String> visited = new LinkedList();
        visited.add(START);
        new Search().depthFirst(graph, visited);
    }

    private void depthFirst(Graph graph, LinkedList<String> visited) {
        LinkedList<String> nodes = graph.adjacentNodes(visited.getLast());
        // examine adjacent nodes
        for (String node : nodes) {
            if (visited.contains(node)) {
                continue;
            }
            if (node.equals(END)) {
                visited.add(node);
                printPath(visited);
                visited.removeLast();
                break;
            }
        }
        for (String node : nodes) {
            if (visited.contains(node) || node.equals(END)) {
                continue;
            }
            visited.addLast(node);
            depthFirst(graph, visited);
            visited.removeLast();
        }
    }

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

プログラムの出力。

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