# 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?

• 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. – Mohammad 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
{"found_math": true, "script_math_tex": 0, "script_math_asciimath": 0, "math_annotations": 0, "math_alttext": 0, "mathml": 0, "mathjax_tag": 0, "mathjax_inline_tex": 1, "mathjax_display_tex": 0, "mathjax_asciimath": 0, "img_math": 0, "codecogs_latex": 0, "wp_latex": 0, "mimetex.cgi": 0, "/images/math/codecogs": 0, "mathtex.cgi": 0, "katex": 0, "math-container": 0, "wp-katex-eq": 0, "align": 0, "equation": 0, "x-ck12": 0, "texerror": 0, "url": "https://cs.stackexchange.com/questions/2274/enumerating-all-the-walks-in-a-graph-between-a-start-vertex-and-a-terminal-verte", "fetch_time": 1627703375000000000, "content_mime_type": "text/html", "warc_filename": "crawl-data/CC-MAIN-2021-31/segments/1627046154042.23/warc/CC-MAIN-20210731011529-20210731041529-00343.warc.gz", "warc_record_offset": 198779446, "warc_record_length": 38554, "token_count": 867, "char_count": 3305, "score": 3.984375, "int_score": 4, "crawl": "CC-MAIN-2021-31", "snapshot_type": "latest", "language": "en", "language_score": 0.9123435616493225, "file_path": "/sailhome/yjruan/project/latent-lm/data/processed/finemath-4plus/finemath-4plus/train-00012-of-00064.parquet"}