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

很容易看出A和B之间的唯一路径是直接路径,但是从节点A开始的天真DFS将浪费O(n!)时间无用地探索集团内的路径,即使它(对于人类)显而易见这些路径都不可能导致B.

还可以构建具有类似属性的DAG,例如通过使起始节点A连接目标节点B和两个其他节点C ₁和C ₂,两个节点连接到节点D ₁和D ₂,两者都连接到E ₁和E ₂,依此类推.对于这样排列的n层节点,从A到B的所有路径的天真搜索将最终浪费O(2 ⁿ)时间来检查所有可能的死角,然后放弃.

当然,从clique中的一个节点(除C之外)或DAG的最后一层向目标节点B添加边缘将创建从A到B的指数级大量可能路径,并且纯粹的局部搜索算法无法预先确定是否会找到这样的边缘.因此,从某种意义上说,这种天真搜索的输出敏感性差是由于他们缺乏对图的全局结构的认识.

虽然有各种预处理方法(例如迭代消除叶节点,搜索单节点顶点分隔符等),可以用来避免这些"指数时间死角",我不知道任何一般在所有情况下都可以消除它们的预处理技巧.一般的解决方案是在搜索的每个步骤检查目标节点是否仍然可以访问(使用子搜索),如果不是,则提前回溯 -​​ 但是,这会显着减慢搜索速度(最糟糕的是) ,对于许多不包含这种病态死胡同的图,与图的大小成比例).

与第二层相比，这是一个逻辑上更好看的递归版本。

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> paths = new ArrayList>();
    String currentNode = START;
    List visited = new ArrayList();
    visited.add(START);
    new Search().findAllPaths(graph, seen, paths, currentNode);
    for(ArrayList path : paths){
        for (String node : path) {
            System.out.print(node);
            System.out.print(" ");
        }
        System.out.println();
    }   
}

private void findAllPaths(Graph graph, List visited, List> paths, String currentNode) {        
    if (currentNode.equals(END)) { 
        paths.add(new ArrayList(Arrays.asList(visited.toArray())));
        return;
    }
    else {
        LinkedList nodes = graph.adjacentNodes(currentNode);    
        for (String node : nodes) {
            if (visited.contains(node)) {
                continue;
            } 
            List temp = new ArrayList();
            temp.addAll(visited);
            temp.add(node);          
            findAllPaths(graph, temp, paths, node);
        }
    }
}
}

节目输出

B A C E 

B A C F E 

B E

B F C E

B F E