程序師世界是廣大編程愛好者互助、分享、學習的平台,程序師世界有你更精彩!
首頁
編程語言
C語言|JAVA編程
Python編程
網頁編程
ASP編程|PHP編程
JSP編程
數據庫知識
MYSQL數據庫|SqlServer數據庫
Oracle數據庫|DB2數據庫
 程式師世界 >> 編程語言 >> C語言 >> C++ >> C++入門知識 >> Clone Graph [leetcode] dfs和bfs

Clone Graph [leetcode] dfs和bfs

編輯:C++入門知識

Clone Graph [leetcode] dfs和bfs


變量unordered_map cloneMap;

因為會有環,所以需要cloneMap記錄舊的節點和新的節點對。

還需要一個visited記錄已經訪問過的節點,可以和cloneMap合並在一起。


DFS:

在克隆某個Node時,首先放入map中。

之後遍歷neighbors。如果neighbors不在map裡,即沒有訪問過,則遞歸調用cloneGraph函數。

最後返回克隆過的節點。

    UndirectedGraphNode *cloneGraph(UndirectedGraphNode *node) {
        if (node == NULL) return NULL;
        if (cloneMap.find(node) != cloneMap.end()) 
            return cloneMap[node];
        cloneMap[node] = new UndirectedGraphNode(node->label);
        cloneMap[node]->neighbors = vector();
        for (int i = 0; i < node->neighbors.size(); i++)
        {
            UndirectedGraphNode * curNode = node->neighbors[i];
            UndirectedGraphNode * newNode = cloneGraph(curNode);
            cloneMap[node]->neighbors.push_back(newNode);
        }
        return cloneMap[node];
    }

BFS:

使用一個queue記錄要訪問的節點。

因為不能在訪問queue中節點的時候再創建對應的node==>因為在處理父親節點的時候需同時創建好其neighbors

所以需要在將不在map中的neighbors(沒有訪問過的子節點)放入queue的同時創建克隆的節點,並且放入map裡。

    UndirectedGraphNode *cloneGraph(UndirectedGraphNode *node) {
        if (node == NULL) return NULL;
        vector queue;
        queue.push_back(node);
        cloneMap[node] = new UndirectedGraphNode(node->label);
        cloneMap[node]->neighbors = vector();
        
        for (int i = 0; i < queue.size(); i++)
        {
            UndirectedGraphNode * newNode = cloneMap[queue[i]];
            for (int j = 0; j < queue[i]->neighbors.size(); j++)
            {
                UndirectedGraphNode * curNb = queue[i]->neighbors[j];
                if (cloneMap.find(curNb) == cloneMap.end())
                {
                    queue.push_back(curNb);
                    UndirectedGraphNode * newNb = new UndirectedGraphNode(curNb->label);
                    newNb->neighbors = vector();
                    cloneMap[curNb] = newNb;
                }
                newNode->neighbors.push_back(cloneMap[curNb]);
            }
        }
        return cloneMap[node];
    }


  1. 上一頁:
  2. 下一頁:
Copyright © 程式師世界 All Rights Reserved