133. Clone Graph - my practice in July 2018

June 22, 2019

Introduction

It is my personal opinion. I was afraid to write down the thinking process when I practiced last time back in July 2018. I understand that it is important to show how I approach a problem, why it is better to choose BFS instead of DFS, what is challenge problem to solve to clone a node.

My sharing

Here is my post to share written on June 22, 2019.

It is challenge to master a graph algorithm. I like to review my last practice back in July 2018; I think that I should spend some time to work on a case study on example graph, and then explain how it works based on breadth first search.

Here are highlights:

1. Apply breadth first search in original graph;
2. Build a hashmap to map any node in original graph and clone graph;
3. To visit any neighbor node, if it is the first time to visit, then the node should be added to hashmap first, and also it should be added to queue to visit its neighbors in next level of BFS; otherwise update clone graph node and its neighbor node connection.

Case study example graph

June 22, 2019
I think that it is important for me to work on an example, and then write down every step if I have time, and then I can review the basics how to clone a node with neighbors using BFS.

The nodes 1 has two neighbors, node 2 and 4.
I like to explain how to clone the graph with node 1 with two neighbor nodes 2 and 4.

First visit node 1, and then create a new node for clone graph, assign value of node 1; And also add entry in hashmap to make node 1 and clone of node 1.
Go over all neighbors of node 1, node 2 and node 4; first visit node 2, and see if
hashmap has an entry for node 2 or not.

If there is no entry in hashmap for node 2, so create a new node in clone graph, copy the value of node 2, and then add map from node 2 to clone node of node 2; and also add clone neighbor relationship, and last, it is most important to visit neighbor by adding neighbor node to the queue.

The hashmap is also to serve visited look up, if the node is visited, then it should have an entry in hashmap.

If the neighbor node is visited, all we need to do is to add one more neighbor relationship.

Do not forget, search all nodes in the graph; always mark visit, avoid deadloop; Do not forget to clone neighbor relationship in clone graph as well.

The best way to review the graph algorithm is to draw a diagram to illustrate the steps in the clone process. I did quickly draw a diagram, which will be enhanced later.

/**
 * Definition for undirected graph.
 * public class UndirectedGraphNode {
 *     public int label;
 *     public IList<UndirectedGraphNode> neighbors;
 *     public UndirectedGraphNode(int x) { label = x; neighbors = new List<UndirectedGraphNode>(); }
 * };
 */
public class Solution {
    public UndirectedGraphNode CloneGraph(UndirectedGraphNode node)
        {
            if (node == null)
            {
                return null;
            }

            var queue = new Queue<UndirectedGraphNode>();
            var map   = new Dictionary<UndirectedGraphNode, UndirectedGraphNode>();

            var newHead = new UndirectedGraphNode(node.label);

            queue.Enqueue(node);
            map.Add(node, newHead);

            while (queue.Count > 0)
            {
                var curr = (UndirectedGraphNode)queue.Dequeue();

                var currNeighbors = curr.neighbors;

                foreach (UndirectedGraphNode neighbor in currNeighbors)
                {
                    if (!map.ContainsKey(neighbor))
                    {
                        var copy = new UndirectedGraphNode(neighbor.label);

                        map.Add(neighbor, copy);

                        map[curr].neighbors.Add(copy);

                        queue.Enqueue(neighbor);
                    }
                    else
                    {
                        map[curr].neighbors.Add(map[neighbor]);
                    }
                }
            }

            return newHead;
        }
}