Cloning an undirected graph is a fundamental task in computer science. It is particularly useful in scenarios like creating backups, simulating processes, or ensuring that modifications to a graph don’t affect the original structure.
A graph in which edges have no direction is called an undirected graph. These type of graphs contain bidirectional edges in between nodes or vertices.
In mathematics, an undirected graph
A clone of an undirected graph is an identical copy of the original graph. It has the same structure, with all vertices and edges preserved. However, the clone is a separate instance from the original graph, meaning any changes made to one graph will not affect the other.
To clone an undirected graph in Python, we can apply algorithms such as Depth-First Search (DFS) or Breadth-First Search (BFS) to systematically traverse the original graph and replicate its structure. During the traversal, we keep track of visited nodes to avoid infinite loops and ensure that each node and its edges are copied to the new graph.
Here's a general approach to clone an undirected graph:
Start with the original graph.
Initialize an empty clone graph.
Traverse the original graph using DFS or BFS.
For each node encountered during traversal:
Create a corresponding node in the clone graph.
Add edges to the cloned node for each neighbor encountered.
Return the clone graph.
A simple undirected graph is shown below:
Here’s an implementation of the above undirected graph using BFS:
from collections import dequeclass Node:def __init__(self, val = 0, neighbors = None):self.val = valself.neighbors = neighbors if neighbors is not None else []def cloneGraph(node):if not node:return None# Dictionary to store the mapping of original nodes to their copiesnode_map = {}queue = deque([node])# Clone the starting nodecloned_node = Node(node.val)node_map[node] = cloned_nodewhile queue:curr_node = queue.popleft()for neighbor in curr_node.neighbors:if neighbor not in node_map:# Clone the neighbor nodecloned_neighbor = Node(neighbor.val)node_map[neighbor] = cloned_neighborqueue.append(neighbor)# Add the clone of neighbor to the cloned node's neighbors listnode_map[curr_node].neighbors.append(node_map[neighbor])return node_map[node]# Example usage:# Create a graphnode1 = Node(1)node2 = Node(2)node3 = Node(3)node4 = Node(4)node1.neighbors = [node2, node4]node2.neighbors = [node1, node3]node3.neighbors = [node2, node4]node4.neighbors = [node1, node3]# Clone the graphcloned_node = cloneGraph(node1)# Function to print the graphdef printGraph(node):seen = set()queue = deque([node])while queue:curr_node = queue.popleft()if curr_node not in seen:seen.add(curr_node)print("Node:", curr_node.val)print("Neighbors:", [neighbor.val for neighbor in curr_node.neighbors])for neighbor in curr_node.neighbors:queue.append(neighbor)print("Original Graph:")printGraph(node1)print("\nCloned Graph:")printGraph(cloned_node)
In the code above:
Lines 3–6: The code defines a class Node
representing nodes in a graph, where each node has a value and a list of neighbors.
Lines 8–30: The method cloneGraph()
takes a node
from an input graph and clones the entire graph.
Lines 13-14: It initializes a dictionary node_map
to store the mapping of original nodes to their clones, and a queue for breadth-first search (BFS) traversal.
Lines 19–28: It iteratively performs BFS traversal starting from the input node
, cloning each node and its neighbors, and updating the node_map
accordingly. Each cloned node is stored in the node_map
with its corresponding original node as the key.
Line 30: The method returns the clone of the input node, which represents the cloned graph.
Lines 34–41: Four nodes are created to construct a graph structure. Each node is assigned a value and connected to specific neighboring nodes, forming a graph topology.
Line 44: The cloneGraph()
function is invoked with the starting node node1
, which clones the entire graph and returns the cloned node representing the copied graph.
Lines 47–63: A function printGraph()
is defined to print the nodes and their neighbors in the graph. Both the original graph and the cloned graph are printed separately using this function to visualize their structures.
Free Resources