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