CODEWITHSUNDEEP
graphpathdepth-first-searchbreadth-first-search
Alexandros
Alexandros

Reputation: 2200

Enumerate all paths from a single source in a graph

I was wondering if you are aware of an algorithm to enumerate all possible simple paths in a graph from a single source, without repeating any of the vertices. keep in mind that the graph will be very small (16 nodes) and relatively sparse (2-5 edges per node).

To make my question clear:

Vertices: A,B,C

A connects to B, C
B connects to A, C
C connects to A, B

Paths (from A):

A,B
A,C
A,B,C
A,C,B

Vertices: A,B,C,D

A connects to B, C
B connects to A, C, D
C connects to A, B, D

Paths (from A):

A,B
A,C
A,B,C
A,B,D
A,C,B
A,C,D
A,B,C,D
A,C,B,D

It is surely not BFS or DFS, although one of their possible variants might work. Most of the similar problems I saw in SO, were dealing with pair of nodes graphs, so my problem is slightly different.

Also this Find all possible paths from one vertex in a directed cyclic graph in Erlang is related, but the answers are too Erlang related or it is not clear what exactly needs to be done. As I see, the algorithm could be alternatively be decribed as find all possible simple paths for a destined number of hops from a single source. Then for number of hops (1 to N) we could find all solutions.

I work with Java but even a pseudocode is more than enough help for me.

Upvotes: 1

Views: 1427

Answers (1)

Rodolfo
Rodolfo

Reputation: 156

In Python style, it is a BFS with a different tracking for visited:

MultiplePath(path, from):
  from.visited = True
  path.append(from)
  print(path)

  for vertex in neighbors(from):
    if (not vertex.visited):
      MultiplePath(path, vertex)

  from.visited = False
Return

Upvotes: 3

Related Questions