Skip to main content
4 of 4
MathJax: \langle, \rangle
Martin Sleziak
  • 4.7k
  • 4
  • 35
  • 40

Algorithm to check if vertex belong to infinite path in Graph theory

My purpose is to understand if in a graph $G = \langle V, E\rangle$ given 4 vertices in input (a, b ,c and d) they belong to an infinite path. With infinite path I mean a vertex succession that has a known head without ending.

In other words what I'm trying to do is to find and algorithm that could identify this kind of sequence:

$$ p = a , x_1 , x_2 , x_3, ... , c , ... , d , ... , b , x_i , ... $$

Before ask a question I've thought about using BFS because I have a sort of sequence to find, but I'm stuck at infinite path. I don't know how detect it.

Philip
  • 133
  • 5