Almost every type of data in the real world can be represented and understood on a graph much easier than any other data representation. A graph is a non-linear data structure consisting of a finite collection of vertices and a set of pairs of these vertices, also known as edges.

We'll be talking about a fascinating graph problem â€ślength of the longest increasing sequence in a graphâ€ť today and will look at an example and its implementation using C++. So letâ€™s begin with understanding the problem statement.

Problem Statement

You are given a graph Find the length of the Longest Increasing Sequence in a graph (LIS), i.e., the length of a sequence of nodes having values sorted in increasing order.

Letâ€™s see an example of the same and understand better.

Get the tech career you deserve, faster!

Connect with our expert counsellors to understand how to hack your way to success

User rating 4.7/5

1:1 doubt support

95% placement record

Akash Pal

Senior Software Engineer

326% Hike After Job Bootcamp

Himanshu Gusain

Programmer Analyst

32 LPA After Job Bootcamp

After Job Bootcamp

Example

We are given the following graph with the nodes 0,1,2,3 and 4. We have to find the length of the longest sequence.

Output

Explanation

Letâ€™s start finding increasing sequences in the above graph. Following are all the possible sequences:

0, 2

0, 2, 4

0, 4

0, 1, 4

0, 1, 3, 4

So, the longest increasing sequence in the graph consists of nodes 0, 1, 3, and 4, and Hence answer the length of this sequence, i.e., 4.

Dry Run

Letâ€™s look at how we have reached 4 as the longest length.

Start by taking the root node as 0. First, apply DFS Algorithm and store the result. The resulting array of nodes will look like this:

Now, traverse these nodes one by one; first, for the 0th node, check for its neighbors, i.e., 2 and 4. Since the smallest value than the 0th node doesnâ€™t exist, skip this.

Repeat the same for 1; its neighbors are 0, 4, and 3. We have to take a smaller value than the current node. So choose 0 and return the length to the 0th node plus one for the current node. Hence, the answer becomes 2.

Now, moving on to the next node, 4. Find the smallest of its neighbors, and return the maximum answer. Suppose we choose 3 as smaller than 4; now, repeat the same for 3. We will reach this sequence: 4 -> 3 - > 1 -> 0. Hence, the answer will be 4

Wasnâ€™t this easy? Now, letâ€™s look at the algorithm for this problem.

Algorithm

Our approach to this solution is to traverse each node and check for its neighbors with the help of recursion. This will help us to find the minimum length. Letâ€™s look at each step in detail:

Start by taking a node as the root node and applying the Depth-First-Search algorithm. Store the result of the DFS in an array.

Now, visit the nodes in the order of the above resultant array.

Find the longest sequence till that node by checking the neighbors whose values are smaller than the current node, and check the same for this neighbor element using recursion.

Repeat the steps until you reach the elements greater than the current node.

Update the temporary answer as the maximum length of the path till this node and add an extra one for the current node.

Update the answer as the maximum length of the path we can reach from all nodes and return the final answer after traversing all the nodes.

Now, letâ€™s look at the C++ Code for the same.

C++ Code

#include <bits/stdc++.h>
using namespace std;
// Template to create nodes of the graph
class Node
{
public:
vector<Node *> neighbors;
int val;
Node(int val)
{
this->val = val;
this->neighbors = {};
}
};
void dfs(Node *root, map<Node *, int> &visited, vector<Node *> &result)
{
// Return if you have already visited this node
if (visited.find(root) != visited.end())
return;
// Push the current node in the list
result.push_back(root);
// Update the visited map
visited[root] = 0;
// Apply dfs for all the neighbors of the current node
for (Node *nbr : root->neighbors)
{
dfs(nbr, visited, result);
}
}
int helper(Node *root, map<Node *, int> &visited)
{
// If the current node is already checked, return ans till that node
if (visited[root] != 0)
return visited[root];
// Initialize a temporary variable to store length
int tempAns = 0;
// Iterate through all it's neighbors
for (Node *nbr : root->neighbors)
{
// If value of neighbour is less than current node's value
// then apply recursion to check for further nodes
if (nbr->val < root->val)
{
// Update tempAns as maximum of answer and tempAns
tempAns = max(tempAns, helper(nbr, visited));
}
}
// Store this length + 1 ( for current node )
visited[root] = tempAns + 1;
// Return the answer till this node
return tempAns + 1;
}
int LISGraph(Node *root)
{
// Base case - If there is no node, return 0 as length
if (!root)
return 0;
// Variable to store the maximum length
int ans = 1;
// To track visited elements and to store answer till that node
map<Node *, int> visited;
// Store all nodes as a result of traversal
vector<Node *> result;
// First step - Apply dfs and store the sequence in nodes
dfs(root, visited, result);
// Traverse nodes one by one
int n = result.size();
for (int i=0; i<n; i++)
{
Node *currNode = result[i];
// If current node is not yet checked for LIS, check it
if (!visited[currNode])
{
helper(currNode, visited);
}
// Update the answer as maximum of maxi and curr length
ans = max(ans, visited[currNode]);
}
// Return the answer
return ans;
}
int main()
{
// Create 5 nodes
Node *zero = new Node(0);
Node *one = new Node(1);
Node *two = new Node(2);
Node *three = new Node(3);
Node *four = new Node(4);
// Set neighbors of 0th node
zero->neighbors.push_back(two);
zero->neighbors.push_back(four);
zero->neighbors.push_back(one);
// Set neighbors of 1st node
one->neighbors.push_back(zero);
one->neighbors.push_back(three);
one->neighbors.push_back(four);
// Set neighbors of 2nd node
two->neighbors.push_back(zero);
two->neighbors.push_back(four);
// Set neighbors of 3rd node
three->neighbors.push_back(one);
three->neighbors.push_back(four);
// Set neighbors of 4th node
four->neighbors.push_back(zero);
four->neighbors.push_back(one);
four->neighbors.push_back(two);
four->neighbors.push_back(three);
// Call the LISGraph function
cout <<"The Length of Longest Increasing Sequence of Nodes in a Graph is: " << (LISGraph(zero));
return 0;
}

The output for the above-discussed example is shown below:

Complexities

Time complexity

O(V + E) is the Time Complexity of this algorithm, where V denotes the count of the vertices and E refers to the number of edges in the graph as a result of the DFS function. In the worst case, we need to travel all the nodes.

Space complexity

O(V) is the space Complexity of this algorithm, where V denotes the count of the vertices in the graph due to the initialization of a set of nodes.

What is the difference between a graph and a tree?

Trees and graphs are not the same since a tree can never have loops, whereas a graph can. A tree's nodes are also always connected, but a graph's nodes are not.

What is the difference between a DFS Traversal and a BFS Traversal?

We start at any random node in a DFS traversal of a graph and travel down each branch before returning to the current node. In a BFS traversal, we visit each node before moving on to their offspring nodes.

Why does DFS use stack?

Whenever a situation of dead end occurs during any iteration, the Depth First Search (DFS) method employs a stack to track where to find the next vertex to begin a search.

How is a vertex set written?

The letters V(G) and E stand for the vertex and the edge set, respectively, of graph G. If the context makes the specific graph, we may refer to these sets as V and E.

Conclusion

In the article, we have discussed one popular question: the length of the longest increasing sequence in a graph with the help of an example. We hope that this article will help you understand the concept of a graph, and if you want to learn more about the graph, check out our other blogs on graphs: