Code360 powered by Coding Ninjas X Naukri.com. Code360 powered by Coding Ninjas X Naukri.com
Table of contents
1.
Introduction
2.
Problem Statement
2.1.
Sample Example
3.
DFS Approach
3.1.
Algorithm
3.2.
Dry Run
3.3.
Code in C++
3.4.
Code in Python
3.5.
Algorithm Complexity
4.
Frequently Asked Questions
4.1.
What is DFS?
4.2.
What is BFS?
4.3.
Can there be multiple shortest paths in a graph?
4.4.
What is a graph?
4.5.
What are some common applications of DAG graphs?
5.
Conclusion
Last Updated: Mar 27, 2024
Easy

Clone a Directed Acyclic Graph

Roadmap to SDE career at Amazon
Speaker
Anubhav Sinha
SDE-2 @
25 Jun, 2024 @ 01:30 PM

Introduction

This blog will discuss the solution to the problem of cloning a directed acyclic graph. Let’s first understand what a DAG (Directed Acyclic Graph) means. 

A directed acyclic graph is a graph data structure consisting of nodes and directed edges connecting these nodes such that edges are unidirectional and do not form a cycle. 

Introduction image

Before we dive deep into the solution to this problem, we should look at a sample example to better understand this problem.

Problem Statement

Given a directed acyclic graph (DAG) represented as a set of vertices and edges. We need to create a copy of the graph such that the copy is identical to the original graph.

Sample Example

Input 

Example input DAG

Output 

The cloned graph: 

1-2
2-3
3-4
3-5
3-6
 

Explanation

  • Traversing the graph in the depth-first search algorithm, we first go to the starting node, let’s say 1 in this case, and add it to the cloned graph.
     
  • Now we go to the adjacent neighbors of 1, which is 2. We again add 2 in the cloned graph, i.e., 1-2.
     
  • Similarly, from 2, we reach 3 as 3 is its only neighbor. Add 3 to the cloned graph, i.e.1-2, 2-3.
     
  • Now from 3, we can go either to 4, 5, or 6. Let’s say we go to 4. Add 4 to the cloned graph, i.e., 1-2, 2-3, 3-4.
     
  • Since 4 has no neighbors, it will backtrack to 3, and we go to 5, i.e., 1-2, 2-3, 3-4, 3-5.
     
  • Now we see that there is no neighbor for 5. Therefore we backtrack to 3. 
     
  • From 3, we go to the last unvisited node, 6, i.e., 1-2, 2-3, 3-4, 3-5, 3-6.
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

DFS Approach

To duplicate a directed acyclic graph, we can perform a DFS (depth-first search) on the graph. During this, we can assign the value of each original node to its corresponding newly created neighboring nodes. We should continue this procedure until we have traversed the entire original graph.

Algorithm

  1. Define a function called ‘printGraph’ that takes a starting node and an unordered_map to keep track of visited nodes. The function will print the graph in DFS order starting from the given node. It uses a stack to traverse the graph.
     
  2. Define a function called ‘cloneGraphHelper’ that recursively clones the graph using DFS Algorithm traversal. The function takes three arguments: the previous node, an unordered_map to keep track of cloned nodes, and an unordered_map to keep track of visited nodes. The function returns the cloned node.
     
  3. If the previous node is null, return null.
     
  4. If the previous node is already cloned, return the cloned node.
     
  5. Create a new node with the value of the previous node, and mark it as cloned and visited.
     
  6. Clone all adjacent nodes of the previous node recursively, and push them into the adjacency list of the new node.
     
  7. Return the new node.

Dry Run

  • For every node in the graph, we will traverse for its adjacent elements, mark the starting node as visited, and see if it’s added to the cloned graph. If not, add it to the cloned graph.

Step 1

  • Then traverse for neighboring nodes of 1. If it is unvisited, traverse them. And add it to the cloned graph. Here 2 is the only unvisited node of 1 that is not visited.

