Introduction
Syllabus
Guidelines for labs
Lab sections
Take quiz & check grades
 
Searching in Graphs
Breadth First Search
 Given a graph and a source vertex "s": 
 Explore all edges to discover every vertex reachable from "s". 
 Produce a tree "Breadth First Tree" that contains all such vertices 
 Computes the distance (number of edges) to all vertices 
 Path in the BF Tree is the shortest path to each vertex. 
 Directed and undirected graphs 
Approach
 Progress uniformly in all directions (discovers all vertices at distance k before
distance k+1) 
 Use status or colors: white, gray , black
 white  not discovered 
 gray  discovered but further edges are not explored 
 black  discovered and explored 

Build a tree starting at "s"
 s is the root 
 scan all adjacent vertices and add new edges to the tree 
 predecessor or parent of vertex: u is parent of v if v was discovered from u 
vertex information:
 info field 
 parent vertex 
 distance in edges 
 color 
you need to save unexplored vertices for later exploration, suggestion: use a queue
you need to represent a list of edges (adjacent nodes), suggestion: use an adjacency list.
 Each vertex points to the first element in the list; elements may contain: vertex
id, weight, pointer to next element in list.

Algorithm approach:
build a Breadth First Tree from vertex "u" to vertex "v"
 Initialize all vertices
 Set up the source vertex;
 color=gray, distance=0, parent=0;
 put this node (s) in the queue Q.
 Explore vertices in queue Q:
 while (Q) not empty:
 {
 u = head of queue (Q); // remove it?
 for each vertex "v", adjacent to u:
 if v>color = white
 {
 color =gray
 distance=distance +1;
 parent = u
 put "v" in queue Q
 }
 Dequeue (Q)
 u > color = black
 }
ta
