CS2040s: Searching On Graphs

Searching.. Graph Edition

Goals:

Starting at some vertex s and find some other vertex f (finish)

Visit all nodes in the graph

Techniques

Breadth first Search (BFS)

Explore level by level.

Always moving forward in the frontier (wave)

Initial = {s}

Do not go backwards 

=> Find the shortest path

Uses a Queue

We keep looking at the neighbours at selected nodes at once each time we advance

Label the visited.

BFS(G, s, f)
    visit(s)
    Queue.add(s)
    while not Queue.empty()
            curr = Queue.dequeue()
            if curr == f
                  return curr 
           for each neighbor u of curr
                   if u is not visited
                       visit(u)
                       Queue.enqueue(u)
return null  

1. Run BFS 

2. Start from s, put s in queue

3. Check if queue is empty else end

4. Not empty? => take out first node => curr
5. If curr is final, return curr
else

6. Look at the neighbours of curr,
if not visited, mark them as visited and add them in queue
else continue to next neighbour
7. go back to 3

BFS will not work in an unconnected graph.

The queue is use to add each frontier and pop each time we search the frontier's neighbours

During the execution, we explored the frontier level by level. We first explore the neighbours then explore our neighbours neighbour

BFS will fail in a >1 Component 

=> BFS works by searching neighbours, >1 component is an unconnected graph

Running time of BFS? (Assume adj List) is O(V + E)

=> Each vertex added once O(V) and for each node,  we list the neighbours only once O(E)

Running time of BFS? (Assume adj matrix) is O(V^2)

=> Looking through each neighbour takes v time, visiting is v

Depth first Search (DFS)

Look at at one path till reach dead end,
then we backtrack until reach an unexplored neighbour

Recursively explore till finish is found

Uses a Stack

DFS(G, s, f)
    visit(s)
    Stack.push(s)
    while not Stack.empty()
           curr = Stack.pop()
            if curr == f
                return curr
           for each neighbor u of curr
               if u is not visited
                       visit(u)
                      Stack.push(u)
     return null

1. Start from s, visit s

2. Store s in stack
3. while stack is not empty, else end
4. Pop stack, curr
5. If curr is finish, return curr
else
6. For each neighbour of curr,
if not visited => visit, push to stack
else => continue

If reach dead end (ie. all neighbours are visited), go backwards by polling the stack.
(Backtrack till find one path that was not taken yet by checking neighbours not visited)

7. Go back to 3

Running time of DFS (Adj List) is O(V+E)

=> The algo is the same as BFS except the data structure. Each vertex is added one and for each vertex we enumerate the neighbours

Recursion:

DFS(G, v, f)
   visit(v)
    if v == f
          return v
    for each neighbor u of v
            if u is not visited
                 w = DFS(G, u, f)
                 if w is not null
                      return w
      return null  

1. Visit the v
2. Check if v is f, return if is
3. check all neighbours of v
not visited => DFS recursively
if w not null, return w
4. Go back to 3

Both DFS and BFS visit every node and every edge once, not every path

Storing the Path

To store the path we just need to add one line for DFS

Save the parent each time we iterate down

1. Store the parent in array
edgeTo[neighbour_unvisited] = curr

//check the path exist first

Print path:

x = f
while (x != s)
    path.pushFront(x)
    x = edgeTo[x]   
path.pushFront(s)

Because the path is stored front back, we need to use this function to be in the correct order.

Shortest Path

BFS Store the shortest path.

In DFS, we will find a possible path that we can encounter first

But for BFS, we will choose the possible path that each neighbour can bring simultaneously

(This is for unweighted graphs)

We cannot search every path because it will take exponent time to search

Directed Acyclic Graph (DAG)

Not every directed graph have a topological ordering => Cyclic graph

Input: 

- An adjacency list (DAG)

Output:

A list of nodes in topological order

A topological ordering is possible only with DAG

KAHN's Algorithm

1. Start with a node v with no incoming edges
2. Add v to list

3. Remove v and its outgoing edges

4. repeat 1

L = list()
S = list()
add all nodes with no incoming edge to S
while S is not empty:
    remove node v from S
    add v to tail of L
    for each of v’s neighbors u
          remove edge e where source is v //remove edges
          if u has no other incoming edges //(1)
              add u to S  

This is similar to BFS because we move the frontier forward

Time complexity (adj-list): O(V+E)
=> O(v) add all nodes with no incoming edges to s
=> O(E) loop through all the nodes in S

Topological sort using DFS (Assume DAG)

Process node when it is last visited

We could use the hashset to check visited nodes
Use this only for topological.

Base idea:

1. Start from any path (run DFS)

=> Set the last node in that path as prev node

=> There is no outgoing edges for this node
2. Back track from the prev node
=> Pick any other unvisited node before

3.repeat



L = list()
while there are unvisited nodes
     v = select unvisited node
     DFS(G, v, L)
//this is to get the last node
====================
DFS(G,v,L)   if v is visited      return
    else
        for each of v’s neighbor u
              DFS(G, u, L)
     visit(v)
     L.pushFront(v)

1. If v is visited, return
else
2. Check every v neighbours and DFS it
3. Visit v
4. Add to list front

Time complexity: O(V+E)
=> DFS
=> Visit each node once, enumerates the edges

Is Every topological ordering unique: No

=> We can swap certain place