How to clone an undirected graph in Python

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.

An undirected graph

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 $G$ can be defined as a pair $(V, E)$ , where $V$ is a set of vertices and $E$ is a set of edges. Each edge in $E$ is represented as an unordered pair $(u, v)$ , where $u$ and $v$ are vertices in $V$ .

Understanding cloning

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.

Cloning process

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.

General approach to cloning

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:
1. Create a corresponding node in the clone graph.
2. Add edges to the cloned node for each neighbor encountered.
Return the clone graph.

Code example

A simple undirected graph is shown below:

from collections import deque
class Node:
    def __init__(self, val = 0, neighbors = None):
        self.val = val
        self.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 copies
    node_map = {}
    queue = deque([node])
    # Clone the starting node
    cloned_node = Node(node.val)
    node_map[node] = cloned_node
    
    while queue:
        curr_node = queue.popleft()
        for neighbor in curr_node.neighbors:
            if neighbor not in node_map:
                # Clone the neighbor node
                cloned_neighbor = Node(neighbor.val)
                node_map[neighbor] = cloned_neighbor
                queue.append(neighbor)
            # Add the clone of neighbor to the cloned node's neighbors list
            node_map[curr_node].neighbors.append(node_map[neighbor])
    
    return node_map[node]
# Example usage:
# Create a graph
node1 = 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 graph
cloned_node = cloneGraph(node1)
# Function to print the graph
def 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)

Code explanation

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