为了账号安全,请及时绑定邮箱和手机立即绑定

求任意两个顶点之间所有联系的图算法

/ 猿问

求任意两个顶点之间所有联系的图算法

慕桂英3389331 2019-07-25 14:14:02

求任意两个顶点之间所有联系的图算法

我试图确定完成以下任务的最佳时间效率算法。

我有一套记录。对于这组记录,我有连接数据,它指示来自这个集合的记录对如何彼此连接。这基本上代表了一个无向图,记录是顶点,连接数据是边。

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

我希望从集合中选择任意两个记录,并且能够显示所选记录之间的所有简单路径。所谓“简单路径”是指路径中没有重复记录的路径(即仅有限路径)。

注意:两个选择的记录总是不同的(即起始点和结束顶点永远不会相同;没有循环)。

例如:

    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以记录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

这是一个例子,在实践中,我可能有包含数十万条记录的集合。


查看完整描述

3 回答

?
哆啦的时光机

这似乎可以通过图的深度优先搜索来完成。深度优先搜索将发现两个节点之间的所有非周期路径。这个算法应该非常快,并且可以缩放到大图(图的数据结构是稀疏的,所以它只需要使用足够多的内存)。

我注意到,上面指定的图只有一个边,即方向边(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);
    }}

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



查看完整回答
反对 回复 2019-07-26
?
守着星空守着你


美国国家标准和技术研究所(NIST)的“算法和数据结构在线词典”将这一问题列为“所有简单路径“并建议深度优先搜索..CLRS给出了相应的算法。

发现了一种利用Petri网的巧妙方法。这里


查看完整回答
反对 回复 2019-07-26
?
一只萌萌小番薯

这是我想出的伪码。这不是任何特定的伪代码方言,但应该足够简单,以便跟随。

任何人都想把它拆开。

  • [P]是表示当前路径的顶点列表。

  • [X]是满足条件的路径列表

  • [s]是源顶点。

  • [d]是目标顶点。

  • [C]是当前顶点(路径查找例程的参数)。

假设有一种查找相邻顶点的有效方法(第6行)。

     1 PathList [p]
     2 ListOfPathLists [x]
     3 Vertex [s], [d]

     4 PathFind ( Vertex [c] )
     5     Add [c] to tail end of list [p]
     6     For each Vertex [v] adjacent to [c]
     7         If [v] is equal to [d] then
     8             Save list [p] in [x]
     9         Else If [v] is not in list [p]
    10             PathFind([v])
    11     Next For
    12     Remove tail from [p]
    13 Return


查看完整回答
反对 回复 2019-07-26
  • 3 回答
  • 0 关注
  • 88 浏览
我要回答

添加回答

回复

举报

0/150
提交
取消
意见反馈 帮助中心 APP下载
官方微信