133. Clone Graph - My first practice back in July 2016

Here is the discussion post I wrote today.

It is challenge to master the graph algorithm. What I do is to review all graph algorithms, and then review basics through my past practice.

Here are highlights of my practice back in July 2016.

1. Clone a graph is similar to clone a tree; The traverse of a graph can be depth first search or breadth first search, each node should be copied, and then connected node should be keeped in clone graph as well;
2. Design a hashmap to save the orginal node in graph with cloned graph; Start from any given node first;
3. Choose breadth first search, since adjacent list should be went through and then each neighbor node should be cloned as well.

June 22, 2019
I think that I should work on a few things back in 2016. I should write some comment, and also I should learn some advanced C# feature, like using implicit type var to declare queue to save time.

/**
 * 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;
 
            Queue<UndirectedGraphNode> queue = new Queue<UndirectedGraphNode>();
            Dictionary<UndirectedGraphNode, UndirectedGraphNode> map = 
                                   new Dictionary<UndirectedGraphNode,UndirectedGraphNode>();
 
            UndirectedGraphNode newHead = new UndirectedGraphNode(node.label);
 
            queue.Enqueue(node);
            map.Add(node, newHead);
 
            while(queue.Count > 0 ){
                UndirectedGraphNode curr = (UndirectedGraphNode)queue.Dequeue();                

                IList<UndirectedGraphNode> currNeighbors = curr.neighbors; 
 
                foreach (UndirectedGraphNode aNeighbor in currNeighbors){
                    if(!map.ContainsKey(aNeighbor)){
                        UndirectedGraphNode copy = new UndirectedGraphNode(aNeighbor.label);

                        map.Add(aNeighbor,copy);

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

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

            return newHead;
    }
}