BFSを使ってグラフを複製する（無向）

Question

私は、BFSを使って無向グラフを複製する簡単なアルゴリズムを書いたが、私は理解できないいくつかの論理が間違っているようだ。ある人は見てもらえますか？

考えてみましょう。各ノードを訪問し、それらを1度だけコピーします。ノードをコピーした後、その隣人がコピーされていないかどうかを確認し、隣人をエンキューします。その隣人がすでにコピーされている場合は、それらを隣人の隣のベクトルに入れます。ここで

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]; 
} 

は、ノード構造体です：あなたは、あなたがするので、あなたのコードで別々にNULLノードケースを処理する必要がすべてのhttps://leetcode.com/problems/clone-graph/

Answer 1

まず：

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

は、ここに私が練習してるOJですの入力グラフがNULLの場合はreturn m[NULL]となります。

以下のコードを参照してください。コードを追加して削除した場所と、コードを追加して削除した理由についてコメントしました。

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; 
} 

編集： - あなたのプログラムが間違っている

---

： -

1. 自己サイクルのためにあなたが間違った出力を取得します。あなたがノードへのリンクを作り直すことによって、自転車を2回作ります。

2. ノードAが隣人Bを持っているならば、Bも隣人としてノードAを持っている必要はありません。しかし、すべてのノードに対して、あなたはそれを隣人に押し付けているだけでなく、隣人の隣にもノードを押し込んでいます。これは間違っています。

3. ノードが処理されていない場合は、現在のノードと未処理ノードの間にリンクを作成しないでキューに入れるだけです。詳細については

はあなたのコードの実行を参照してください -

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 
----------------------------------------------------------------------------------------------------