首页
学习
活动
专区
工具
TVP
发布
精选内容/技术社群/优惠产品,尽在小程序
立即前往

Leetcode No.133 克隆图(DFS)

一、题目描述 给你无 连通 图中一个节点引用,请你返回该图 深拷贝(克隆)。 图中每个节点都包含它值 val(int) 和其邻居列表(list[Node])。...该图在测试用例中使用邻接列表表示。 邻接列表 是用于表示有限图无序列表集合。每个列表都描述了图中节点邻居集。 给定节点将始终是图中第一个节点(值为 1)。...节点 4 值是 4,它有两个邻居:节点 1 和 3 。 示例 2: 输入:adjList = [[]] 输出:[[]] 解释:输入包含一个空列表。...该图仅仅只有一个值为 1 节点,它没有任何邻居。 示例 3: 输入:adjList = [] 输出:[] 解释:这个图是空,它不含任何节点。...递归调用每个节点邻接点。每个节点递归调用次数等于邻接数量,每一次调用返回其对应邻接克隆节点,最终返回这些克隆邻接列表,将其放入对应克隆节点邻接表中。

29620

☆打卡算法☆LeetCode 133. 克隆图 算法解析

一、题目 1、算法题目 “给定一个无连通图中一个节点引用,返回该图深拷贝。” 题目链接: 来源:力扣(LeetCode) 链接: 133....图中每个节点都包含它值 val(int) 和其邻居列表(list[Node])。...该图在测试用例中使用邻接列表表示。 邻接列表 是用于表示有限图无序列表集合。每个列表都描述了图中节点邻居集。 给定节点将始终是图中第一个节点(值为 1)。...节点 4 值是 4,它有两个邻居:节点 1 和 3 。 示例 2: 输入: adjList = [[]] 输出: [[]] 解释: 输入包含一个空列表。...递归调用每个节点邻接点,每次节点递归调用次数等于邻接数量,最终返回这些克隆邻接列表,将其放入对应克隆节点邻接表中。

30820
您找到你想要的搜索结果了吗?
是的
没有找到

克隆图

你无 连通 图中一个节点引用,请你返回该图 深拷贝(克隆)。 图中每个节点都包含它值 val(int) 和其邻居列表(list[Node])。...该图在测试用例中使用邻接列表表示。 邻接列表 是用于表示有限图无序列表集合。每个列表都描述了图中节点邻居集。 给定节点将始终是图中第一个节点(值为 1)。...节点 4 值是 4,它有两个邻居:节点 1 和 3 。 示例 2: 输入:adjList = [[]] 输出:[[]] 解释:输入包含一个空列表。...每个节点值 Node.val 都是唯一,1 <= Node.val <= 100。 无图是一个简单图,这意味着图中没有重复边,也没有自环。...由于图是无,如果节点 p 是节点 q 邻居,那么节点 q 也必须是节点 p 邻居。 图是连通图,你可以从给定节点访问到所有节点。

1.1K30

一天一大 lee(克隆图)难度:中等-Day20200812

题目: 给你无 连通 图中一个节点引用,请你返回该图 深拷贝(克隆)。 图中每个节点都包含它值 val(int) 和其邻居列表(list[Node])。...该图在测试用例中使用邻接列表表示。 邻接列表 是用于表示有限图无序列表集合。每个列表都描述了图中节点邻居集。 给定节点将始终是图中第一个节点(值为 1)。...节点 4 值是 4,它有两个邻居:节点 1 和 3 。 示例 2 输入:adjList = [[]] 输出:[[]] 解释:输入包含一个空列表。该图仅仅只有一个值为 1 节点,它没有任何邻居。...每个节点值 Node.val 都是唯一,1 <= Node.val <= 100。 无图是一个简单图,这意味着图中没有重复边,也没有自环。...由于图是无,如果节点 p 是节点 q 邻居,那么节点 q 也必须是节点 p 邻居。 图是连通图,你可以从给定节点访问到所有节点。 抛砖引玉 ?

32620

