克隆无向图[bfs访问每条边而不止节点]

前言

BFS作为图操作的基础之一，对于无向图，可以利用hash来防止一个节点多次遍历，导致死循环。但是如果BFS需要访问每条边，而不止节点，那么一个节点可能会被访问多次，单纯的hash记录不能放在一个节点多次进入队列。

一、克隆无向图

二、BFS访问每条边

package everyday.hash;

import java.util.*;

public class CloneGraph {
    
    // bfs
    public Node cloneGraph(Node node) {
    
        if (null == node) return null;
        Node root = new Node(node.val);
        // 防止无向图来回访问。
        Set<Node> visited = new HashSet<>();
        // 防止已经加入队列的节点，再次因为其他连接边，再次加入队列。（每个节点的度不止1）
        Set<Node> queSet = new HashSet<>();
        // 把已经clone的节点记录起来，防止无法拿到已经new出来的节点。
        Map<Integer, Node> cloneNodes = new HashMap<>();

        Queue<Node> que = new LinkedList<>();
        Queue<Node> newQue = new LinkedList<>();
        que.offer(node);
        newQue.offer(root);

        queSet.add(node);
        cloneNodes.put(root.val, root);

        while (!que.isEmpty()) {
    
            // 取当前队首节点。
            Node cur = que.poll();
            Node newCur = newQue.poll();
            // 该节点设置为已访问过，防止无向图循环访问。
            visited.add(cur);

            for (Node nei : cur.neighbors) {
    
                // 访问过的，就已经把节点和边都搞好了，就不用再做其他事了。
                if (!visited.contains(nei)) {
    
                    // 如果节点还没创立，就new出新的节点。
                    if (!cloneNodes.containsKey(nei.val)) {
    
                        Node next = new Node(nei.val);
                        cloneNodes.put(next.val, next);
                    }
                    Node next = cloneNodes.get(nei.val);
                    // 不能重复加入队列。
                    if (!queSet.contains(nei)) {
    
                        que.offer(nei);
                        newQue.offer(next);
                        queSet.add(nei);
                    }
                    // 无向图，设置双向边。
                    newCur.neighbors.add(next);
                    next.neighbors.add(newCur);
                }
            }
        }
        return root;
    }

    // Definition for a Node.
    class Node {
    
        public int val;
        public List<Node> neighbors;

        public Node() {
    
            val = 0;
            neighbors = new ArrayList<Node>();
        }

        public Node(int _val) {
    
            val = _val;
            neighbors = new ArrayList<Node>();
        }

        public Node(int _val, ArrayList<Node> _neighbors) {
    
            val = _val;
            neighbors = _neighbors;
        }
    }
}

总结

1）BFS访问每条边，双hash防止死循环的同时，防止由多边访问同一节点，从而导致同一节点多次加入队列。

参考文献

[1] LeetCode 克隆无向图