Clone Graph

class Solution {
public:
    Node* cloneGraph(Node* node) {
        if (!node) {
            return nullptr;
        }
        // Using an unordered map to store cloned nodes
        unordered_map<Node*, Node*> cloneMap;
        // Initialize the BFS queue
        queue<Node*> q;
        q.push(node);
        // Creating the initial clone
        cloneMap[node] = new Node(node->val);
        while (!q.empty()) {
            Node* current = q.front();
            q.pop();
            // Go through each neighbor of the node
            for (Node* neighbor : current->neighbors) {
                if (cloneMap.find(neighbor) == cloneMap.end()) {
                    // If the neighbor is not cloned yet, clone it
                    cloneMap[neighbor] = new Node(neighbor->val);
                    q.push(neighbor);
                }
                // Attach the cloned neighbor to the cloned node's neighbors list
                cloneMap[current]->neighbors.push_back(cloneMap[neighbor]);
            }
        }
        // The node from cloneMap corresponding to the input node is returned
        return cloneMap[node];
    }
};

The provided C++ code implements a solution for cloning a graph. The method takes a graph node as input and returns a cloned copy of the entire graph including all nodes and their connections. Here is a step-by-step breakdown:

1. First, check if the input node is null; if so, return nullptr indicating no graph to clone.

2. Utilize an unordered map, cloneMap, to map original nodes to their clones, ensuring each node is cloned only once.

3. Set up a queue for Breadth-First Search (BFS) and initialize it with the input node.

4. Create a clone of the initial node and store this in the map.

5. Use a loop to process each node in the queue:

   • Remove the node from the front of the queue.
   • Iterate through all its neighbors.
   • For each neighbor that hasn’t yet been cloned:
     • Clone the neighbor and place it in the map.
     • Add the cloned neighbor to the corresponding neighbor list of the cloned node.
     • Push the unprocessed neighbor into the queue for future cloning.

6. Beyond the loop, fetch and return the cloned node that corresponds to the original input node from the cloneMap, to return the entire cloned graph structure.

This implementation ensures that all nodes and their respective connections are duplicated accurately. Since it employs BFS, every node and its immediate neighbors are processed level by level, ensuring a complete and correct graph structure in the cloned graph.

class Solution {
    public Node copyGraph(Node source) {
        if (source == null) return source;

        // Mapping of original nodes to their clones
        HashMap<Node, Node> mapping = new HashMap<>();

        // Queue for BFS
        LinkedList<Node> exploreQueue = new LinkedList<>();
        exploreQueue.add(source);

        // Initialize with the source node clone
        mapping.put(source, new Node(source.val, new ArrayList<>()));

        while (!exploreQueue.isEmpty()) {
            Node current = exploreQueue.poll();

            for (Node adjacent : current.neighbors) {
                if (!mapping.containsKey(adjacent)) {
                    mapping.put(adjacent, new Node(adjacent.val, new ArrayList<>()));
                    exploreQueue.add(adjacent);
                }
                mapping.get(current).neighbors.add(mapping.get(adjacent));
            }
        }

        return mapping.get(source);
    }
}

The given Java code defines a method to clone a graph using Breadth-First Search (BFS). The method, copyGraph, takes a graph node (source) and copies all its nodes and edges, returning the cloned graph.

• Start by checking if the input node is null. If it is, return null.
• Utilize a HashMap called mapping to store relationships between original nodes and their respective cloned versions.
• Use a LinkedList to function as the BFS queue to manage nodes as you explore them. Begin with the source node.
• Map the source node to its cloned version inside the HashMap. This clone includes initializing its value and an empty list for its neighbors.
• Process each node in the queue:
  • Retrieve and remove the head of the queue.
  • Iterate over its neighbors and:
    • If the neighbor hasn't been visited (not in mapping), clone it, add this clone to the map, and queue the original neighbor for further exploration.
    • Update the neighbors of the clone with clones of adjacent nodes.
• Finally, return the clone of the source node accessed from the HashMap.

This method ensures each node and its connections are accurately replicated in the cloned graph without duplicating any nodes, following BFS to systematically explore and clone entire graph components.

struct Node *copyGraph(struct Node *source) {
    if (!source) {
        return NULL;
    }
    struct Node *mapped[101] = {NULL};
    struct Node **buffer = calloc(101, sizeof(struct Node *));
    buffer[0] = source;
    int head = 0;
    int tail = 1;

    struct Node *copy = calloc(1, sizeof(struct Node));
    copy->val = source->val;
    copy->numNeighbors = source->numNeighbors;
    mapped[source->val] = copy;

    while (head != tail) {
        struct Node *current = buffer[head++];
        struct Node *copyCurrent = mapped[current->val];
        copyCurrent->neighbors = calloc(copyCurrent->numNeighbors, sizeof(struct Node *));
        
        for (int i = 0; i < copyCurrent->numNeighbors; i++) {
            struct Node *neighbor = current->neighbors[i];
            if (!mapped[neighbor->val]) {
                buffer[tail++] = neighbor;
                struct Node *copyNeighbor = calloc(1, sizeof(struct Node));
                copyNeighbor->val = neighbor->val;
                copyNeighbor->numNeighbors = neighbor->numNeighbors;
                copyCurrent->neighbors[i] = mapped[neighbor->val] = copyNeighbor;
            } else {
                copyCurrent->neighbors[i] = mapped[neighbor->val];
            }
        }
    }
    free(buffer);
    return mapped[source->val];
}

