-
Notifications
You must be signed in to change notification settings - Fork 72
/
Clone a Graph
133 lines (116 loc) · 2.98 KB
/
Clone a Graph
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
// C++ program to clon a directed acyclic graph.
#include <bits/stdc++.h>
using namespace std;
// Class to create a new graph node
class Node
{
public:
int key;
vector<Node *> adj;
// key is the value of the node
// adj will be holding a dynamic
// list of all Node type neighboring
// nodes
Node(int key)
{
this->key = key;
}
};
// Function to print a graph,
// depth-wise, recursively
void printGraph(Node *startNode,
vector<bool> &visited)
{
// Visit only those nodes who have any
// neighboring nodes to be traversed
if (!startNode->adj.empty())
{
// Loop through the neighboring nodes
// of this node. If source node not already
// visited, print edge from source to
// neighboring nodes. After visiting all
// neighbors of source node, mark its visited
// flag to true
for(auto i : startNode->adj)
{
if (!visited[startNode->key])
{
cout << "edge " << startNode
<< "-" << i
<< ":" << startNode->key
<< "-" << i->key
<< endl;
if (!visited[i->key])
{
printGraph(i, visited);
visited[i->key] = true;
}
}
}
}
}
// Function to clone a graph. To do this, we
// start reading the original graph depth-wise,
// recursively. If we encounter an unvisited
// node in original graph, we initialize a
// new instance of Node for cloned graph with
// key of original node
Node *cloneGraph(Node *oldSource,
Node *newSource,
vector<bool> &visited)
{
Node *clone = NULL;
if (!visited[oldSource->key] &&
!oldSource->adj.empty())
{
for(auto old : oldSource->adj)
{
// Below check is for backtracking, so new
// nodes don't get initialized everytime
if (clone == NULL ||
(clone != NULL &&
clone->key != old->key))
clone = new Node(old->key);
newSource->adj.push_back(clone);
cloneGraph(old, clone, visited);
// Once, all neighbors for that particular node
// are created in cloned graph, code backtracks
// and exits from that node, mark the node as
// visited in original graph, and traverse the
// next unvisited
visited[old->key] = true;
}
}
return newSource;
}
// Driver Code
int main()
{
Node *n0 = new Node(0);
Node *n1 = new Node(1);
Node *n2 = new Node(2);
Node *n3 = new Node(3);
Node *n4 = new Node(4);
n0->adj.push_back(n1);
n0->adj.push_back(n2);
n1->adj.push_back(n2);
n1->adj.push_back(n3);
n1->adj.push_back(n4);
n2->adj.push_back(n3);
n3->adj.push_back(n4);
// Flag to check if a node is already visited.
// Stops indefinite looping during recursion
vector<bool> visited(5, false);
cout << "Graph Before Cloning:-\n";
printGraph(n0, visited);
visited = { false, false, false, false, false };
cout << "\nGraph Before Starts:-\n";
Node *clonedGraphHead = cloneGraph(
n0, new Node(n0->key), visited);
cout << "Cloning Process Completes.\n";
visited = { false, false, false, false, false };
cout << "\nGraph After Cloning:-\n";
printGraph(clonedGraphHead, visited);
return 0;
}
// This code is contributed by sanjeev2552