### Prof. Paulo Franca - Spring 2000

Introduction

Syllabus

Guidelines for labs

Lab sections

## Searching in Graphs

 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

#### 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