133. Clone Graph.html

<html>
<head>
  <title>133. Clone Graph</title>
  <basefont face="Tahoma" size="2" />
  <meta http-equiv="Content-Type" content="text/html;charset=utf-8" />
  <meta name="exporter-version" content="Evernote Windows/304720 (en-US, DDL); Windows/10.0.14393 (Win64);"/>
  <style>
    body, td {
      font-family: Tahoma;
      font-size: 12pt;
    }
  </style>
</head>
<body>
<a name="7420"/>
<h1>133. Clone Graph</h1>
<div>
<table bgcolor="#D4DDE5" border="0">
<tr><td><b>Created:</b></td><td><i>7/28/2016 10:37 AM</i></td></tr>
<tr><td><b>Updated:</b></td><td><i>3/15/2017 9:10 PM</i></td></tr>
<tr><td><b>Tags:</b></td><td><i>#, breadth first search, depth first search, Graph, leetcode tag, Medium</i></td></tr>
</table>
</div>
<br/>

<div>
<span><div><a href="https://leetcode.com/problems/clone-graph/">https://leetcode.com/problems/clone-graph/</a></div><div><br/></div><div>思路：</div><div><br/></div><div style="box-sizing: border-box; padding: 8px; font-family: Monaco, Menlo, Consolas, 'Courier New', monospace; color: rgb(51, 51, 51); border-top-left-radius: 4px; border-top-right-radius: 4px; border-bottom-right-radius: 4px; border-bottom-left-radius: 4px; background-color: rgb(251, 250, 248); border: 1px solid rgba(0, 0, 0, 0.148438);"><div>/**</div><div> * Definition for undirected graph.</div><div> * class UndirectedGraphNode {</div><div> *     int <span style="color: rgb(255, 0, 0);">label</span>;</div><div> *     List&lt;UndirectedGraphNode&gt; <span style="color: rgb(255, 0, 0);">neighbors</span>;</div><div> *     UndirectedGraphNode(int x) { label = x; neighbors = new ArrayList&lt;UndirectedGraphNode&gt;(); }</div><div> * };</div><div> */</div></div><div><br/></div><div>DFS</div><div style="box-sizing: border-box; padding: 8px; font-family: Monaco, Menlo, Consolas, 'Courier New', monospace; color: rgb(51, 51, 51); border-top-left-radius: 4px; border-top-right-radius: 4px; border-bottom-right-radius: 4px; border-bottom-left-radius: 4px; background-color: rgb(251, 250, 248); border: 1px solid rgba(0, 0, 0, 0.148438);"><div>public <span style="color: rgb(255, 0, 0);">HashMap</span>&lt;Integer, UndirectedGraphNode&gt; <span style="color: rgb(255, 0, 0);">map</span> = new HashMap();<br/>
public UndirectedGraphNode <span style="background-color: rgb(255, 250, 165);-evernote-highlight:true;">cloneGraph</span>(UndirectedGraphNode node) {<br/>
    if (node == null) return null;<br/>
    if (map.<span style="color: rgb(255, 0, 0);">containsKey</span>(node.label))<br/>
        return map.get(node.label);<br/>
    UndirectedGraphNode cloned = new UndirectedGraphNode(node.label);</div><div>    map.put(cloned.label, cloned);</div><div><br/></div><div>    for(UndirectedGraphNode neighbor: node.neighbors){<br/>
        cloned.neighbors.<b>add</b>(<span style="background-color: rgb(255, 250, 165);-evernote-highlight:true;">cloneGraph(neighbor)</span>);<br/>
    }<br/>
    return cloned;<br/>
}</div></div><div><br/></div><div><br/></div><div>BFS</div><div style="box-sizing: border-box; padding: 8px; font-family: Monaco, Menlo, Consolas, 'Courier New', monospace; color: rgb(51, 51, 51); border-top-left-radius: 4px; border-top-right-radius: 4px; border-bottom-right-radius: 4px; border-bottom-left-radius: 4px; background-color: rgb(251, 250, 248); border: 1px solid rgba(0, 0, 0, 0.148438);"><div>public class Solution {<br/>
    public UndirectedGraphNode cloneGraph(UndirectedGraphNode node) {<br/>
        if (node == null) return null;<br/>
       <br/>
        UndirectedGraphNode newNode = new UndirectedGraphNode(node.label); //new node for return<br/>
        HashMap&lt;Integer, UndirectedGraphNode&gt; map = new HashMap(); //store visited nodes<br/>
       <br/>
        map.put(newNode.label, newNode); //add first node to HashMap<br/>
       <br/>
        LinkedList&lt;UndirectedGraphNode&gt; <b>queue</b> = new <b>LinkedList</b>(); //to store **original** nodes need to be visited<br/>
        queue.add(node); //add first **original** node to queue<br/>
       <br/>
        <b>while</b> (!queue.isEmpty()) { //if more nodes need to be visited<br/>
            UndirectedGraphNode n = <b>queue.pop();</b> //search first node in the queue<br/>
            <b>for</b> (UndirectedGraphNode neighbor : n.neighbors) {<br/>
                if (!map.containsKey(neighbor.label)) { //add to map and queue if this node hasn't been searched before<br/>
                    map.put(neighbor.label, new UndirectedGraphNode(neighbor.label));<br/>
                    queue.add(neighbor);<br/>
                }<br/>
                <b>map.get(n.label).neighbors.add(map.get(neighbor.label))</b>; //add neighbor to new created nodes<br/>
            }<br/>
        }<br/>
       <br/>
        return newNode;<br/>
    }<br/>
}</div></div><div><br/></div></span>
</div></body></html>