首页 > 试题广场 >

复制无向图

[编程题]复制无向图
  • 热度指数:17791 时间限制:C/C++ 1秒,其他语言2秒 空间限制:C/C++ 32M,其他语言64M
  • 算法知识视频讲解
本题要求复制一个无向图,图中每个节点都包含一个标签和它的邻居列表
我们无向图用以下的方法序列化:
  • 节点的标签是互不相同的,
  • 我们使用“#”作为节点之间的分隔符,使用“,”作为节点标签和节点的节点邻居的分隔符。
例如:现在有一个序列化的无向图{0,1,2#1,2#2,2}.
这个无向图一共有3个节点,因此序列被#分隔成三部分
  1. 第一个节点的标签是0,节点0和节点1,节点2之间有边
  2. 第二个节点的标签是1,节点1和节点2之间有边
  3. 第三个节点的标签是2,节点2和节点2(它自己)之间有边,形成了自环
这个无向图如下图所示



说明:本题目包含复杂数据结构UndirectedGraphNode,点此查看相关信息
头像 0x0offer的菜鸡
发表于 2019-08-24 13:05:52
分步进行 (1)首先通过DFS深度优先遍历,复制节点,使用一个map来保存原来节点A和复制节点A' 即map[A]=A' (2)通过遍历map中的key值,找到原图中节点的所有邻居节点,将该邻居节点对应的复制节点添加到key值对应的复制节点的邻居节点即可 另外注意这个题很好通过,因 展开全文
头像 ButterFlyEffect
发表于 2020-11-08 18:11:13
深度遍历,由于是图。所以我们需要用一个map维持clone过的节点,以及对应的新节点。遇到的时候直接赋值,避免再次陷入clone流程中。递归最简单。 /** * Definition for undirected graph. * struct UndirectedGraphNode { * 展开全文
头像 华科不平凡
发表于 2020-09-23 17:45:57
首先,这是个图的问题,二话不说,咱先搬出BFS和DFS两大法宝。 基本思路是:创建一个unordered_map,其中保存指向旧节点的指针到指向新节点的指针的映射,同时也用它来判断旧节点是否被遍历过。 BFS代码如下: // // Created by jt on 2020/9/23. // #in 展开全文
头像 Thanksfornowcoder
发表于 2020-07-18 17:33:52
本题要求复制一个无向图,图中每个节点都包含一个标签和它的邻居列表。首先分析题意: 我上来就没读懂要干嘛,看各位好汉一顿BFS,DFS轰炸,彻底懵了。首先,复制无向图,不是简单地复制指针的指向,而是要创建全部节点,并按照原先的关系进行新图关系的组织。但是有个问题是:新节点的数量就那么多个,而ne 展开全文