刚学会深拷贝一个对象,学妹却问我怎么深拷贝一个图

既然搞懂了深浅拷贝以及其区别,我们再看看图,图一般用来表示节点和节点之间关系,常分为有图和无图,在这里我们以无图(一旦连接即双向)为主题。...邻接表表示一个图 问题分析 如果这个图使用邻接表表示,给你无 连通 图中一个节点引用,请你返回该图 深拷贝(克隆),这个问题是力扣131克隆图原题。...图中每个节点都包含它值 val(int) 和其邻居列表(list[Node])。...图片来源力扣 给一个节点引用,怎么克隆这个图呢? 如果只有这一个节点,那么克隆这个节点就好。如果这个节点只有一层邻居,那克隆这个邻居列表(克隆List集合)即可。...这里最好方法是使用HashMap,其中key保存是被克隆图中节点,而value是在克隆图中所对应节点,这样在克隆新图过程中,我们遍历被克隆图中节点邻居时候,就可以用哈希判断这个节点对应

39620

【GCN】图卷积网络入门(一)

状态,该状态对邻域信息进行编码。状态嵌入 ? 用于产生输出 ? ,例如预测节点标签分布。原始GNN模型处理无齐次图,其中图中每个节点都有其输入特征 ? ,每条边也可能都有其特征。...边和邻居集合。 为了根据输入邻域更新节点状态,定义一个在所有节点之间共享参数函数 ? ,称为局部转移函数。为了产生节点输出,有一个参数函数 ? ,称为局部输出函数。然后, ?...分别表示节点特征、节点连接特征、节点邻居隐藏状态和节点邻居特征。 如果将所有的状态、输出、特征和节点特征分别堆叠起来并使用矩阵表示为: ? ,那么上面的公式可以改写为: ?...在这一步中,该算法旨在给接受域中节点一个顺序,以便从无序图空间映射到矢量空间。这是最重要步骤,它背后想法是为不同图中两个具有相似的结构地位节点分配相似的相对位置。 卷积结构。...是训练数据下标的集合, ? 是真实标签。 ? 计算为: ? 其中 ? 表示 ? 经过softmax输出。因此, ? 是衡量两个卷积输出距离无监督损失函数。

1.8K40

揉捻Map-疯狂Java

弱连 通图是在将有图中方向忽略后形成连通图。 生成树(Spanning Tree):生成树是一个无环连通子图,包含了原图中所有节 点,并且通过最少边连接这些节点。...插入和删除边操作比较耗时,时间复杂度为O(1)。 邻接表(Adjacency List): 邻接表是一种链表数组形式,用于表示图中每个节点邻接节点。...其他表示方法: 邻接集合(Adjacency Set):使用集合来表示每个节点与其邻居节点之间连 接关系。...邻接字典(Adjacency Dictionary):使用字典来表示每个节点与其邻居节点 之间连接关系。...邻接矩 阵适用于稠密图,邻接表适用于稀疏图,关联矩阵适用于多重图,而邻接集合邻接字典适用于特定操作和查询需求。 图存储和计算效率: 图存储和计算效率是处理大规模图关键因素。

16920

每周学点大数据 | No.15 图在计算机中存储

不仅如此,我们还希望这些边和点集合可以被更高效地发现,比如举出一个顶点,就可以很快地找到它邻居们。所以直接存储所有的边和顶点查询效率不够高,因此计算机工作者们选取了邻接矩阵和邻接表。...相应,如果有一条有边BA,它权值为4,我们就将G[1][0]填充为4。 ? 邻接矩阵例子 小可:那么如何表示无边呢? Mr. 王:在邻接矩阵表示中,一般不去区分有图和无图。...无表示方法和有图是一致,只不过在无图中,对于长度为3边AB,我们将G[1][0]和G[0][1]值都改为3即可。...王:所以邻接矩阵更加适合用来存储稠密图,图中边越多,浪费空间就越少。 小可:对于那些比较稀疏图,怎么办呢? Mr. 王:这就要使用另一种存储结构——邻接表。邻接表比较适合用于存储稀疏图。...邻接表是一个链表集合,链表所有的表头代表一个节点。比如前面的例子有A,B,C,D,E这5个节点,在这个集合中建立5个链表,分别代表这5个节点,然后将每个节点所有邻居作为元素插入到链表中。

