-
Notifications
You must be signed in to change notification settings - Fork 13
/
Graph_CloneConnectedUndirectedGraph.java
138 lines (110 loc) · 4.91 KB
/
Graph_CloneConnectedUndirectedGraph.java
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
134
135
136
137
138
import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.*;
// https://leetcode.com/problems/clone-graph/
// https://www.geeksforgeeks.org/clone-an-undirected-graph/ (Good tutorial)
// https://github.com/bephrem1/backtobackswe/blob/master/Graphs/CloneAGraph/CloneAGraph.java
// https://www.youtube.com/watch?v=vma9tCQUXk8 (BEST Video explanation)
public class Graph_CloneConnectedUndirectedGraph {
/* below code is simple BFS only*/
private static GraphNode getClonedGraph(GraphNode startingNode) {
if (startingNode == null) return null; /* If the start node is null then we cannot do any cloning */
Map<GraphNode, GraphNode> vertexMap = new HashMap<>(); /* vertexMap maps the original node reference to its clone */
Queue<GraphNode> queue = new LinkedList<>(); /* queue for Breadth First Search */
vertexMap .put(startingNode, new GraphNode(startingNode.value));
queue.add(startingNode); /* Add the start node to the queue. Give the start node a clone in the vertexMap */
/*
* The breadth first search continues until we have processed all vertices in
* the original graph. We know this is done when the queue is empty
*/
while (!queue.isEmpty()) {
GraphNode currNode = queue.poll(); /* We grab a node. We will express all of the edges coming off of this node. */
for (GraphNode neighbour : currNode.neighbours) { /* Iterate over all adjacent neighbours */
/* Has this neighbor been given a clone? */
if (!vertexMap .containsKey(neighbour)) {
/*
* No? Give it a mapping and add the original neighbor to the search queue so we
* can express its edges later
*/
vertexMap .put(neighbour, new GraphNode(neighbour.value));
queue.add(neighbour);
}
/*
* Draw the edge from currVertex's clone to neighbor's clone. Do you see how our
* hashtable makes this quick access possible
*/
vertexMap .get(currNode).neighbours.add(vertexMap .get(neighbour));
}
}
return vertexMap.get(startingNode); /* Return the clone of the start. This is the entry point for the cloned graph section.*/
}
public static void main(String[] args) throws IOException {
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
int t = Integer.parseInt(br.readLine().trim());
while (t-- > 0) {
GraphNode actualStartingNode = buildGraph();
System.out.println("BFS traversal of a graph before cloning");
bfs(actualStartingNode);
GraphNode clonedStartingNode = getClonedGraph(actualStartingNode);
System.out.println("BFS traversal of a graph after cloning");
bfs(clonedStartingNode);
}
}
private static void bfs(GraphNode startingNode) {
Queue<GraphNode> queue = new LinkedList<>();
Map<GraphNode, Boolean> visited = new HashMap<>();
queue.add(startingNode);
visited.put(startingNode, true);
while (!queue.isEmpty()) {
GraphNode currNode = queue.poll();
System.out.println("Value of the Node : " + currNode.value);
System.out.println("Address of the Node : " + currNode);
for(GraphNode neighbour : currNode.neighbours) {
if (visited.get(neighbour) == null) {
queue.add(neighbour);
visited.put(neighbour, true);
}
}
}
System.out.println();
}
private static GraphNode buildGraph() {
/*
Note : All the edges are Undirected
Given Graph:
1--2
| |
4--3
*/
GraphNode node1 = new GraphNode(1);
GraphNode node2 = new GraphNode(2);
GraphNode node3 = new GraphNode(3);
GraphNode node4 = new GraphNode(4);
List<GraphNode> neighbours = new ArrayList<>();
neighbours.add(node2);
neighbours.add(node4);
node1.neighbours = neighbours;
neighbours = new ArrayList<>();
neighbours.add(node1);
neighbours.add(node3);
node2.neighbours = neighbours;
neighbours = new ArrayList<>();
neighbours.add(node2);
neighbours.add(node4);
node3.neighbours = neighbours;
neighbours = new ArrayList<>();
neighbours.add(node1);
neighbours.add(node3);
node4.neighbours = neighbours;
return node1;
}
static class GraphNode {
private int value;
private List<GraphNode> neighbours;
GraphNode(int value) {
this.value = value;
this.neighbours = new ArrayList<>();
}
}
}