Clone directed graph. The input to the algorithm is one of the nodes of the graph which contains a list of its adjacent nodes. Assume you can navigate visit all renaming nodes in the graph from the node that you are given. Your function has to return pointer to cloned graph.

View Solution

There are two approaches to solve this puzzle, both have to do with how can we traverse the graph. First one is breath first search, second is depth first search. In both solutions we need to keep track of all mappings between the original and new graph (e.g. hash table) as well as structure that would keep track of all visited nodes (e.g. set). Breath first search (BFS) uses queue for all nodes we should navigate next. We add nodes to the queue only if they were not yet visited.

Let's start with BFS solution:

Let's start with BFS solution:

struct Node { Node(int v) : value(v) {} int value; vector<Node*> adjacent ; }; Node* Lookup(Node *n, unordered_map<Node*, Node*> &map) { Node *m = nullptr; if (map.find(n) == map.end()) { m = new Node(n->value); map[n] = m; } else { m = map[n]; } return m; } Node* CloneGraphBFS(Node* graph) { if (!graph) return nullptr; unordered_map<Node*, Node*> map; unordered_set<Node*> visited; queue<Node*> q; q.push(graph); visited.insert(graph); while (!q.empty()) { Node *current = q.front(); q.pop(); Node *current_copy = Lookup(current, map); // Take care of connections for (size_t i = 0; i < current->adjacent .size(); ++i) { Node *next = current->adjacent [i]; Node *next_copy = Lookup(next, map); // Make connection current_copy->adjacent .push_back(next_copy); // Visit next to copy its connections if (visited.count(next) == 0) { q.push(next); visited.insert(next); } } } return map[graph]; }

Ok, next it is time to do the same with DFS approach. All we need to change is to use recursive call to visit all renaming nodes rather than using queue. Here is the code:

struct Node { Node(int v) : value(v) {} int value; vector<Node*> adjacent ; }; Node* Lookup(Node *n, unordered_map<Node*, Node*> &map) { Node *m = nullptr; if (map.find(n) == map.end()) { m = new Node(n->value); map[n] = m; } else { m = map[n]; } return m; } Node* CloneDFSHelper(Node *current, unordered_map<Node*, Node*> &map, unordered_set<Node*> &visited) { // Return if we already visited this node if (visited.count(current) != 0) return nullptr; // Mark as visited visited.insert(current); // Make a copy of current node or get one if we created it already Node *current_copy = Lookup(current, map); // Visit all adjacent nodes for (size_t i = 0; i < current->adjacent .size(); ++i) { Node *next = current->adjacent [i]; Node *next_copy = Lookup(next, map); // Make connection current_copy->adjacent .push_back(next_copy); // Clone everything under adjacent node CloneDFSHelper(next, map, visited); } return current_copy; } Node* CloneGraphDFS(Node *graph) { if (!graph) return nullptr; unordered_map<Node*, Node*> map; unordered_set<Node*> visited; return CloneDFSHelper(graph, map, visited); }