1.2K70

原创 | 一文读懂图神经网络

基本概念 1.1 图基本概念 通常使用G=(V, E)来表示图,其中V表示节点集合、E表示边集合。对于两个相邻节点u, v, 使用e=(u,v)表示这两个节点之间边。...1)邻接矩阵(Adjacency Matrix) 用于表示图中节点之间关系,对于n个节点简单图,有邻接矩阵 : 2)度矩阵(Degree Matrix) 节点度(Degree)表示与该节点相连个数...为了得到节点输出o, 引入局部输出函数g。因此,有以下定义: 其中x表示节点投中, h表示节点隐状态,ne[n]表示表示节点n邻居节点集合,co[n]表示节点n邻接集合。...最终节点输出如下公式所示,很好理解,就是给邻居节点分配不同权重来聚合信息。...2.3 GraphSAGE -归纳式学习框架 提到GraphSAGE[7]模型, 不得不又提到GCN,我们回顾一下GCN迭代公式: 图中红框位置所做操作可以简单理解为对邻接矩阵A归一化变换,去掉该部分会发现剩下结构等同于深度神经网络

1.3K40

图机器学习无处不在! 用 Transformer 可缓解 GNN 限制

一个有类型节点或类型边图被称为异质图,举个例子,在引文网络项目可以是论文或作者,有类型节点,而 XML 图中关系有类型边;它不能仅仅通过其拓扑结构来表示,还需要额外信息 图也可以是有(例如追随者网络...表示图处理和操作常见方法有两种,一种是作为其所有边集合(可能由其所有节点集合补充),或是作为其所有节点之间邻接矩阵。...图注:Hugging Face 标志和被打乱 Hugging Face 标志,是完全不同新形象 但图情况并非如此:如果我们洗掉图边缘列表邻接矩阵列,它仍然是同一个图。...但是,它仍然会使整个图信息变得平滑和丢失——递归分层集合可能更有意义,或者增加一个虚拟节点,与图中所有其他节点相连,并将其表示作为整个图表示。...选择一个聚合:一些聚合技术(特别是平均/最大集合)在创建精细表示以区分类似节点不同节点邻居表示时,会遇到失败情况;例如,通过均值集合,一个有4个节点邻居表示为1、1、-1、-1,平均为0,与一个只有

1.1K20

图神经网络模型总结

在计算机科学中,图是由顶点和边两部分组成一种数据结构。图G可以通过顶点集合V和它包含边E来进行描述。 image.png 根据顶点之间是否存在方向依赖关系,边可以是有,也可以是无。...其中Φ^e应用于图中每条边更新,Φ应用于图中每个节点更新,Φ则用来更新图全局表示;ρ函数将输入表示集合整合为一个表示,该函数设计为 可以接收任意大小集合输入,通常可以为加和、平均值或者最大值等不限输入个数操作...,这种思想可以归结为一句话: 图中每个结点无时无刻不因为邻居和更远影响而在改变着自己状态直到最终平衡,关系越亲近邻居影响越大。...举个简单例子,对于下图中左图(为了简单起见,举了无图且边没有权重例子)而言,它度矩阵 D ,邻接矩阵A和拉普拉斯矩阵L, 分别如下图所示,度矩阵D只有对角线上有值,为对应节点度,其余为0;邻接矩阵...邻接矩阵A与特征H相乘,等价于,某节点邻居节点特征相加。这样多层隐含层叠加,能利用多层邻居信息。

2.1K11

图机器学习无处不在,用 Transformer 可缓解 GNN 限制

一个有类型节点或类型边图被称为异质图,举个例子,在引文网络项目可以是论文或作者,有类型节点,而 XML 图中关系有类型边;它不能仅仅通过其拓扑结构来表示,还需要额外信息 图也可以是有(例如追随者网络...表示图处理和操作常见方法有两种,一种是作为其所有边集合(可能由其所有节点集合补充),或是作为其所有节点之间邻接矩阵。...图注:Hugging Face 标志和被打乱 Hugging Face 标志,是完全不同新形象 但图情况并非如此:如果我们洗掉图边缘列表邻接矩阵列,它仍然是同一个图。...但是,它仍然会使整个图信息变得平滑和丢失——递归分层集合可能更有意义,或者增加一个虚拟节点,与图中所有其他节点相连,并将其表示作为整个图表示。...选择一个聚合:一些聚合技术(特别是平均/最大集合)在创建精细表示以区分类似节点不同节点邻居表示时,会遇到失败情况;例如,通过均值集合,一个有4个节点邻居表示为1、1、-1、-1,平均为0,与一个只有

57620

图论算法基础(修订版)

比如还是刚才那幅图: 用邻接表和邻接矩阵存储方式如下: 邻接表很直观,我把每个节点x邻居都存到一个列表里,然后把x和这个列表关联起来,这样就可以通过一个节点x找到它所有相邻节点。...比如说我想判断节点1是否和节点3相邻,我要去邻接表里1对应邻居列表里查找3是否存在。但对于邻接矩阵就简单了,只要看看matrix[1][3]就知道了,效率高。...很简单呀: 如果是邻接表,我们不仅仅存储某个节点x所有邻居节点,还存储x到每个邻居权重,不就实现加权有图了吗?...如果连接无图中节点x和y,把matrix[x][y]和matrix[y][x]都变成true不就行了;邻接表也是类似的操作,在x邻居列表里添加y,同时在y邻居列表里添加x。...,res中添加path时需要拷贝一个新列表,否则最终res中列表都是空

75720

基于networkx分析Louvain算法社团网络划分

(称为边)构成,V、E分别计G集合和边集合。...两者唯一区别在于,有图中边是有方向性。  图2:有图和无图  注:上图左边为无图,右边为有图。黑色加粗部分表示边方向。比如:1—>2便是边是1到2这个方向。 ...3图度 度是相对于图中概念,图中任意一点v度是指:与v相连条数。在有图中与顶点v出关联数目称为出度,与顶点v入关联数目称为入度。...2求图常用属性    读取CSV文件获取图集合列表 部分原始数据如图:    计算图各种属性整体图,看到所有人都是有联系,由于人物比较多,所以图显示不出具体效果。...算法步骤: 1)将图中每个节点看成一个独立社区,次数社区数目与节点个数相同;  2)对每个节点i,依次尝试把节点i分配到其每个邻居节点所在社区,计算分配前与分配后模块度变化ΔQ,并记录ΔQ最大那个邻居节点

