图算法查找两个任意顶点之间的所有连接

一尘不染

图算法查找两个任意顶点之间的所有连接

algorithm

我正在尝试确定最佳的时间效率算法来完成下面描述的任务。

我有一套记录。对于这组记录，我具有连接数据，该数据指示该组记录中的记录对如何相互连接。这基本上表示一个无向图，其中记录是顶点，而连接数据是边。

集合中的所有记录都具有连接信息（即不存在孤立记录；集合中的每个记录都连接到集合中的一个或多个其他记录）。

我想从集合中选择任意两个记录，并能够显示所选记录之间的所有简单路径。“简单路径”是指在路径中没有重复记录的路径（即仅有限路径）。

注意：所选的两个记录将始终是不同的（即开始和结束顶点永远不会相同；没有周期）。

例如：

    如果我有以下记录：
        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

这是一个例子，实际上我可能有包含数十万条记录的集合。

阅读 1057

2020-07-28

共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

2020-07-28