有没有办法在有向图中找到一个节点的所有传入边？
在有向图中找到一个节点的所有传入边的方法有两种常见的实现方式：
- 邻接表：在邻接表表示的有向图中，每个节点都维护一个列表，列表中存储了指向该节点的所有边的起始节点。通过遍历整个图的邻接表，可以找到指向目标节点的所有传入边。这种方法的时间复杂度为O(V+E)，其中V为节点数，E为边数。
- 邻接矩阵：在邻接矩阵表示的有向图中，使用一个二维矩阵来表示节点之间的边的关系。矩阵中的每个元素表示从一个节点到另一个节点的边的存在与否。通过遍历整个矩阵的列，可以找到指向目标节点的所有传入边。这种方法的时间复杂度为O(V^2)，其中V为节点数。
以下是腾讯云相关产品和产品介绍链接地址：
- 腾讯云云服务器（CVM）：提供弹性计算能力，满足各类业务需求。详情请参考：https://cloud.tencent.com/product/cvm
- 腾讯云云数据库MySQL版：提供高性能、可扩展的MySQL数据库服务。详情请参考：https://cloud.tencent.com/product/cdb_mysql
- 腾讯云对象存储（COS）：提供安全、稳定、低成本的云端存储服务。详情请参考：https://cloud.tencent.com/product/cos
- 腾讯云人工智能（AI）：提供丰富的人工智能服务和解决方案，包括图像识别、语音识别、自然语言处理等。详情请参考：https://cloud.tencent.com/product/ai
相关·内容
1回答
获取邻接表/矩阵中所有节点的所有邻居的复杂度
arrays、algorithm、time-complexity、graph-theory
如果我想得到图中一个节点的所有邻居，如果图存储在邻接矩阵中，时间复杂度是O(|V|)，如果图保存在邻接表中，时间复杂度也是O(|V|)。现在我在想，如果我不想获得一个节点的邻居而是所有节点的邻居，这种情况会发生什么变化。(注意:邻接表包含一个数组和链表。在每个数组条目处存储一个链表，其中每个数组条目代表一个节点。链表中的每个节点代表一个相邻节点。)
我的想法是这样的：
在邻接矩阵中，我需要查看每一个条目。因此，我的时间复杂度为O(|V|^2)。在邻接表中，我需要查看每个数组条目并遍历它们各自的链表。我在想，这应该在O(|E|)中完成，因为我基本上只看所有的边。
我的想法正确吗？
浏览 25提问于2017-07-25得票数 0
2回答
如何在C++中生成曲面的邻接矩阵
c++、graphics、3d、sparse-matrix、mesh
我正在研究Graphite。它位于C++的内置库中。
我正在试着做一个球体的表面。球体为网格形式。
如何构造曲面的邻接矩阵和次数矩阵，以便计算拉普拉斯矩阵？
我正在处理一个曲面，稍后我需要对其进行变形，因为我需要曲面的邻接矩阵和次数矩阵。
我正在使用C++。提前谢谢。
浏览 1提问于2018-10-17得票数 0
2回答
以节省内存的方式将加权边列表转换为邻接矩阵
python、adjacency-matrix
使用Python，如何以节省内存的方式将加权边列表转换为对称邻接矩阵？
例如，考虑以下包含4个节点和3个边的加权边列表：
A B 1
A C 2
C D 3
则输出邻接矩阵如下：
0 1 2 0
1 0 0 0
2 0 0 3
0 0 3 0
我希望以一种节省内存的方式来做到这一点-- 100000 x 100000邻接矩阵(10**10值)。请注意，矩阵是对称的，并且所有对角线的值都是0。
浏览 7提问于2021-10-24得票数 0
1回答
如果图不是邻接矩阵，如何找到节点的所有邻域？
c、graph-theory、breadth-first-search
我尝试过用C语言实现google BFS，但它们似乎都期望图形以邻接矩阵的形式出现，据我所理解，它能够在短时间内找到所有相邻的节点。
但是，如果输入是以一对节点的形式进行的，我应该做什么来找出相邻的节点呢？
当我每次寻找邻居的时候，我应该存储边缘并循环遍历它们吗？但这听起来很慢，就像像我这样的傻瓜会做的那样：
还是我应该把输入转换成邻接矩阵？
输入示例
{
Nodes:
0
1
2
3
Edges:
0 2
1 3
2 3
0 1
}
Pseducode
BFS (G, s) //Whe
浏览 1提问于2018-09-04得票数 1
回答已采纳
2回答
如何在只使用邻接表的无向图中找到存在的圈(以及顶点编号)？
c++、algorithm、graph-theory、adjacency-matrix、graph-traversal
如果你只有一个邻接矩阵，你如何找到圈在无向图中的位置？
浏览 15提问于2019-07-12得票数 1
2回答
弗洛伊德·沃希尔使用邻接表
java、floyd-warshall
是否可以使用邻接表对Floyd Warshall进行编码？我必须处理文本文件中的一百万个顶点，因此，邻接矩阵不是一个解决方案。有没有已经可用的实现？请帮帮忙。
浏览 3提问于2014-11-29得票数 3
1回答
图中DFS和BFS的空间复杂度
depth-first-search、breadth-first-search、space-complexity
我试图理解DFS和BFS在图中的空间复杂性是什么。我理解，当使用邻接矩阵时，BFS的空间复杂度为O(v^2)，其中v是顶点数。
使用邻接表可以降低平均情况下的空间复杂度，即< v^2。但在最坏的情况下，它将是O(v^2)。即使包括队列，也会是O(n^2) (忽略较低的值)。
但是，DFS的场景是什么呢？即使我们使用邻接矩阵/列表。空间复杂性为O(v^2)。但这似乎是一个非常松散的界限，这也没有考虑堆栈框架。
关于复杂的问题，我说得对吗？如果不是，BFS/DFS的空间复杂性是什么？在计算DFS的空间复杂度时，我们是否考虑堆栈框架？
对于BFS和DFS对于图，空间复杂度的紧界是什么？
浏览 1提问于2019-03-19得票数 1
回答已采纳
3回答
根据图的表示，BFS的时间复杂度是多少？
data-structures、graph、graph-algorithm、breadth-first-search
我想知道BFS的时间复杂性是什么，如果我使用：
邻接矩阵
邻接表
边表
它们的空间复杂性是一样的吗？
浏览 6提问于2013-10-23得票数 15
1回答
如何使用python从G(n，p)图创建邻接矩阵？
python、machine-learning、adjacency-matrix、graphml、graph-modelling-language
我要求从一个随机图创建一个邻接矩阵。我真的不知道怎么做，我知道的唯一的方法是通过图和顶点建立邻接矩阵。
def adjacency_matrix(n,p) n是顶点的数量，p是在两个顶点之间有一条边的概率。
浏览 2提问于2019-12-15得票数 0
4回答
利用腾讯云GPU构建深度学习网络？
对象存储、深度学习
如题，本人（学生）想用腾讯云构建一个实验性的深度学习网络，具体要用到腾讯云的哪些服务呢？（GPU，COS），另外还需考虑较低的成本。。。
浏览 1112提问于2017-12-13
3回答
优先级队列Prims算法的复杂性？
java、algorithm、minimum-spanning-tree、prims-algorithm
我用的是邻接矩阵，优先级队列是数据结构。
根据我的计算，复杂性是V^3 log V
While循环：V
检查相邻顶点：V
如果条目已经存在，检查队列，并更新相同的：V log v
但是，我到处读到复杂性是V^2
请解释一下。
浏览 4提问于2012-11-25得票数 8
回答已采纳
1回答
在无向图中寻找欧拉圈
graph-theory、depth-first-search
Hierholzer的算法帮助我们在O(m+n)时间内找到图中的欧拉回路，但它使用的邻接矩阵占用O(n^2)空间。谁能给出一个O(m+n)时间算法，它使用图的邻接表表示来进行深度优先搜索遍历，占用O(m+n)空间？这里m表示图中的边数，n表示图中的顶点数。
浏览 1提问于2018-06-17得票数 0
4回答
对象和指针图表示
data-structures、graph
我到处都看到有三种表示图的方法：
对象和指针
邻接矩阵
邻接表
然而，我不明白这些对象和指针表示是什么--然而每个招聘人员都知道，许多博客引用了博客，它们确实是一个单独的表示形式。
对于一个非常类似的问题，似乎认为顶点结构本身没有指向其他顶点的内部指针，而是用包含指向相邻顶点的指针的边结构来表示。
在任何情况下，这种表示如何提供任何明显的分析优势？
浏览 11提问于2015-01-07得票数 14
4回答
图的数据结构
data-structures、hashtable、graph-theory
我目前正在写硕士论文。是关于图表的。我的算法准备好了。但是现在我必须考虑有用的数据结构来表示图形，以及我需要一个良好的运行时所需的其余部分。由于内存量大，我不允许使用邻接矩阵。因为我必须检查每一次迭代是否存在某一条边，所以邻接列表也没有任何意义。
首先，我想到了两个相互嵌套的哈希表。所有节点存储在第一表中，所有相邻节点存储在第二表中。但是，由于我必须能够在算法中选择一个随机邻居，这也不是最优的。此外，我还必须能够在算法的每一次迭代中保存边缘权重。
包含所有基本操作的列表：
我需要一个边缘的表示，如果存在某种边缘，我可以在其中签入O (1)。
我必须能够选择O(1)中固定节点的随机邻居。
浏览 6提问于2021-08-21得票数 2
回答已采纳
9回答
对于C++中的图问题，邻接表和邻接矩阵哪个更好？
c++、graph、adjacency-list、adjacency-matrix
对于C++中的图问题，邻接表和邻接矩阵哪个更好？每种方法的优缺点是什么？
浏览 0提问于2010-02-08得票数 145
3回答
基于邻接表的图的度数计算
algorithm、graph、asymptotic-complexity
我遇到了这个问题，在这个问题中，需要根据邻接表表示来计算图中每个节点的入度数。
for each u
for each Adj[i] where i!=u
if (i,u) ∈ E
in-degree[u]+=1
现在，根据我的说法，它的时间复杂度应该是O(|V||E|+|V|^2)，但我提到的解决方案将其描述为等于O(|V||E|)。
请帮帮忙，告诉我哪一个是对的。
浏览 0提问于2014-04-08得票数 5
2回答
用于图数据结构的最坏情况存储器
algorithm、data-structures、graph
我可以在许多书中看到，图的最坏情况内存要求是O(V)。但是，如果我没有记错的话，图通常表示为邻接矩阵，而不是通过创建节点(如链表/树)来表示。因此，对于一个包含5个顶点的图，我需要5x5矩阵，它是O(V^2)。他们为什么把它说成O(V)？
我是不是漏掉了什么？如果这个问题太天真，我很抱歉。
浏览 1提问于2013-06-22得票数 1
回答已采纳
8回答
邻接矩阵中的循环检测
matlab、graph、matrix、graph-algorithm
设A是图G = (V,E)的邻接矩阵。A(i,j) = 1如果节点i和j与边缘连接，则为A(i,j) = 0。
我的目标是理解G是否是无环的。循环的定义如下：
i和j连接：A(i,j) = 1
j和k连接：A(j,k) = 1
k和i连接：A(k,i) = 1
我已经实现了一个解决方案，其导航矩阵如下：
从边缘(i,j)开始
选择从O发出的边缘的集合j，即A的j-th行中的所有1s。
以DFS方式导航O
如果从此导航生成的路径之一导致节点i，则检测到一个循环。
显然，这个解非常慢，因为我必须评估矩阵中的所有路径。如果A非常大，所需的开销非常大。我想知
浏览 11提问于2013-05-08得票数 17
回答已采纳
5回答
稀疏图和密集图的区别是什么？
data-structures、graph、graph-theory
我读到用邻接表表示稀疏图，用邻接矩阵表示稠密图是很理想的。但我想要了解稀疏和密集图之间的主要区别。
浏览 1提问于2012-09-26得票数 49
回答已采纳
1回答
关于图的边矩阵的c++实现
c++、graph、graph-theory
我搞不懂如何定义一个程序来寻找图中的边矩阵。问题是，如果一个人输入邻接矩阵的值，它给出了图中顶点连接的信息，例如:有3个顶点，然后V1连接到V2但不使用V3，然后V2连接到V3，它给出：
0 1 0
1 0 1
0 1 0
现在，有了这些信息，我想编写一个找到边到边的连接的程序，例如有3条边: 1-2边，2-3边，它的输出是：
0 1
1%0
我知道要使第一个输出“邻接矩阵”，但第二个。提前谢谢。
浏览 0提问于2014-03-23得票数 0
扫码
添加站长 进交流群
领取专属 10元无门槛券
手把手带您无忧上云
相关资讯
热门标签
云服务器
即时通信 IM
ICP备案
对象存储
实时音视频活动推荐
腾讯云开发者
