Welcome Back!

Learning Objectives
By the end of this class, you should know...

  • How do you traverse a graph using the Breadth First Search Algorithm?
  • What is the SSSP problem?
  • How do you traverse a graph using the Depth First Search Algorithm?


Announcements
  • Return Midterm 2 - Awesome results!
    • As: 30
    • Bs: 8
    • Cs: 2
    • Ds: 1
    • Fs: 1
  • Project Report 4 due one week from today
    • Return Project Report 3
    • Please come see me if there was a problem with your project report.
    • Also, please see me if there was any issue with peer evaluations
  • Which project teams have not met with me regarding the project?
  • Final Exam Review Sheet Posted (with answer key linked at bottom of page)
    • Final exam is one week from Thursday


Review Activity

  • Is the graph connected or disconnected?
  • Is it directed or undirected?
  • Is it cyclic or acyclic?
  • What is the degree of vertex B in the graph?


Image source.



Writing a Graph Data Structure

  • Let's start to think programmatically about how we will represent a Graph as a data structure.
  • As we know, a Graph is simply a set of vertices and edges.
  • The vertices can be written as a vertex set and the edges as an edge set.
  • We saw an example an example of a vertex and edge set at the beginning of class.

    Asymmetric 7-vertex graph satisfying P<sub>1</sub>

    
    Vertex and Edge Sets for Graph G:   

    V(G)
= { 1, 2, 3, 4, 5, 6, 7}

           E(G) = {15, 17, 57, 45, 46, 67, 27, 26, 23, 34}

Adjacency Lists

  • In addition to using sets, there is another way to represent a Graph using what are called adjacency lists.
  • An adjacency list representation of a graph is a collection of unordered lists, one for each vertex in the graph.
  • Each list contains the set of adjacent vertices to that vertex.
  • For example, I could represent the above Graph G using an adjacency list like so:

1: 5, 7

2: 3, 6, 7

3: 2, 4, 6

4: 3, 5, 6

5: 1, 4, 7

6: 2, 3, 4, 7

7: 1, 2, 5, 6


Review Activity

With a partner, write out the adjacency list for the following Graphs:

  • How is the adjacency list different when the Graph is directed vs undirected?

Graph G1:


Image source.


Graph G2:




Adjacency Lists and the Graph Data Structure
  • Using the adjacency list representation of a Graph makes it easy to represent our Graph in code.
  • We can use an array of linked lists.
  • Each index of the array represents one vertex in our Graph.
  • The array at this location represents the adjacency list for that Graph.
  • We can see this representation as the depiction below:

images/lecture15/adjlistexample.png
Image source.

  • We will start writing our Graph data structure next class...
  • We will also talk about two special forms of search Depth First Search and Breadth First Search.


Breadth First Search

  • Breadth First Search (BFS) is a Graph Traversal Algorithm that solves the Single Source Shortest Path (SSSP) problem.
  • In other words, it finds the shortest path (fewest edges) between a source vertex and any other vertex in the graph.
  • BFS traverses across the graph rather than down each path, hence its name.
  • It also creates a BFS tree which is a subtree of the original graph that is rooted at the source vertex.
  • The algorithm uses a Queue, as well as a book-keeping scheme wherein vertices are assigned colors to keep track of which vertices have been visited as the algorithm progresses.


BFS Algorithm

BFS(G, s)

for all x in V(G)                

color[x] = white             

distance[x] = -1       

parent[x] = Nil              

color[s] = grey                 

distance[s] = 0                  

Enqueue(Q,s)

while(Q is not empty)

x = front of Q

Dequeue(Q,x)

for all y in adj[x]

if color[y] == white

color[y] = grey

distance[y] = distance[x] + 1

parent[y] = x

Enqueue(Q, y)

color[x] = black


BFS Big-O Run-time:

  • The Big-O run-time of BFS is considered to be O(|V| + |E|) 
  • Where |V| = number of vertices in the Graph and |E| is the number of edges.
  • Every vertex and every edge will be explored in the worst case when running BFS.


BFS Example

  • Let's trace through this algorithm with an example.
  • Consider the following graph G1:

Related image


  • Suppose that we wish to find the shortest distance from A to any other vertex in our graph.
  • In other words, we consider A to be our source vertex.
  • Recall that shortest distance means fewest number of edges.
  • As we trace BFS on the above graph, we will need to do some book keeping.
  • Thus, we should start by drawing the following chart to help organize us:

 Vertex Adjacency_List[]
 Color[] Distance[] Parent[]
 A G
 0 NIL
B
 W
-1 NIL
C  W-1 NIL
D
  W-1 NIL
E  W -1NIL
 F  W -1 NIL
 G  W-1 NIL

Queue: A

Colors

  • Here the Color column for each vertex will be set to one of three possible values: white, grey or black.
  • White indicates that a vertex has not been processed
  • Grey indicates that a vertex is in process
  • Black indicates that a vertex is finished being processed

Distance

  • The distance column indicates distance to the source vertex
  • The distance to the source from the source is 0, so we can immediately assign it a value.
  • Other vertices are assigned the value of -1 to start. This value will be updated as the algorithm progresses.

Parent

The parent column indicates which vertex immediately proceeded the current vertex in the path from the source to the current vertex.
  • NIL indicates that a parent has not been assigned.
  • However, in the case of the source vertex, the value of NIL will never be updated.

