专栏首页TheOneGIS空间站Leetcode: Clone Graph

Leetcode: Clone Graph

Clone an undirected graph. Each node in the graph contains a label and a list of its neighbors.

OJ’s undirected graph serialization: Nodes are labeled uniquely.

We use # as a separator for each node, and , as a separator for node label and each neighbor of the node. As an example, consider the serialized graph {0,1,2#1,2#2,2}.

The graph has a total of three nodes, and therefore contains three parts as separated by #.

First node is labeled as 0. Connect node 0 to both nodes 1 and 2. Second node is labeled as 1. Connect node 1 to node 2. Third node is labeled as 2. Connect node 2 to node 2 (itself), thus forming a self-cycle. Visually, the graph looks like the following:

   1
  / \
 /   \
0 --- 2
     / \
     \_/

题目要求克隆图,采用深度优先或者广度优先进行遍历。使用一个Map存储原始节点和克隆以后的节点。

参考代码(使用深度优先遍历):

/**
 * Definition for undirected graph.
 * struct UndirectedGraphNode {
 *     int label;
 *     vector<UndirectedGraphNode*> neighbors;
 *     UndirectedGraphNode(int x) : label(x) {};
 * };
 */
class Solution 
{
public:
    UndirectedGraphNode* cloneGraph(UndirectedGraphNode* node) 
    {
        if (node == nullptr)    return nullptr;

        // map的key为原始节点,value为拷贝的节点
        unordered_map<UndirectedGraphNode*, UndirectedGraphNode*> copyMap;
        // 完成给定节点的图的拷贝工作
        clone(node, copyMap);

        return copyMap[node];
    }
private:
    static UndirectedGraphNode* clone(UndirectedGraphNode* node, unordered_map<UndirectedGraphNode*, UndirectedGraphNode*> &copyMap)
    {
        // 如果该节点已经拷贝过,直接返回该节点的拷贝
        if (copyMap.find(node) != copyMap.end())  return copyMap[node];

        // 否则,拷贝该节点及其相邻节点
        UndirectedGraphNode* copiedNode = new UndirectedGraphNode(node->label);
        copyMap[node] = copiedNode;
        for (auto neighborNode : node->neighbors)
            copiedNode->neighbors.push_back(clone(neighborNode, copyMap));

        return copiedNode;
    }
};

本文参与腾讯云自媒体分享计划,欢迎正在阅读的你也加入,一起分享。

我来说两句

0 条评论
登录 后参与评论

相关文章

  • DOM4J使用过程中的一个细节问题:节点的选择

    Node的selectNodes或者selectSingleNode方法,或者XPath的selectNodes或者selectSingleNode方法。

    TheOneGIS
  • 二叉树的遍历以及遇到的一些问题

    这里以二叉树的前序遍历为例。输入前序遍历的数据元素(以空格作为空元素),构造二叉树,然后遍历二叉树输出每个数据元素所在的层。

    TheOneGIS
  • Leetcode: Binary Tree Right Side View

    Given a binary tree, imagine yourself standing on the right side of it, return t...

    TheOneGIS
  • BinarySearchTree二叉搜索树

    二叉树具有唯一的根节点 二叉树每个节点最多有两个孩子 二叉树每个节点最多有一个父亲节点,根节点是唯一没有父亲节点的。 二叉树具有天然递归结构。 每个节点...

    羊羽shine
  • ElasticSearch(7.2.2)-es分布式⼯作原理

    cwl_java
  • 二叉搜索树的这些你都会了吗?

    在计算机科学中,树(英语:tree)是一种抽象数据类型(ADT)或是实作这种抽象数据类型的数据结构,用来模拟具有树状结构性质的数据集合。它是由n(n>0)个有限...

    beifengtz
  • openshift/origin工作记录(5)——node节点系统资源预留

    解决思路为设置node节点系统资源预留值。

    胡了了
  • openshift/origin工作记录(5)——node节点系统资源预留

    实际应用中发现,如果不做处理,当集群内应用数量不断增加时,会占满node节点的系统资源,导致某node节点挂掉,同时也会造成openshift集群的卡死。

    胡了了
  • 深入理解AbstractQueuedSynchronizer

    JUC中的许多并发工具类ReentrantLock,CountDownLatch等的实现都依赖AbstractQueuedSynchronizer

    Java识堂
  • ElasticSearch(7.2.2)- es集群的基本核心概念

    cwl_java

扫码关注云+社区

领取腾讯云代金券