BREADTH FIRST TRAVERSAL Lesson Plan -3

Evocation

Breadth First Traversal

Process all adjacent vertices of a vertex before going to next level Pick a vertex A then process all of adjacent vertices (BCD) Process all of first vertex, pick its first adjacent vertex (B) and process all of vertices, then second adjacent vertex C and all of vertices

BFS Example

Breadth First Traversal Algorithm Algorithm breadth First (graph) if (empty graph) return end if create Queue (queue) loop (through all vertices) set vertex to not processed end loop loop (through all vertices) if (vertex not processed) if (vertex not in queue) enqueue (queue, walkptr) set vertex t enqueued end if

Breadth First Traversal Algorithm loop (not emptyQueue (queue)) set vertex to dequeue (queue) process (vertex) set vertex to processed loop (through adjacency list) if (destination not enqueued or processed) enqueue (queue, destination) set destination to enqueued end if get next destination end loop end if get next vertex end loop destroy Queue (queue) end breadth First

Graph Storage Structures To represent graph, need to store two set First set represent vertices of graph Second set represents edges or arcs Adjacency Matrix Use vector (one dimensional array) for vertices and a matrix (two dimensional array) to store edges If two vertices are adjacent If there is an edge between them the matrix intersect has value of 1 If there is no edge between them the matrix intersect has value of 0

Graph Representation

Adjacency matrix for non directed graph

Adjacency matrix for directed graph

Adjacency List Adjacency list uses two dimensional ragged array to store edges

Adjacency list for non directed graph

Adjacency list for directed graph

Adjacency Multilist Lists in which nodes may be shared among several lists (an edge is shared by two different paths) There is exactly one node for each edge Example

Mind Map Breadth First Traversal BFS Example BFS Algorithm Graph Storage Structures Adjacency Matrix Adjacency List Adjacency MultiList Directed Non-directed

Summary In breadth first search all adjacent vertices are processed before processing descendants of vertex To represent graph, we need to store two sets of information first represent vertices, second set represent edges Methods used to store graph are adjacency matrix, adjacency list, adjacency multilist In adjacency matrix, use a vector to store vertices and matrix to store edges In adjacency list, use linked list to store vertices and two dimensional linked list to store edges In adjacency multilist, nodes are shared among several list