确定两个节点之间是否有边的时间复杂度

文章/答案/技术大牛

发布

1回答

graph、time-complexity

我正在尝试计算一个算法的复杂度来解决这个问题：我试图得到的解决方案是在图上搜索第一个节点，然后搜索到另一个节点的邻接表。这个算法的大O时间复杂度是多少？

浏览 64提问于2021-05-18得票数 0

2回答

具有恒定时间复杂度的无向图边的数据结构

c++、performance、data-structures、graph

我有一个无向图，其中节点存储在一个平面数组中。现在我正在寻找边缘的数据结构。对于获取给定节点的所有边，它应该具有恒定的时间复杂度。边缘包含两个节点索引和附加信息(如权重)。我看到的唯一方法是复制数据，一个按左节点排序，另一个按右节点排序。但我想防止重复的边

浏览 0提问于2014-01-01得票数 0

回答已采纳

1回答

寻找单向有向图中是否存在路径的最佳方法

algorithm、graph

我有一个有大量节点的图，其中有一个开始节点(所有边都向外)和一个端节点(所有边缘都指向它)。对这类图中的搜索进行优化是一个单向的、无权的graph.How，以确定两个节点之间是否存在路径？是否存在优化搜索(比如添加一些附加信息)，因为我将经常在图表上进行搜索？编辑:要添加更多关于该图形的信息，该图形有一个具有

浏览 4提问于2014-01-15得票数 6

4回答

有比Dijkstra更快的算法吗？

graph-theory、dijkstra

给定一个只有正边权的有向连通图，是否有比使用fibonacci堆的Dijkstra更快的算法来寻找两个顶点之间的最短路径？我不是在寻找优化，例如，一半的执行时间，而是不同时间复杂度的算法(比如从O(n * log n)到O(n))。确定所有边缘权重的GCD。将图转换为

浏览 4提问于2009-11-09得票数 9

回答已采纳

1回答

递归和迭代方法在时间复杂度上有区别吗？

time-complexity

我知道在递归算法和迭代算法之间确实存在空间复杂度的差异。但是，它们之间的时间复杂度是否也存在差异？例如:如果我有一个递归地计算列表中节点数量的程序，然后我实现了与迭代相同的程序，那么我在时间复杂度上是否会有任何差异，即O(n)？谢谢

浏览 0提问于2011-11-01得票数 0

回答已采纳

2回答

在图中找到带BFS的路径

java、graph、path、breadth-first-search

我想用bfs在图中的两个节点之间找到一条路径。我编写了一个函数，它以正确的顺序访问所有节点(不确定它是否工作，但对我来说似乎是正确的)，但是我需要存储路径(包含形成路径的所有边的列表)，我不知道如何做到:\ 有人能帮我吗？(预先谢谢:)

浏览 3提问于2015-04-01得票数 0

回答已采纳

1回答

无向图的顶点和边的变化

c++、boost、graph-theory

每隔t秒，我需要检查它是否发生了变化(顶点\边删除\添加)。retVal = add_edge(1, 2, G); //

浏览 1提问于2015-04-27得票数 2

1回答

Prim算法的时间复杂度是如何使用优先级Q的ElogV？

algorithm、complexity-theory、big-o、prims-algorithm

我使用的伪代码： else visited[s]=1;根据我的理解第2行:所有顶点乘以…的度数之和。..that is 2E times 对于每一行2:第3行和第4行占用log E

浏览 1提问于2009-08-22得票数 4

回答已采纳

2回答

如何删除networkx中的节点？

python、graph-theory、networkx

我有一个数据集，我正在上传各种时间段的图表，并试图弄清楚它们之间的关系。我想删除所有没有边的节点，但我不确定删除或删除节点的命令。你知道怎么做吗？

浏览 2提问于2011-10-18得票数 6

回答已采纳

4回答

C++：大图的权值存储

c++、graph、shortest-path

我在解决一些关于图表的问题。它需要存储N个节点的权重(N<=50000)。我不能用矩阵来存储图的权重(因为50000x50000不能分配)。你知道其他方法吗？谢谢。

浏览 11提问于2016-01-28得票数 0

回答已采纳

3回答

关于无向图复杂性的DFS？

algorithm、graph、tree、time-complexity、depth-first-search

