Clone a Directed Acyclic Graph

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.

• 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.

• 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.

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

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

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

• 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;
}

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

Run Code

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)

You can also try this code with Online Python Compiler

Run Code

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:

• Number of Unique Good Subsequences
• Cut Into Segments
• Given a Linked List of Line Segments, Remove middle points
   

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!