[prev] 52 [next]

Finding a Path (cont)

Overall strategy for path-finding (function isPath(V,W)):

// is there a path from V to W?
ToVisit = {V}   // vertices to be checked
Visited = {}    // previously checked vertices
while (still some vertices in ToVisit) {
    X = remove a vertex from ToVisit
    Visited += X
    foreach (Y in neighbours(X)) {
        if (Y == W) return TRUE
        if (Y not in Visited) ToVisit += Y
    }
}
return FALSE

  • BFS = ToVisit implemented via a queue of vertices
  • DFS = ToVisit implemented via a stack of vertices