Commitea25239

committed

clone graph using BFS

1 parentfdcbeeb commitea25239Copy full SHA for ea25239

File tree

+44

-0

lines changed

+44

-0

lines changed

Lines changed: 12 additions & 0 deletions

Original file line number	Diff line number	Diff line change
`@@ -0,0 +1,12 @@`
	`1`	`+packageclasses;`
	`2`	`+`
	`3`	`+importjava.util.*;`
	`4`	`+`
	`5`	`+/**`
	`6`	`+ * Created by fishercoder1534 on 9/30/16.`
	`7`	`+ */`
	`8`	`+publicclassUndirectedGraphNode {`
	`9`	`+publicintlabel;`
	`10`	`+publicList<UndirectedGraphNode>neighbors;`
	`11`	`+publicUndirectedGraphNode(intx) {label =x;neighbors =newArrayList<UndirectedGraphNode>(); }`
	`12`	`+}`

Lines changed: 32 additions & 0 deletions

Original file line number	Diff line number	Diff line change
`@@ -0,0 +1,32 @@`
	`1`	`+packagemedium;`
	`2`	`+`
	`3`	`+importclasses.UndirectedGraphNode;`
	`4`	`+importjava.util.*;`
	`5`	`+`
	`6`	`+/**`
	`7`	`+ * Created by fishercoder1534 on 9/30/16.`
	`8`	`+ */`
	`9`	`+publicclassCloneGraph {`
	`10`	`+`
	`11`	`+publicUndirectedGraphNodecloneGraph(UndirectedGraphNodenode) {`
	`12`	`+if(node ==null)returnnode;`
	`13`	`+`
	`14`	`+Map<Integer,UndirectedGraphNode>map =newHashMap();`
	`15`	`+Queue<UndirectedGraphNode>queue =newLinkedList();`
	`16`	`+UndirectedGraphNoderoot =newUndirectedGraphNode(node.label);`
	`17`	`+map.put(root.label,root);`
	`18`	`+queue.offer(node);//remember to offer the original input node into the queue which contains all the information`
	`19`	`+while(!queue.isEmpty()){`
	`20`	`+UndirectedGraphNodecurr =queue.poll();`
	`21`	`+for(UndirectedGraphNodeeachNode :curr.neighbors){`
	`22`	`+if(!map.containsKey(eachNode.label)){`
	`23`	`+map.put(eachNode.label,newUndirectedGraphNode(eachNode.label));`
	`24`	`+queue.offer(eachNode);`
	`25`	`+ }`
	`26`	`+map.get(curr.label).neighbors.add(map.get(eachNode.label));`
	`27`	`+ }`
	`28`	`+ }`
	`29`	`+returnroot;`
	`30`	`+ }`
	`31`	`+`
	`32`	`+}`

Comments

(0)