Recitation 9 Graph Traversal Algorithms Solved

Some aspects of the real world can be represented as a relationship between objects and the connections between them. For ex., an airline route map, the expansive road network of the United States. Modeling them helps us answer some of the questions such as

    • What is the duration of a direct flight between Denver and San Francisco?

    • What is the distance between Denver to San Francisco via road?

Graphs are the Data Structures used to approach these questions.

Graph: A graph is a pair (V, E), where V is a set of nodes, called vertices and E is a collection of pairs of vertices, called edges.

Directed Edge

    • Ordered pair of vertices (u, v)

    • First vertex u is the origin.

    • Second vertex v is the destination.

    • Example: one way road traffic




u        v



Undirected Edge

    • Unordered pair of vertices (u, v)

    • Example: Railway lines




u    v




Applications

    • Representing relationships between components in electronic circuits.

    • Transportation networks: Highway network, Flight network

    • Computer networks: Local area network, Internet web



Graph Representation

As in other Abstract Data types, to manipulate graphs we need to represent them in some useful form. Two of the most popular ways are
    • Adjacency Matrix

    • Adjacency Lists

Graph Traversals

A precursor to solving the questions that we posed above using Graphs, we must learn how to traverse them. Graph Traversal Algorithms are also called Graph Search Algorithms. The two most commonly used traversal algorithms are

    • Depth First Search (DFS)

    • Breadth First Search (BFS)



Depth First Search (DFS)


Depth first search involves choosing a vertex as a starting point, and picking one of its unvisited neighboring vertices, and doing this process recursively till all nodes are marked visited. At every step, we remember the vertex from which we visited the current vertex. This enables backtracking once we have no more neighboring vertices marked unvisited.
CSCI 2270 – Data Structures


Recitation 9

Graph Traversal Algorithms



The pseudocode is shown below


























It is important to mark nodes as they are visited. This is done when the nodes are popped out of the Stack. And care is taken to ensure that only nodes marked as “not visited” are pushed onto the Stack. This recursive behavior (which uses a system stack) can be simulated by an iterative algorithm explicitly using a stack. So, DFS uses a stack to push nodes we mean to visit.

We gave a pseudocode for DFS traversal using recursion and we will be giving a visualization of DFS traversal using stacks to help you understand better. The following will give you the basic idea of Stack implementation.
CSCI 2270 – Data Structures


Recitation 9

Graph Traversal Algorithms


›
CSCI 2270 – Data Structures


Recitation 9

Graph Traversal Algorithms

CSCI 2270 – Data Structures


Recitation 9

Graph Traversal Algorithms





















As C does not have any unvisited adjacent node so we keep popping the stack until we find a node that has an unvisited adjacent node. In this case, there is none and we keep popping until the stack is empty.

Applications of DFS

    • Finding connected components in an undirected graph

(a variant of DFS is used for doing the same in directed graphs - Kosaraju algorithm)

    • Solving puzzles, such as mazes (DFS helps to reach the goal faster)





Breadth First Search (BFS)

Breadth-first search is one of the simplest algorithms for searching a graph and the archetype for many important graph algorithms.

BFS works level by level. Initially, BFS starts at a given vertex, which is at level 0. In the first stage it visits all vertices at level 1 (its immediate neighbors). In the second stage, it visits all vertices at second level (neighbors’ neighbors). These new vertices are the one which are adjacent to level 1 vertices.

BFS continues this process until all the levels of the graph are completed. Generally, Queue Data Structure is used for storing the vertices of a level. Like DFS, assume that initially all vertices are marked as unvisited. Vertices that have been processed and removed from the queue are marked visited. We use a queue to represent the visited set as it will keep the vertices in order of when they were first visited.
CSCI 2270 – Data Structures


Recitation 9

Graph Traversal Algorithms


Breadth-first search is so named because it expands the frontier between discovered and undiscovered vertices uniformly across the breadth of the frontier. That is, the algorithm discovers all vertices at distance k from s before discovering any vertices at distance k + 1.

Similarly, we have an example for BFS as well using queues.
CSCI 2270 – Data Structures


Recitation 9

Graph Traversal Algorithms

CSCI 2270 – Data Structures


Recitation 9

Graph Traversal Algorithms




















































Applications of BFS

    • Finding all connected components in an undirected graph.

    • Finding the shortest path between two nodes.

    • Finding nodes at distance k from a source node - e.g., find friends of friends on social media
CSCI 2270 – Data Structures


Recitation 9

Graph Traversal Algorithms








Comparison of BFS vs DFS on a simple graph:























Exercise


        A. Silver Badge Problem (Mandatory)


            1. Download the Recitation 9 zipped file from Canvas and open Lab 9.

            2. Follow the TODOs and in Graph.cpp, complete the findShortestPath() function.

            3. This function finds the length of the shortest path between a source and destination vertex in an undirected and unweighted graph.



    B. Gold Badge Problem


            1. In Graph.cpp, complete the printPath() function after modifying the findShortestPath() function so as to print the shortest path after finding it’s length.