使用BFS克隆圖（無向）

Question

我寫了一個簡單的算法來克隆一個無向圖使用BFS，但似乎有一些邏輯錯誤，我不明白。有人可以看看嗎？

這個想法是訪問每個節點，並複製它們只有一次，複製一個節點後，檢查其鄰居是否沒有複製，排隊該鄰居;如果其鄰居已被複制，則將它們放入彼此的鄰居向量中。

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

這裏的節點結構：

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

這裏的OJ我與練習：https://leetcode.com/problems/clone-graph/

Answer 1

所有你必須單獨處理NULL節點情況下首先因爲在你的代碼，你會return m[NULL]如果輸入圖形是NULL可能導致runtime error。

看看下面的代碼我已評論我在哪裏添加和刪除了代碼，以及爲什麼我添加並刪除了代碼。

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. 這是沒有必要的，如果節點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 
----------------------------------------------------------------------------------------------------