Are two vertices connected in a graphProblem: How to tell if a path exists between two vertices on a graph? Answer: Choose one vertex V as your start; let V' be the end point. Let R_n and D_n denote sets of of vertices. Set R_0 = nil, D_0 = {V}, n = 0, found = false; while D_n .ne. nil begin begin if V' in D_n found = true escape end if R_n+1 = R_n + D_n D_n+1 = neighbours(D_n) - R_n+1 endIn terms of color, the graph starts out gray, and the original set is blue. In each cycle the gray neighbours of the blue vertices turn green, the blue vertices turn red, and then the green vertices turn blue. This page was last updated July 1, 2004. |