看来这可以通过图的深度优先搜索来完成.深度优先搜索会找到两个节点之间的所有非循环路径.这个算法应该非常快并且可以扩展到大图(图数据结构是稀疏的，所以它只使用与它一样多的内存需要).

我注意到您在上面指定的图形只有一条有方向的边 (B,E).这是打字错误还是真的是有向图?不管怎样，这个解决方案都有效.抱歉，我无法在 C 语言中做到这一点，我在这方面有点弱.不过，我希望您能够轻松翻译此 Java 代码.

Graph.java:

import java.util.HashMap;导入 java.util.LinkedHashSet;导入 java.util.LinkedList;导入 java.util.Map;导入 java.util.Set;公共类图{私有映射>map = new HashMap();public void addEdge(String node1, String node2) {LinkedHashSet相邻 = map.get(node1);如果(相邻==空){相邻 = 新 LinkedHashSet();map.put(node1, 相邻);}相邻.添加(节点2)；}public void addTwoWayVertex(String node1, String node2) {添加边缘(节点 1，节点 2)；添加边缘(节点 2，节点 1)；}public boolean isConnected(String node1, String node2) {设置相邻 = map.get(node1);如果(相邻==空){返回假；}返回相邻.包含(节点2)；}公共链表相邻节点(字符串最后){LinkedHashSet相邻 = map.get(last);如果(相邻==空){返回新的链表()；}返回新的 LinkedList(相邻)；}}

Search.java:

import java.util.LinkedList;公共类搜索{私有静态最终字符串 START = "B";私有静态最终字符串END =E"；公共静态无效主(字符串 [] args){//这个图是有方向的图图 = new Graph();graph.addEdge("A", "B");graph.addEdge("A", "C");graph.addEdge("B", "A");graph.addEdge("B", "D");graph.addEdge("B", "E");//这是唯一的单向连接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访问 = 新的 LinkedList();访问.添加(开始)；new Search().depthFirst(graph,visited);}private void depthFirst(Graph graph, LinkedListvisited) {LinkedList节点 = graph.adjacentNodes(visited.getLast());//检查相邻节点对于(字符串节点:节点){如果(访问.包含(节点)){继续;}如果(节点.等于(结束)){访问.添加(节点)；打印路径(已访问)；已访问.removeLast();休息;}}对于(字符串节点:节点){if (visited.contains(node) || node.equals(END)) {继续;}访问.addLast(节点)；深度优先(图形，访问)；已访问.removeLast();}}private void printPath(LinkedListvisited) {对于(字符串节点:访问过){System.out.print(节点)；System.out.print(" ");}System.out.println();}}

程序输出:

B E学分B A C F E乙醚B F C E

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

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.

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

For example:

    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]

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

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:

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

Program Output:

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