当我们使用DFS遍历无向连通图并标记出我们在DFS期间移动的边时，我们最终得到一个DFS树，它基本上是一棵树，遍历一棵树需要O(v)复杂性，其中v是顶点的数目，那么为什么它说复杂度是O(v + e)？

浏览 3提问于2020-08-20得票数 0

回答已采纳

2回答

BFS和DFS的运行时是否在二叉树O(N)上？

algorithm、binary-tree、time-complexity、depth-first-search、breadth-first-search

我意识到泛型图上的BFS和DFS的运行时间是O(n+m)，其中n是节点数，m是边数，这是因为对于每个节点，都必须考虑它的邻接表。然而，当BFS和DFS在二叉树上执行时，它的运行时是什么？我认为它应该是O(n)，因为可以离开节点的可能边的数量是恒定的(即，2)。请确认这是否是正确的理解。如果不是，请解释BFS和DFS在二叉树上的正确时间</

浏览 1提问于2013-11-11得票数 25

1回答

如何使用链表在图中找到最短路径？

algorithm、graph、linked-list、pseudocode

如果节点是直接连接的，就有n个节点，节点之间也有边。每个边没有重量和方向(如果节点a和b连接，它意味着双向连接，而不是单向连接)。基于该图，我们可以绘制出二维数组A.An-1的邻接矩阵.因此，问题是如何返回最短路径。如果没有路径，应该返回空路径。而路径应该使用链接列表返回。|A B C D EB|1 0 1 0 0 D|1 0 1 0 1因此，基于上面的矩阵，从C到E

浏览 2提问于2019-09-08得票数 0

回答已采纳

3回答

求二叉树直径的时间复杂度

algorithm、tree、binary-tree、time-complexity

我在这里看到过各种计算二叉树直径的帖子。一种这样的解决方案可以在中找到(查看接受的解决方案，而不是问题中突出显示的代码)。我搞不懂为什么代码的时间复杂度是O(n^2)。我不明白如何遍历一棵树的节点两次(一次是高度(通过getHeight())，一次是直径(通过getDiameter())，而不是n+n，它是2n。任何帮助都将不胜感激。

浏览 0提问于2014-01-26得票数 1

2回答

Python中模运算符的时间复杂度

python、python-3.x、operators、time-complexity、modulo

我正在尝试确定我拥有的算法的时间复杂度，但我首先需要知道Python中%(模数)运算符的时间复杂度。根据上的，它的时间复杂度可能类似于O(log m log n)，在某些特定情况下，它也可以优化为常数，但我想知道是否有人真的知道%的时间复杂度，这样我就可以正确地确定我的算法的

浏览 1提问于2016-02-04得票数 7

7回答

在内存中存储图形的三种方法，优缺点

graph

在内存中存储图形有三种方法：我知道如何写这三种语言，但我不确定我是否考虑过每种语言的优缺点。在内存中存储图形的每种方法的优缺点是什么？

浏览 57提问于2010-07-20得票数 100

回答已采纳

1回答

两个AVL节点之间的最大搜索值

algorithm、data-structures、time-complexity、avl-tree

我有一个AVL tree，而每个节点包括：AVL tree由键排序。复杂度时间： O(l

浏览 2提问于2011-05-17得票数 2

回答已采纳

2回答

弗洛伊德·沃希尔使用邻接表

java、floyd-warshall

是否可以使用邻接表对Floyd Warshall进行编码？我必须处理文本文件中的一百万个顶点，因此，邻接矩阵不是一个解决方案。有没有已经可用的实现？请帮帮忙。

浏览 3提问于2014-11-29得票数 3

2回答

Javascript中链表与数组的比较

javascript、algorithm、data-structures、linked-list

我们在给定的索引处插入新元素，并将其余元素向前移动一个索引。所以我试着用链表来做这件事，并以下面的代码结束： }}, return this.toArray().toString();} 最后，我的问题是:这种方法是否比数组更快，如果是，两者的复杂性是什么？也许更重要的<

浏览 2提问于2013-08-26得票数 7

回答已采纳

1回答

Cypher查询聚合neo4j多重图边并返回一个简单图

graph、neo4j、cypher、aggregate

我们有一个电子邮件连接的多重图。在这个图中，两个节点之间有许多边。是否有任何循环查询来聚合每个节点对之间的所有边，然后返回一个新图？注意:我知道聚合边的查询，但它返回的是表，而不是图！

浏览 7提问于2018-08-08得票数 2

回答已采纳

点击加载更多