Clone ein Diagramm mit BFS (ungerichtet)

Question

Ich schrieb einen einfachen Algorithmus, um eine ungerichtete Grafik mit BFS zu klonen, aber es scheint etwas Logik falsch, dass ich nicht herausfinden kann. Kann jemand einen Blick darauf werfen?

Die Idee ist, jeden Knoten zu besuchen und sie nur einmal zu kopieren, nach dem Kopieren eines Knotens, überprüfen, ob sein Nachbar nicht kopiert wird, reihen Sie diesen Nachbarn ein; Wenn sein Nachbar bereits kopiert ist, lege sie in den Nachbarvektor des anderen.

UndirectedGraphNode *cloneGraph(UndirectedGraphNode *node) { 
    //key -> old node, value -> the new copy 
    unordered_map<UndirectedGraphNode*, UndirectedGraphNode*> m; 
    //the queue always contains old nodes that haven't been copied 
    queue<UndirectedGraphNode*> q; 
    if(node) 
     q.push(node); 

    while(!q.empty()) { 

     UndirectedGraphNode* n = q.front(); 
     q.pop(); 
     if(m.count(n)) continue; // if the node is already copied, continue 

     // create the copy 
     m[n] = new UndirectedGraphNode(n->label); 

     // loop through the neighbors, if it's copied already, add the new copy to new copy's neighbor list 
     for(UndirectedGraphNode* oldNei : n->neighbors) { 

      if(m.count(oldNei)) { 
       UndirectedGraphNode* newNei = m[oldNei]; 
       m[n]->neighbors.push_back(newNei); 
       newNei->neighbors.push_back(m[n]); 
      } 

      else// if not in the map, it's not copied/visited yet 

       q.push(oldNei); 
     } 

    } 

    return m[node]; 
} 

Hier ist der Knoten Struktur:

/** 
* Definition for undirected graph. 
* struct UndirectedGraphNode { 
*  int label; 
*  vector<UndirectedGraphNode *> neighbors; 
*  UndirectedGraphNode(int x) : label(x) {}; 
* }; 
*/ 

Hier ist der OJ Ich übe mit: https://leetcode.com/problems/clone-graph/

Answer 1

allererst Sie NULL Knoten Fall getrennt, weil in Ihrem Code, den Sie zu handhaben haben , wenn das Eingabegraph NULL ist, was verursachen kann.

Schauen Sie sich unten Code Ich habe kommentiert, wo ich den Code hinzugefügt und gelöscht habe und warum ich den Code hinzugefügt und gelöscht habe.

UndirectedGraphNode *cloneGraph(UndirectedGraphNode *node) { 
    // ++ if node is null just return null. 
    if(node == NULL) return NULL; 

    unordered_map<UndirectedGraphNode*, UndirectedGraphNode*> m; 
    queue<UndirectedGraphNode*> q; 
    // -- if(node) no need to check this as we have checked it above 
    q.push(node); 

    // ++ as first input will not have copy so no need to check it in map 
    // just create a copy and associate it with original node in map. 
    UndirectedGraphNode *graphCopy = new UndirectedGraphNode(node->label); 
    m[node] = graphCopy; 

    while(!q.empty()) { 
     UndirectedGraphNode* n = q.front(); 
     q.pop(); 
     // -- if(m.count(n)) continue; :- no need to check this condition as we will 
     // only push non copied node in queue. 

     // -- m[n] = new UndirectedGraphNode(n->label); :- we will create it inside loop 

     // loop through the neighbors, if it's copied already, add the new copy to new copy's neighbor list 
     for(UndirectedGraphNode* oldNei : n->neighbors) { 
      // if node is processed/ copied earlier then just push it in neighbour of current node 
      if(m.count(oldNei)) { 
       UndirectedGraphNode* newNei = m[oldNei]; 
       m[n]->neighbors.push_back(newNei); 
       // -- newNei->neighbors.push_back(m[n]); no need of making back connection as 
       // this node has already processed and contains all it neighbour 
      } 

      else {// if not in the map, it's not copied/visited yet then create new copy of node here 
        //and push it into queue 
       UndirectedGraphNode *p = new UndirectedGraphNode(oldNei->label); // ++ make a copy of node 
       m[n]->neighbors.push_back(p); // ++ push it to current node neighbour 
       m[oldNei] = p; // ++ associate copied node with its original one 
       q.push(oldNei); // push that node to queue 
      } 
     } 
    } 
    return graphCopy; 
} 

Edit: -

---

Wo Ihr Programm falsch ist: -

1. Für Selbst Zyklus werden Sie falsch ausgegeben bekommen. Während du dich selbst wiederholst, wiederhole die Verbindung zum Knoten.

2. Es ist nicht notwendig, dass, wenn der Knoten A ist Nachbar mit B dann B auch Knoten A als Nachbarn haben. Aber für jeden Knoten schiebst du den Nachbar einfach, aber schiebst auch Knoten in den Nachbarn, was falsch ist.

3. Wenn Knoten nicht verarbeitet werden, schieben Sie sie einfach in die Warteschlange, ohne eine Verbindung zwischen dem aktuellen Knoten und dem nicht verarbeiteten Knoten herzustellen.

Für weitere Details siehe die Ausführung des Codes: -

Let's take same graph as of problem: 
First node is labeled as 1. Connect node 1 to both nodes 2 and 3. 
Second node is labeled as 2. Connect node 2 to node 3. 
Third node is labeled as 3. Connect node 3 to node 3 (itself), thus forming a self-cycle. 

So original graph will have neighbor like this: 
Neighbor 1 -> 2 , 3 
Neighbor 2 -> 3 
Neighbor 3 -> 3 

     1 
    /\ 
    / \ 
    2 --- 3 
     /\ 
     \_/ 

Now starting executing your code: 
assume 1 as root node 

first it will insert 1 in Queue 
Q -> [ 1 ] 

inside While Loop :- 
---------------------------------------------------------------------------------------------------- 
First Iteration:- 
n = 1 
Pop : Q -> empty // 1 is poped out so queue is empty now 

here node 1 is not in map so you will create a copy of node 1 and save it in map 
Map -> (1 , 1C) 

Check for neighbour of 1 -> which is 2 & 3 

inside for loop both node 2 & 3 is not processed so you will push it in Queue so Queue will became:- 

Q -> [2, 3] 
---------------------------------------------------------------------------------------------------- 

Second Iteration:- 
n = 2 
Pop : Q -> [ 3 ] 

Node 2 is not in map- 
Create copy of node 2 and push it in map 

Map -> (1, 1C) , (2, 2C) 

Check for neighbour of 2 -> which is 3 

node 3 is not processed till now so push it in Queue 

Q -> [3, 3] 

---------------------------------------------------------------------------------------------------- 

Third Tteration:- 

n = 3 
Pop : Q -> [ 3 ] 

node 3 is not in map so- 
Create copy of node 3 and push it in map 

Map -> (1, 1C) , (2, 2C) , (3, 3C) 

Check for neighbour of 3 -> which is 3 

Node 3 is also in map so you will create a link between node 3C & 3C which is correct but you will do it twice as you are pushing back node also so in this step you will do as follows 

Neighbour 3C -> 3C 
Neighbour 3C -> 3C 

So over all it will look like 

Neighbour 1C -> 
Neighbour 2C -> 
Neighbour 3C -> 3C, 3C 

This is your final result and it different from original 
----------------------------------------------------------------------------------------------------