The provided C program implements a function to clone a graph represented by nodes using a breadth-first search (BFS) approach. Here's how the solution is structured and operates:

• Define a function copyGraph that takes a pointer to a source node of the graph.

• If the source node is NULL, return NULL to indicate there is no graph to copy.

• Use an array mapped to keep track of copied nodes, ensuring that each node is only copied once and helping to manage already visited nodes.

• Employ a buffer implemented as a queue (buffer) to manage nodes during the BFS traversal. This buffer holds pointers to nodes that need to be explored.

• Initialize the graph copying process by creating the first node (copy) which is a copy of the source node, setting its value and number of neighbors.

• Process each node in the graph using BFS:

  • For each node, check its neighbors.
  • If a neighbor hasn't been copied yet (is not in mapped), create a new copy, add it to the queue for further traversal, and link it appropriately.
  • If a neighbor has already been copied, retrieve the copy from mapped and set the appropriate links.

• Free the buffer once the BFS traversal is complete.

• Return the pointer to the copied source node (ensuring the entire graph connected to the source is cloned).

This function efficiently clones any given graph by ensuring each node and its corresponding connections are replicated accurately using BFS, maintaining the structure and attributes of the original graph.

var copyGraph = function (origNode) {
    if (origNode === null) return origNode;
    const mapping = new Map();
    const processQueue = [origNode];
    mapping.set(origNode, { val: origNode.val, neighbors: [] });

    while (processQueue.length > 0) {
        const currentNode = processQueue.shift();
        currentNode.neighbors.forEach((adjacent) => {
            if (!mapping.has(adjacent)) {
                mapping.set(adjacent, { val: adjacent.val, neighbors: [] });
                processQueue.push(adjacent);
            }
            mapping.get(currentNode).neighbors.push(mapping.get(adjacent));
        });
    }
    return mapping.get(origNode);
};

The given JavaScript function copyGraph is designed to clone a graph. Here’s how it works:

• Begin by checking if the original node (origNode) is null. If true, return null immediately.
• Use a Map object, named mapping, to keep track of the original nodes and their clones.
• Initiate a queue, processQueue, with the original starting node to process nodes layer by layer (breadth-first search).
• Loop through each element in the queue:
  • Remove the first node from the queue and process it.
  • For each of the current node’s neighbors, perform the following:
    • If the neighbor has not been visited (i.e., not in the mapping):
      • Create a new clone of this neighbor.
      • Add this cloned neighbor to the processQueue.
    • Add the clone of the neighbor to the cloned current node's neighbors regardless of whether it was newly created or created earlier.
• Once the loop finishes, return the cloned graph starting from the original input node's clone, which can be retrieved from mapping.

This function effectively creates a deep copy of a graph including all connections and nodes, ensuring each node is processed and appropriately linked in the new cloned structure.

"""
# Node class definition
class Node:
    def __init__(self, value=0, connections=None):
        self.value = value
        self.connections = connections if connections is not None else []
"""

from collections import deque


class Solution:

    def cloneGraph(self, node: Optional["Node"]) -> Optional["Node"]:

        if not node:
            return node

        # Holds original nodes as keys and their clones as values
        visited_nodes = {}

        # Initialize BFS with the start node
        bfs_queue = deque([node])
        # Create and record the first node clone
        visited_nodes[node] = Node(node.value, [])

        # Process the BFS queue
        while bfs_queue:
            # Dequeue an element
            current_node = bfs_queue.popleft()
            # Examine each adjacent node
            for neighbor in current_node.connections:
                if neighbor not in visited_nodes:
                    # Clone and visit the neighbor
                    visited_nodes[neighbor] = Node(neighbor.value, [])
                    # Enqueue the new node
                    bfs_queue.append(neighbor)
                # Link the cloned neighbor to the current node's clone
                visited_nodes[current_node].connections.append(visited_nodes[neighbor])

        # Return the cloned graph's start node
        return visited_nodes[node]

The code given solves the problem of cloning a graph using BFS (Breadth-First Search). Here's an overview of how the functionality achieves this:

• Node Class Declaration: A Node class is defined to structure each graph node, having attributes for value and a list of connections to other nodes.
• Graph Cloning: In the cloneGraph method:
  • Start by checking if the node is null which immediately returns the node itself, indicating no cloning is necessary for an empty graph.
  • Use a dictionary visited_nodes to map original nodes to their clones. This approach prevents cloning the same node multiple times and aids in reconstructing the graph structure.
  • Utilize a queue (implemented using deque from collections) for BFS, initiating it with the starting node of the graph.
  • In the BFS loop:
    • Dequeue the front node and iterate through its neighbors.
    • For each unvisited neighbor, create a clone, mark it as visited, and enqueue the neighbor for subsequent BFS exploration.
    • Append the cloned neighbors to the clone of the current node, preserving the graph structure.
  • The function returns a clone of the entire graph starting from the input node.

This solution efficiently reproduces the graph structure by ensuring each node is cloned once with all its respective connections, using BFS strategy to navigate through the graph.