Step 2

  • Now traverse for neighboring components of 2. Add 2 to the cloned graph. And traverse for neighboring nodes of 2. 3 is the only connected neighbor of 2 which is not visited. So add 3 to the cloned graph.

Step 3

  • Now, we can traverse any of the neighbors of 3. Here we are traversing 4. Add 4 to the cloned graph.

Step 4

  • Now there are no neighbors of 4. Backtrack to 3 and traverse 5, which is unvisited and add it to the cloned graph.

Step 5

  • Now again backtrack to 3 as there are no neighbors of 5.

Step 6

  • Now, visit 6 and mark it as visited, and add the node to the cloned graph. Here we have visited all the nodes and can get the cloned graph. 

Code in C++

#include <bits/stdc++.h>
using namespace std;

// This class represents a node in the graph.
class Node {
public:
    // Value of the node
    int val;
    // Adjacency list of the node
    vector<Node*> adj;

    // Constructor to initialize the node with a value.
    Node(int val) {
        this->val = val;
    }
};

// This function prints the graph in DFS order starting from a given node.
void printGraph(Node* startNode, unordered_map<int, bool>& visited) {
    stack<Node*> st;
    st.push(startNode);
    visited[startNode->val] = true;

    while (!st.empty()) {
        Node* cur = st.top();
        st.pop();

        // Print the edge from the current node to each of its neighbours.
        for (auto itr : cur->adj) {
            cout << cur->val << " " <<  "->" << " " <<  itr->val << endl;

            /* 
                If the neighbour has not been visited, mark it 
                as visited and push it onto the stack.
            */
            if (!visited[itr->val]) {
                visited[itr->val] = true;
                st.push(itr);
            }
        }
    }

    // Clear the visited map before exiting.
    visited.clear();
}

// This function recursively clones a graph using DFS traversal.
Node* cloneGraphHelper(Node* prev, unordered_map<int, Node*>& duplicate) {
    // Base case: if the current node is null, return null.
    if (prev == nullptr) {
        return nullptr;
    }

    // If the node is already cloned, return the cloned node.
    if (duplicate.find(prev->val) != duplicate.end()) {
        return duplicate[prev->val];
    }

    // Create a new node and mark it as visited and cloned.
    Node* newNode = new Node(prev->val);
    duplicate[prev->val] = newNode;

    // Clone all the adjacent nodes recursively.
    for (auto neighbour : prev->adj) {
        Node* clonedNeighbour = cloneGraphHelper(neighbour, duplicate);
        newNode->adj.push_back(clonedNeighbour);
    }

    return newNode;
}

// This function clones the given graph using DFS traversal.
Node* cloneGraph(Node* prev) {
    
    // If the current node is null, return null.
    if (prev == nullptr) {
        return nullptr;
    }

    // Create maps to keep track of visited and cloned nodes.
    unordered_map<int, Node*> duplicate;

    // Clone the graph recursively starting from the given node.
    return cloneGraphHelper(prev, duplicate);
}

int main() {
    Node* n0 = new Node(1);
    Node* n1 = new Node(2);
    Node* n2 = new Node(3);
    Node* n3 = new Node(4);
    Node* n4 = new Node(5);
    Node* n5 = new Node(6);

    n0->adj.push_back(n1);
    n1->adj.push_back(n2);
    n2->adj.push_back(n3);
    n2->adj.push_back(n4);
    n2->adj.push_back(n5);

    unordered_map<int, bool> visited;
    cout << "Graph Before Cloning:-\n";
    printGraph(n0, visited);

    Node* clonedGraph = cloneGraph(n0);

    cout << "\nGraph After Cloning:-\n";
    // clear visited map before calling printGraph()
    visited.clear();
    printGraph(clonedGraph, visited);

    return 0;
}


Output

Cpp output

Code in Python

from typing import List, Dict

