Guidelines for labs
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|
|Progress uniformly in all directions (discovers all vertices at distance k before
|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|
|distance in edges|
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.
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