3.4K30

关于图神经网络(Graph Neural Networks,GNN)基础知识汇总1.0

分类有/无图如果给图每条边规定一个方向,那么得到图称为有图。在有图中,与一个节点相关联边有出边和入边之分。相反边没有方向图为无图。...一个更内存友好表达稀疏矩阵连方法是邻接列表邻接列表第k项是一个元组(i,j),代表了节点n_i和n_ j之间边e_k。...具体地,给定一个节点i及其邻居节点集合N(i),图卷积层首先将节点i特征表示为Vi,然后将其与邻居节点特征进行聚合,得到更新后节点i特征表示V'i。...具体地,给定一个节点i及其邻居节点集合N(i),图注意力层首先将节点i特征表示为Vi,然后计算节点i与其邻居节点之间权重,得到更新后节点i特征表示V'i。...在展开图中,传播过程对应于从t到T更新过程(注意,T并不是确定,而是对应于整个图状态到达不动点时刻),不同时间步连接则由图中连接来决定(可以是有,也可以是无)。

4K52

数据结构高频面试题-图

算法思想: 从 DAG 图中选择一个 没有前驱(即入度为0)顶点并输出。 从图中删除该顶点和所有以它为起点边。 重复以上步骤,直到当前图中不存在无前驱顶点。...图中每个节点都包含它值 val(Int) 和其邻居neighbors列表(list[Node])。 提示:必须将给定节点拷贝作为对克隆图引用返回。...给定一个列表 times,表示信号经过有传递时间。 times[i] = (u, v, w),其中 u是源节点,v 是目标节点, w 是一个信号从源节点传递到目标节点时间。...给定数字 n 和一个无边 edges 列表(每一个边都是一对标签)。 你可以假设没有重复边会出现在 edges 中。...], [1,5]] 输出: [1,4] 解释: 给定图为: 5 - 1 - 2 | | 4 - 3 解题思路: 本题可以理解为:对每个边进行遍历,如果构成该边两个节点在图中已经连通,再添加边则必成环

