Length of Longest Increasing Sequence in a Graph

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:

1. 0, 2
2. 0, 2, 4
3. 0, 4
4. 0, 1, 4
5. 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;
}

You can also try this code with Online C++ Compiler

Run Code

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.

Check out this problem - Shortest Common Supersequence.

Frequently Asked Questions

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:

• Detect cycle in directed graph
• Introduction to Graphs
• Graph Theory
• Graph Representation
• Properties of Graph
   

You can refer to our guided paths on the Coding Ninjas Studio platform to learn more about DSA, DBMS, Competitive Programming, Python, Java, JavaScript, etc. To practice and improve yourself in the interview, you can also check out Top 100 SQL problems, Interview experience, Coding interview questions, and the Ultimate guide path for interviews. Do upvote our blog to help other ninjas grow.

Happy Coding !!