language agnostic - Graph Algorithm To Find All Connections Between Two Arbitrary Vertices -

i trying determine best time efficient algorithm accomplish task described below.

i have set of records. set of records have connection data indicates how pairs of records set connect 1 another. represents undirected graph, records being vertices , connection data edges.

all of records in set have connection information (i.e. no orphan records present; each record in set connects 1 or more other records in set).

i want choose 2 records set , able show simple paths between chosen records. "simple paths" mean paths not have repeated records in path (i.e. finite paths only).

note: 2 chosen records different (i.e. start , end vertex never same; no cycles).

for example:

     if have following records:         a, b, c, d, e      , following represents 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 connects record b] 

if chose b starting record , e ending record, want find simple paths through record connections connect record b record e.

    paths connecting b e:       b->e       b->f->e       b->f->c->e       b->a->c->e       b->a->c->f->e 

this example, in practice may have sets containing hundreds of thousands of records.

it appears can accomplished depth-first search of graph. the depth-first search find non-cyclical paths between 2 nodes. algorithm should fast , scale large graphs (the graph data structure sparse uses memory needs to).

i noticed graph specified above has 1 edge directional (b,e). typo or directed graph? solution works regardless. sorry unable in c, i'm bit weak in area. expect able translate java code without 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) {         // graph 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"); // 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         (string node : nodes) {             if (visited.contains(node)) {                 continue;             }             if (node.equals(end)) {                 visited.add(node);                 printpath(visited);                 visited.removelast();                 break;             }         }         (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) {         (string node : visited) {             system.out.print(node);             system.out.print(" ");         }         system.out.println();     } } 

program output:

b e  b c e  b c f e  b f e  b f c e