University of California, Santa Cruz

Prof. Paulo Franca - Spring 2000

Introduction

Syllabus

Guidelines for labs

Lab sections

Take quiz & check grades

Searching in Graphs

Breadth First Search

bulletGiven a graph and a source vertex "s":
bulletExplore all edges to discover every vertex reachable from "s".
bulletProduce a tree "Breadth First Tree" that contains all such vertices
bulletComputes the distance (number of edges) to all vertices
bulletPath in the BF Tree is the shortest path to each vertex.
bulletDirected and undirected graphs

Approach

bulletProgress uniformly in all directions (discovers all vertices at distance k before distance k+1)
bulletUse status or colors: white, gray , black
bulletwhite - not discovered
bulletgray - discovered but further edges are not explored
bulletblack - discovered and explored

Build a tree starting at "s"

bullets is the root
bulletscan all adjacent vertices and add new edges to the tree
bulletpredecessor or parent of vertex: u is parent of v if v was discovered from u

vertex information:

bulletinfo field
bulletparent vertex
bulletdistance in edges
bulletcolor

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.

bullet

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