# Enumerating all the walks in a graph between a start vertex and a terminal vertex?

I was reading something about the concept of walks in a graph b/w a start vertex and a terminating vertex in a graph and then suddenly a problem struck me, is there any algorithm or a method that can be used to enumerate all the distinct walks from a start vertex to a terminal vertex in a graph, if so can you all point me to some relevant links to study this problem and what are some applications of solving this problem?

## migrated from cstheory.stackexchange.comJun 8 '12 at 6:29

This question came from our site for theoretical computer scientists and researchers in related fields.

• Depth-first search from the start vertex to the terminal vertex. When you find the terminal vertex don't stop, keep going, until the algorithm terminates. – M. Alaggan Jun 5 '12 at 13:46
• Nowadays, the definition of walk allows cycles in it. So if the graph is connected but not a tree, there must be INFINITE walks, and it's impossible to enumerate. – Yixin Cao Jun 5 '12 at 14:42
• Actually, even the graph is a tree, you can go along an edge back and forth for any times, and thus the number of walks is still infinite. On the other hand, take $A$ as the adjacency matrix of the graph, the $(i,j)$-element in the $k$-th power of $A$ ($A^k_{i,j}$) is the number of length-$k$ walks from the vertex $i$ to the vertex $j$. – Yixin Cao Jun 5 '12 at 14:55

## If the input graph is undirected:

• If the source vertex $s$ and target vertex $t$ are in different components of the graph, then there are no walks from $s$ to $t$.

• If $s$ and $t$ are in the same component, and that component has only one vertex (so in particular, $s=t$), then there is exactly one walk from $s$ to $t$, namely the unique walk that starts at $s$ and has length $0$.

• Otherwise, there are infinitely many walks from $s$ to $t$.

## If the input graph is directed:

Let $S$ be the subset of vertices reachable from $s$, and let $T$ be the set of vertices from which $t$ is reachable. Finally, let $H$ be the induced subgraph of the input graph $G$ with vertices $S\cap T$. Every walk in $G$ from $s$ to $t$ is actually a walk in the subgraph $H$.

• If $H$ is empty, there are no walks from $s$ to $t$.

• If $H$ is a non-empty directed acyclic graph, then $s$ is the unique source, $t$ is the unique sink, and every walk from $s$ to $t$ is actually a simple path. The number of paths in a dag from a source to a sink can be computed in $O(m)$ time by dynamic programming. Remaining details are left as a homework exercise.

• Otherwise, there are infinitely many walk from $s$ to $t$.

• So the question is only interesting for directed graphs. What then? – Raphael Jun 8 '12 at 12:30
• @JeffE: your comment applies since you are considering cycles. A natural constraint that can be added to the problem so that it becomes more interesting (I am referring to Raphael's comment here) is to forbid re-visiting nodes or to forbid traversing the same edge twice. – Carlos Linares López Nov 26 '12 at 22:32
• @CarlosLinaresLópez: That should be a separate question! Counting paths or trails instead of walks is much more interesting/difficult. – JeffE Nov 26 '12 at 23:19
• @JeffE: Agreed! All I wanted was just to remark that the problem might be interesting if additional constraints are imposed. Nevertheless, you are right and that should be a separate question – Carlos Linares López Nov 27 '12 at 10:07