Intro to Graphs (part 3)

Published in

Nerd For Tech

6 min readApr 3, 2021

Hello all! This is part 3 of the series Intro to Graphs. Part 1 was the general introduction of what graphs are. In summary, a graph data structure is a finite set of vertices (nodes) and set of edges which connect a pair of nodes. In graphs, there are no rules dictating the connection among the nodes. The edges can connect nodes no matter their placement. Part 2 was learning about the two standard approaches of representing graphs, an adjacency matrix and an adjacency list. This article will be going over graph traversal.

Practical uses

Why do we need to know graph data structure? There are many practical uses for graphs that we use daily.

Peer to peer networking
Web crawlers
Finding “closest” matches/recommendations
Shortest path problems:

o GPS Navigation

o Solving mazes

o AI (shortest path to win the game)

Depth First Search (DFS)

Depth first search traverses down a single path, one child node at a time until the end of a branch. Depth first search will tell us if there is a path from the starting node and the end node. DFS can be implemented using recursion or iteration.

DFS Recursion

The recursive implementation determines whether two nodes have a path between them by looking at all the children of the starting node until it reaches the end node. It does this by recursively taking the same steps, again and again to determine if such a path between two nodes even exists. We go down a path until we reach the end node or cannot follow it anymore. If the path becomes a dead end, we backtrack and retrace our steps until we find another possible path to follow.

Implementation

Create an array to store the end result
Create an object to store visited vertices
Create a helper function which accepts a vertex:

o The helper function should return early if the vertex is empty

o The helper function should place the vertex it accepts into the visited object and push that vertex into the result array

o Loop over all of the values in the Adjacency List for that vertex

o If any of those values have not been visited, recursively invoke the helper function with that vertex

Invoke the helper function with the starting vertex
Return the result array

We want to visit every single node of the graph starting at node A. We add A to the result array and mark A as visited in the visited object. We go from A to B, mark it as visited and add it to our result array. We have the option at B to go to A or D. We check if B has any edges that have been visited. A has been visited so we ignore A and go to the next node, D. We mark D as visited and add it to the result array. B has already been visited so we go to the next node, D. We can go to either E or F. We go to E then to C. We are now at a dead end. We still have not visited F. Node E has three edges, C, D, and F. Using the recursion from our helper method, we visit F. The result array will be [A,B,D,E,C,F]

DFS Iteration

The iterative implementation is very similar to the recursive implementation. We use a stack data structure to keep track of the vertices instead of using recursion. Here is my article on stacks if a reminder is needed.

Implementation

Create a stack to help use keep track of vertices (use a list/array)
Create an array to store the end result
Create an object to store visited vertices
Add the starting vertex to the stack, and mark it visited
While the stack is not empty:

o Pop the next vertex from the stack

o If that vertex hasn’t been visited yet:

§ Mark it as visited

§ Add it to the result list

§ Push all of its neighbors into the stack

Return the result array

We will use the same graph as above and we still want to visit every single node starting at node A. We mark A as visited, add it to the result array and pop it from the stack. We check if A’s neighbors, B and C, have been visited. They have not so we add them to the stack and mark them as visited. The stack is now [B,C]. Since C is the last one in the stack, we pop C from the stack, go to C, and add it to the result array. We then add C’s neighbors that have not been visited yet to the stack. The stack is now [B,E]. We follow the same pattern until the stack is empty. The result array will be [A,C,E,F,D,B].

Breadth First Search (BFS)

Instead of traversing doing a single path, breadth first search graph traversal depends on visiting neighbor nodes before visiting children nodes. From the starting node, it has children nodes, and those children nodes have children nodes of their own. We traverse the graph layer by layer. We visit a node, then visit all of its children before moving on to grandchildren. We use a queue data structure to keep track of nodes to visit before moving on to another layer. Here is my article on queues for a refresher. Breadth first search graph traversal is commonly used to determine the shortest path between two nodes in the graph.

Implementation

Create a queue and place the starting vertex in it
Create an array to store the end result
Create an object to store nodes visited
Mark the starting vertex as visited
Loop as long as there is anything in the queue
Remove the first vertex from the queue and push it into the array that stores nodes visited
Loop over each vertex in the adjacency list for the vertex you are visiting.
If it is not inside the object that stores nodes visited, mark it as visited and enqueue that vertex
Return the result array

The graph is slightly different, but we still want to visit every single node of the graph starting at node A. We mark A as visited, add it to the result array and remove it from the queue. We check if A’s neighbors, B and C, have been visited. They have not, so we add them to the queue and mark them as visited. The queue is now [B,C]. Opposite to using a stack, we are removing from the front of the queue. B is the first node in the queue, so we remove B from the queue, go to B, and add it to the result array. We then add B’s neighbors that have not been visited yet to the queue. The queue is now [C,D]. We follow the same pattern until the queue is empty. The result array will be [A,B,C,D,E,F].