My BFS solution Using Java


  • 0
    F

    public class Solution {
    public UndirectedGraphNode cloneGraph(UndirectedGraphNode node) {
    if (node == null) {
    return null;
    }
    //collect the node using BFS
    ArrayList<UndirectedGraphNode> list = bfs(node);

        //copy all the label
        Map<UndirectedGraphNode, UndirectedGraphNode> map = new HashMap<> ();
        for (UndirectedGraphNode graphNode : list) {
            map.put(graphNode, new UndirectedGraphNode(graphNode.label));
        }
        
        //copy the relationship
        for (UndirectedGraphNode graphNode : list) {
            List<UndirectedGraphNode> neightbours = graphNode.neighbors;
            UndirectedGraphNode copyNode = map.get(graphNode);
            List<UndirectedGraphNode> copyNeighbours = new ArrayList<> ();
            for (UndirectedGraphNode neighbour: graphNode.neighbors) {
                copyNeighbours.add(map.get(neighbour));
            }
            copyNode.neighbors = copyNeighbours;
        }
        
        
        
        return map.get(node);
    }
    
    public ArrayList<UndirectedGraphNode> bfs(UndirectedGraphNode node) {
        ArrayList<UndirectedGraphNode> list = new ArrayList<UndirectedGraphNode> ();
        Queue<UndirectedGraphNode> queue = new LinkedList<> ();
        HashSet<UndirectedGraphNode> set = new HashSet<> ();
        
        queue.offer(node);
        set.add(node);
        while (!queue.isEmpty()) {
            UndirectedGraphNode graphNode = queue.poll();
            list.add(graphNode);
            List<UndirectedGraphNode> neighbours = graphNode.neighbors;
            for (UndirectedGraphNode neighbour: neighbours) {
                if (set.contains(neighbour)) {
                    continue;
                }
                queue.offer(neighbour);
                set.add(neighbour);
            }
        }
        return list;
    }
    

    }


Log in to reply
 

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.