图法之间找到任意两个顶点所有连接 [英] Graph Algorithm To Find All Connections Between Two Arbitrary Vertices

问题描述

我想，以确定最佳的时间有效的算法来完成下面描述的任务。

I am trying to determine the best time efficient algorithm to accomplish the task described below.

我有一组记录。对于此组记录我这表明如何对从该记录集连接到另一个连接数据。这基本上重新presents无向图，与记录作为顶点和连接数据的边缘。

I have a set of records. For this set of records I have connection data which indicates how pairs of records from this set connect to one another. This basically represents an undirected graph, with the records being the vertices and the connection data the edges.

所有的在该组中的记录有连接信息（即没有孤立记录是present;在该组的每个记录连接到一个或多个其它的记录中设定的）

All of the records in the set have connection information (i.e. no orphan records are present; each record in the set connects to one or more other records in the set).

我要选择的任何两个记录从集合，并能够显示所选择的记录之间的所有简单路径。通过简单路径我的意思是不具有路径（即只有有限的路径）。

I want to choose any two records from the set and be able to show all simple paths between the chosen records. By "simple paths" I mean the paths which do not have repeated records in the path (i.e. finite paths only).

请注意：这两个选择的记录将永远是不同的（即开始和结束的顶点将永远是相同的，没有周期）

Note: The two chosen records will always be different (i.e. start and end vertex will never be the same; no cycles).

例如：

    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]

如果我选择b以我的起始记录和E作为我的结束纪录，我希望找到通过记录连接，将连接记录B，记录Ë所有简单路径。

If I chose B as my starting record and E as my ending record, I would want to find all simple paths through the record connections that would connect record B to record E.

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

这是一个例子，在实践中我可以具有包含数十万的记录集。

This is an example, in practice I may have sets containing hundreds of thousands of records.

推荐答案

罗伯特，

有看来，这可以完成与深度优先搜索图表。 的深度优先搜索会发现两个节点之间的所有非周期的路径。这个算法应该是非常快，规模大图（图表的数据结构是稀疏的，因此只使用尽可能多的内存，因为它需要）。

It appears that this can be accomplished with a depth-first search of the graph. The depth-first search will find all non-cyclical paths between two nodes. This algorithm should be very fast and scale to large graphs (The graph data structure is sparse so it only uses as much memory as it needs to).

我注意到，您在上面指定的图形只有一个优势是定向（B，E）。这是否是一个错字或者是不是真的有向图？该解决方案的工作，无论。对不起，我无法做到这一点在C，我有点薄弱的区域。我希望你将能够翻译，虽然这个Java code没有太多的麻烦。

I noticed that the graph you specified above has only one edge that is directional (B,E). Was this a typo or is it really a directed graph? This solution works regardless. Sorry I was unable to do it in C, I'm a bit weak in that area. I expect that you will be able to translate this Java code without too much trouble though.

Graph.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

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

程序输出

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

这篇关于图法之间找到任意两个顶点所有连接的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！