2.1K20

图解Spark Graphx实现顶点关联邻接顶点collectNeighbors函数原理

图片 原创/朱季谦 一、场景案例 在一张社区网络里,可能需要查询出各个顶点邻接关联顶点集合,类似查询某个人关系比较近都有哪些人场景。...:2关联邻居顶点集合->{(1,Alice),(3,Charlie),(4,David)} 顶点:3关联邻居顶点集合->{(2,Bob),(4,David)} 顶点:4关联邻居顶点集合->{(2,...(9,Ivy)} 顶点:7关联邻居顶点集合->{(5,Eve),(8,Henry)} 结合文章开始那一个图验证一下,顶点1关联邻接顶点是(2,Bob),(5,Eve),正确;顶点8关联邻接顶点是...若本顶点为2,图里从顶点2指邻居顶点,将得到(1,4,5)。...ctx.dstId, ctx.dstAttr)当作消息传给源顶点A,A会将收到消息保存下来,这样就知道EdgeDirection.Either无边情况下,它有一个邻居B了。

621110

PGL图学习项目合集&数据集分享&技术归纳业务落地技巧

GCN输出固定: GCN输出是节点 唯一确定 embedding; GraphSAGE学习是节点和邻接节点之间关系,学习到是一种映射关系 ,节点embedding可以随着其邻接节点变化而变化...由于在图中节点邻居是 天然无序 ,所以我们希望构造出聚合函数是 对称 (即改变输入顺序,函数输出结果不变),同时具有 较强表达能力 (比如可以参数学习)。...对图中每个节点邻接节点进行 采样 ,输入节点及其n阶邻接节点特征向量 根据K层 聚合函数 聚合邻接节点信息 就产生了各节点embedding 16.minibatch子图是怎么得到...下图伪代码,就是在其前传播之前,多了个minibatch操作。 先对所有需要计算节点进行采样(算法2中2~7行)。用一个字典来保存节点及其对应邻接节点。...这个子图邻接列表和特征矩阵作为一个minibatch送入GPU训练,这样一来,convolve操作过程中就没有GPU与CPU通信需求了。

31520

图算法-LeetCode 133、207(拓扑排序,邻接表建立)

图中每个节点都包含它值 val(Int) 和其邻居列表(list[Node])。 ? 解释: 节点 1 值是 1,它有两个邻居:节点 2 和 4 。...无图是一个简单图,这意味着图中没有重复边,也没有自环。 由于图是无,如果节点 p 是节点 q 邻居,那么节点 q 也必须是节点 p 邻居。 必须将给定节点拷贝作为对克隆图引用返回。...这是不可能。 说明: 输入先决条件是由边缘列表表示图形,而不是邻接矩阵。详情请参见图表示法。 你可以假定输入先决条件中没有重复边。...一个很简单思路是使用拓扑排序算法,可以判断一个循环是否存在于一个有图中。...说明这个有图中没有循环,否则则有循环。

1.2K20

扫码

添加站长 进交流群

领取专属 10元无门槛券

手把手带您无忧上云

扫码加入开发者社群

相关资讯

热门标签

活动推荐

    运营活动

    活动名称
    广告关闭
    领券