home
table of contents
Comp. Sci.
July 2004
email

Are two vertices connected in a graph

Problem: 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
	end
In 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.

home
table of contents
Comp. Sci.
July 2004
email