Data Structures and Algorithms: Undirected Graph Processing

In the last post, we saw about what is a graph? How to build one from scratch? Where can it be used? In case, if you need a small recap on graphs or if you’re new to graph, check out my previous post:

Data Structures: Graph

By the end of the last post, you might have had a lingering thought on the back of you’re mind, ‘ I’m aware of what is a graph and its awesome applications. And I’m pretty sure on how to implement one, but how can I get these awesome functionalities of this powerful data structure into action?’

To solve that problem, let’s dive into some graph processing algorithms. We are going to look into 3 algorithms in this post :

1. Depth-First Search(DFS)
2. Breadth-First Search(BFS)
3. Connected Components(CC).

Depth-First Search:

DFS is a classical graph processing algorithm, used for traversing or searching a graph or tree data structure(a graph without any cycles can be thought of as an tree). The idea is pretty simple,

1. we arbitrarily select a vertex in a graph and
2. then we visit it’s neighboring vertices.
3. Continue this process recursively until there are no neighboring nodes for a particular node,
4. while doing so, we maintain an array to check if the particular adjacent vertex is visited or not, this is to avoid visiting the same node more than once.
5. Then we backtrack and check for other unmarked vertices and traverse them in a same way we did earlier.

Whoa, that is a lot of words to be honest !😅. Maybe we will look at an illustration to get a better intuition,

DFS in action

1. First we randomly select a vertex, here it is ‘1’ and we look at 1’s neighbors which are ‘2’ and ‘6’ .
2. Then we choose to visit ‘2’ first, and now instead of visiting the next neighbor of ‘1’ which is ‘6’,
3. we go onto visit 2’s neighbors which are ‘3’ and ‘5’, in the process of visiting ‘3’ we decide to visit 3’s neighbor too.

I hope that explains the recursive strategy of DFS to visit vertices on a graph.

Moral: Don’t get too obsessed with DFS 😂

Algorithm

a) Create a recursive function called DFS that takes the index of vertex to be visited.

b) Mark the current as vertex as visited in the boolean indexed array.

c) Traverse all the adjacent nodes if they are not visited and call the recursive function with index of adjacent vertex.

So, let’s look into some code to get a better idea of the DFS algorithm. To get one thing right out of the start, DFS is based on recursive strategy so, you could either go with

1. recursive function or
2. stack for implementation.

I have chosen stack for my implementation as it pretty easy to understand, if you’re not confident with recursion.(I will be using java for my example, but I will be providing the API for the algorithm so you could have building one of these on your own.)

DFS API

DFS Code

Applications

Some typical applications of DFS are:

1. Find all vertices connected to a given source vertex
2. Find a path between two vertices
3. Flood fill(Photoshop magic wand).

Breadth-First Search:

BFS is another classical graph processing algorithm, similar to DFS it is used for traversing or searching a tree or graph data structure. The objective of a BFS algorithm is similar to that of DFS, only the strategy of execution differs.

BFS in action

1. First we randomly select a vertex, here it is vertex ‘1’ and we look at 1’s neighbors which are ‘2’ and ‘3’.
2. Then, we choose to visit ‘2’ and then we keep track of 2’s neighbors but we don’t visit them yet.
3. Rather we choose to visit ‘3’ and then we keep track of 3’s neighbors.
4. Now, we plan to visit neighbors of ‘2’ and then to neighbors of ‘3’ and so on.,

Algorithm

a) Select a vertex from a graph as the source vertex s.

b) Put s onto a FIFO queue, and mark s as visited.

c) Repeat this until queue is empty:

(i) remove the least recently added vertex v

(ii) add each of v’s unvisited neighbors to the queue, and mark them as visited.

BFS API

BFS Code

Applications

Some typical applications of BFS are:

1. Social networks, you could have seen in LinkedIn profiles stated as 1st, 2nd and 3rd degree connection with respect to your profile.
2. Shortest path and minimum spanning tree for unweighted graph.
3. Crawlers in search engine are built index based using BFS.
4. GPS navigation systems: BFS is used to find shortest paths from one location to another location.

Difference b/w DFS and BFS

Here is an illustration depicting the difference in approach between DFS and BFS:

Connected Components

The relation “is connected to” is an equivalence relation:

a) reflexive: vertex v is connected to itself

b) symmetric: if vertex v is connected to vertex w, then w is connected to v

c) transitive: if v connected to w and w connected to x, then v connected to x

In simple words, a connected component is a maximal set of connected vertices.

Algorithm

a) Initialize all vertices v as unmarked.

b) For each unmarked vertex v, run DFS to identify all vertices discovered as part of the same component.

Connected-Components API

Connected-Components Code

So, we have come to the end of this post and thank you so much 😊 if you have made this far into this post. I will see you in the next post with introduction to directed graphs and some directed-graph processing algorithms!! Always grateful, never complacent!

References

1. Algorithms book by Robert Sedgewick
2. https://www.geeksforgeeks.org/depth-first-search-or-dfs-for-a-graph/
3. https://www.geeksforgeeks.org/breadth-first-search-or-bfs-for-a-graph/
4. https://en.wikipedia.org/wiki/Component_(graph_theory)

My Github Repository

1. https://github.com/Sethuram52001/DSA