# This class represents a node in the graph.
class Node:
    def __init__(self, val: int):
        self.val = val  # Value of the node
        self.adj = []  # Adjacency list of the node

# This function prints the graph in DFS order starting from a given node.
def printGraph(startNode: Node, visited: Dict[int, bool]) -> None:
    st = [startNode]
    visited[startNode.val] = True

    while st:
        cur = st.pop()

        for itr in cur.adj:
            print(cur.val, "->", itr.val)
            if itr.val not in visited or not visited[itr.val]:
                visited[itr.val] = True
                st.append(itr)

    # Clear the visited map before exiting
    visited.clear()

# This function recursively clones a graph using DFS traversal.
def cloneGraphHelper(prev: Node, duplicate: Dict[int, Node]) -> Node:
    # Base case
    if prev is None:
        return None

    # If the node is already cloned, return the cloned node.
    if prev.val in duplicate:
        return duplicate[prev.val]

    # Create a new node and mark it as visited and cloned.
    newNode = Node(prev.val)
    duplicate[prev.val] = newNode

    # Clone all the adjacent nodes recursively.
    for neighbour in prev.adj:
        clonedNeighbour = cloneGraphHelper(neighbour, duplicate)
        newNode.adj.append(clonedNeighbour)

    return newNode

# This function clones the given graph using DFS traversal.
def cloneGraph(prev: Node) -> Node:
    if prev is None:
        return None

    # Create maps to keep track of visited and cloned nodes.
    duplicate = {}

    # Clone the graph recursively starting from the given node.
    return cloneGraphHelper(prev, duplicate)

if __name__ == '__main__':
    n0 = Node(1)
    n1 = Node(2)
    n2 = Node(3)
    n3 = Node(4)
    n4 = Node(5)
    n5 = Node(6)

    n0.adj = [n1]
    n1.adj = [n2]
    n2.adj = [n3, n4, n5]
    
    visited = {}
    print("Graph Before Cloning:-")
    printGraph(n0, visited)

    clonedGraph = cloneGraph(n0)

    print("\nGraph After Cloning:-")
    # Clear visited map before calling printGraph()
    visited.clear()
    printGraph(clonedGraph, visited)


Output

Python Output

Algorithm Complexity

Time Complexity: O(E+V)

The time complexity will be O(E+V), where ‘E’ is the edge of the graph, and ‘V’ is the vertice of the graph. The function “printGraph()” visits every node and every edge in the graph once, which takes O(V+E) time.

Space Complexity: O(V)

The space complexity of the code is O(V), where V is the number of nodes in the graph. This is due to using maps to store cloned nodes and visited nodes during the cloning process and a stack to keep track of nodes to be visited in the printGraph() function.

Check out this problem - Duplicate Subtree In Binary Tree

Frequently Asked Questions

What is DFS?

DFS, or depth-first search, is a graph traversal algorithm that explores as far as possible along each branch before backtracking.

What is BFS?

BFS, or breadth-first search, is a graph traversal algorithm that explores all the vertices of a graph level by level.

Can there be multiple shortest paths in a graph?

Yes, we can find multiple shortest paths in a graph.

What is a graph?

A graph is a non-linear data structure consisting of nodes and edges. The nodes can be called vertices, and edges connect two nodes.

What are some common applications of DAG graphs?

DAG (Directed Acyclic Graph) graphs are commonly used in task scheduling and project management, where tasks or activities are represented as nodes, and the dependencies between them are represented as directed edges.

Conclusion

In this blog, we learned how to clone a directed acyclic graph. We have implemented the problem in C++ and python programming languages.

For more Graph data structure articles, you can refer following links:

To learn more about DSA, competitive coding, and many more knowledgeable topics, please look into the guided paths on Coding Ninjas Studio. Also, you can enroll in our courses and check out the mock test and problems available to you. Please check out our interview experiences and interview bundle for placement preparations.

Happy Coding!

Previous article
Clone of an undirected graph
Next article
Word Ladder
Live masterclass