Graph Search

New Notation

• Unvisited
• Assignment Operations

Forward Search

Overview

• “start” node in v
• “goal” node in v
  • sometimes we have multiple goals
  • in this class, we will assume we only care about getting to any of the goals
• each node has:
  • a list of its neighbors
    • v.Neighbors $\leftarrow \cup \left\{u|\left(v,u\right)\in E\right\}$
    • in practice, stored as and array or a list (inside the node’s data structre)
  • function to get the next neighbor
    • iterates on v.Neighbors
    • each time it is called, returns a new neighbor of v
    • after returning each neighbor once, all subsequent calls return 0 (or null, depending on language convention)

Two Fundamental Algorithms

• Simplest possible implementations of forward-search
  • Breadth-First Search (BFS)
  • Depth-First Search (DFS)
• BFS and DFS are algorithmically identical, except:
  • BFS:
    • uses a queue
    • search tree goes as wide as possible before going deeper
  • DFS:
    • uses a stack
    • search tree goes as deep as possible before going wider

Pseudocode

function searchAlgorithm(G, start, goal, Q) {
    UNVISITED <- V[start]
    Q.insert(start)
 
    while Q.top() != 0 {
        v <- Q.pop()
 
        while v.nextNeighbor() != 0 {
            u <- v.nextNeighbor()
 
            if u ∈ UNVISITED {
                UNVISITED <- UNVISITED[u]
                u.parent <- v
                Q.insert(u)
            }
        }
 
        if v = goal {
            return SUCCESS
        }
    }
 
    return FAILURE
}