Graph-Reachability Problem

computation

Definition

Graph-Reachability Problem

Given a graph $G=(V,E)$ and vertices $u,v\in V$. The graph reachability problem asks whether there exists a path from $u$ to $v$ in $G$.

The graph reachability problem is a decision problem.

Pseudo-code

from itertools import product
 
def reachable(
	V: set[Vertex],
	E: set[tuple[Vertex, Vertex]],
	u: Vertex,
	v: Vertex,
) -> bool:
	S: list[Vertex] = [u]
	while True:
		s = S;
		for i, j in product(S, V):
			if (i, j) in E:
				S.append(j)
		if s == S:
			break;
	if v in S:
		return true
	else
		return false