Queue

  • The Queue will maintain an order in which the vertices need to be processed.
  • The Queue is pre-filled only with the value of the source.
  • As vertices are processed, they are added to the back of the queue.
  • When they are finished being processed, they are dequeued.

A Word on the Source Vertex

  • The source vertex is indicated in purple.
  • I initialize it differently than the other vertices as it is already in progress as the algorithm starts
  • Note that I could apply the BFS algorithm using any vertex in my Graph as the source.


Review of Adjacency List Representation of a Graph

  • Take a sheet of paper and recreate the table above.
  • Also draw the corresponding graph on your paper
  • Then, fill in the adjacency list for each of the vertices.
  • Hold onto the paper when you are finished, as you will fill in the table as the BFS algorithm is applied.


Activity: BSF on Graph G1

  • While the professor is tracing through the BFS example on G1, update your own paper.


BFS on G1:


breadth first search demo

Image source.


BFS Activity


  • Trace BFS on the following graph, using 8 as the source vertex

ملف:Disconnected simple graph.svg

  • Don't forget to use the following chart and to darken the lines of the BFS tree that results from tracing the graph


 Vertex Adjacency_List[]
 Color[] Distance[] Parent[]
 0 W
 -1 NIL
1
 W
-1 NIL
2
  W-1 NIL
3
  W-1 NIL
4
  W -1NIL
 5  W -1 NIL
 6  W-1 NIL
 7  W -1NIL
 8  W -1NIL

Queue:



Depth First Search

  • Depth First Search (DFS) is another algorithm for traversing or searching a Graph.
  • Unlike BFS, however, DFS does not provide us with a solution to the SSSP problem.
  • The algorithm recursively traverses the depth of the Graph (downward), rather than its breadth (across).
  • DFS creates what is called a DFS forest, which provides us with useful information about the edges in the Graph.


DFS Algorithm

DFS(G)

for all x in V(G)

    color[x] = W

    parent[x] = NIL

    discover_time[x] = -1

    finish_time[x] = -1

time = 0

for all x in V(G)

    if color[x] == W

        Visit(x)


Visit(x)

color[x] = G

discover_time[x] = ++time

for all y in adj[x]

    if color[y] == W

        parent[y] = x

        Visit(y)

color[x] = B

finish_time[x] = ++time


DFS Big-O Run-time:

  • The Big-O run-time of DFS, like BFS, is considered to be O(|V| + |E|) 
  • Where |V| = number of vertices in the Graph and |E| is the number of edges.
  • Every vertex and every edge will be explored in the worst case with DFS.


DFS Example
  • Let's trace through this algorithm with an example.
  • Consider the following graph:

ملف:Disconnected simple graph.svg

  • The book-keeping involved with DFS is also somewhat different than BFS.
  • Here, we keep track of start and finish times of vertices, in addition to colors and parents (no distances).
 Vertex Adjacency List
 Color Discover Finish Parent
 0 W
 -1-1
  NIL
1
 W
-1
-1  NIL
2
  W -1 -1  NIL
3
  W-1 
 -1  NIL
4
  W -1 -1
 NIL
 5  W -1  -1  NIL
 6  W-1 
 -1  NIL
 7
  W -1 -1NIL
 8  W-1
-1
NIL

Colors

  • Here the Color column for each vertex will be set to one of three possible values: white, grey or black.
  • White indicates that a vertex has not been processed
  • Grey indicates that a vertex is in process
  • Black indicates that a vertex is finished being processed

Discover Time (1 - 2n)

  • The time at which the vertex was first discovered (colored gray).
  • Initialized to 0

Finish Time (1 - 2n)

  • The time at which the vertex was finished (turned black).
  • Initialize to 0

Parent

  • The parent column indicates which vertex immediately proceeded the current vertex in the path from the source to the current vertex.
  • NIL indicates that a parent has not been assigned.
  • However, in the case of the root of the graph (or connected component).

A Word on the Lack of a Source Vertex

  • Since we are not trying to find a shortest path here, there is no source vertex.
  • Instead, we always start at the "root" of the graph, which in practice is we usually progress in ascending or descending order.

Group Activity

  • Take a sheet of paper and recreate the table above.
  • Also draw the corresponding graph on your paper
  • Then, fill in the adjacency list for each of the vertices.
  • Hold onto the paper when you are finished, as you will fill in the table as the DFS algorithm is applied.
  • While the professor is tracing through the DFS example on G1, update your own paper.
  • Also fill in the DFS forest.


Group Activity

  • On a new sheet of paper, trace DFS on the following graphs.
  • For credit, you need to trace the values on the table as shown during the lesson.
  • You should also create the DFS forest.
  • Refer to the algorithm when in doubt.
  • Process the vertices in ascending order.
  • When you are finished, think to yourself: How would I handle this disconnected graph if I applied the BFS algorithm?

Graph 1:


Graph 2:

Image source.

Applications of DFS and BFS


Image source.

Cycle detection                                  Shortest Path

Connected Components                           Connectivity Testing



Edge Classification

figure4051

Gray to White       Gray to Black             Gray to Gray                Gray to Black

Image source.

  • Back edges indicate a cycle!
Wrap Up
  • With your partner, answer the questions from today's learning objectives