Cloner un Graphe non recté [bfs accède à chaque bord et pas seulement aux noeuds]

Préface

BFSComme l'une des bases de l'opération graphique,Pour les graphiques non rectés,Peut être utiliséhashPour empêcher un noeud de traverser plus d'une fois,Provoque un cycle mort.Mais siBFSBesoin d'accéder à chaque côté,Et pas seulement les noeuds,Un noeud peut alors être consulté plusieurs fois,SimplehashLes enregistrements ne peuvent pas être mis dans la file d'attente plus d'une fois sur un noeud.

Un.、Cloner un Graphe non recté

2.、BFSAccès à chaque bord

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);
        // Empêcher les graphiques non rectilignes d'aller et venir.
        Set<Node> visited = new HashSet<>();
        //  Empêcher les noeuds qui ont rejoint la file d'attente , Encore une fois, à cause des autres bords de connexion , Rejoignez la file d'attente .（ Chaque noeud a plus que 1）
        Set<Node> queSet = new HashSet<>();
        // - Oui.clone Les noeuds de , Empêcher l'impossibilité d'obtenir déjà newLes noeuds qui sortent.
        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()) {
    
            //  Prendre le noeud de tête de file d'attente actuel .
            Node cur = que.poll();
            Node newCur = newQue.poll();
            //  Ce noeud est défini pour avoir accès à , Empêcher l'accès circulaire au graphique non recté .
            visited.add(cur);

            for (Node nei : cur.neighbors) {
    
                // Visited, J'ai fait les noeuds et les bords , Plus besoin de faire autre chose .
                if (!visited.contains(nei)) {
    
                    //  Si le noeud n'a pas été créé ,Justenew Nouveau noeud .
                    if (!cloneNodes.containsKey(nei.val)) {
    
                        Node next = new Node(nei.val);
                        cloneNodes.put(next.val, next);
                    }
                    Node next = cloneNodes.get(nei.val);
                    //  Impossible de rejoindre la file d'attente à plusieurs reprises .
                    if (!queSet.contains(nei)) {
    
                        que.offer(nei);
                        newQue.offer(next);
                        queSet.add(nei);
                    }
                    // Graphique non recté, Définir les bords bidirectionnels .
                    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;
        }
    }
}

Résumé

1）BFSAccès à chaque bord,Doublehash Tout en empêchant la circulation morte , Empêcher l'accès multilatéral au même noeud , Cela fait que le même noeud se joint à la file d'attente plus d'une fois .

Références

[1] LeetCode Cloner un Graphe non recté