1回答
我有n个顶点编号为1...n，并希望将每个顶点与所有其他顶点配对。这将导致n*(n-1)个/2边数。每个顶点都有一定的strength.The差，两个顶点之间的强度是边的权重。我需要得到总的权重。使用两个循环，我可以在O(n^2)时间内做到这一点。但是我想减少时间，我可以使用邻接表并使用它创建一个n*(n-1)个/2边的图，但是我如何在不<em
浏览 8提问于2017-08-30得票数 3
回答已采纳
2回答
为了找到模型上所有的平坦(或接近平坦)的表面，我认为我可以尝试通过它们的法向量对三角形进行分组(给我面向相同方向的三角形)，然后我可以在这些较小的集合中搜索位置相似或相连的三角形。我有顶点信息和三角形信息(顶点、中心和法线)。
如有任何建议，我们将不胜感激。
浏览 2提问于2019-09-01得票数 1
给定有向多图的邻接列表表示，有向多图是否有O(V+E)算法将其转化为无向简单图？该算法显然应该使用最小的空间。
浏览 5提问于2012-10-10得票数 0
1回答
图在c++中的实现问题
、、、
我正在学习如何在C++中实现一个图，所以我读了，发现有两种常用的方法：邻接表和邻接矩阵。我理解邻接表和邻接矩阵在空间上的权衡。2)使用不同的数据结构有什么不同？链表与向量图
邻接表和邻接矩阵的另一个显著区别是它们执行的操作效率。在邻接列表中，可以有效地列出每个顶点的邻域，时间与顶点的程度成
浏览 0提问于2013-12-13得票数 1
回答已采纳
3回答
在我的算法课上，我被告知用于图表示的邻接表的缩回是迭代通过对应于每个节点的相邻节点数组的O(n)查找时间。我使用将节点映射到其相邻节点的HashSet的HashMap来实现我的邻接列表，这不是只需要O(1)查找时间吗？我是不是漏掉了什么？
浏览 2提问于2017-03-26得票数 3
1回答
链表在图邻接表示中的优势
、、、
Skiena的算法设计手册(3ed，第204页)提到了邻接列表，而不是一般的邻接表示，定义它们为每个顶点a分配一个具有底层集合set(L_a) = {b | (x, b) <- edges, x ==但是，在我们不关心顺序的情况下，这些操作也可以是对数组的固定时间操作，使用“交换和pop”来删除。哈希表将具有恒定时间搜索的额外优势。我的理解是，哈希表比链接列表或数组花费更多的内存，但这种考虑已经变得相对不那么重要了。(在没有特定应用程序的情况下
浏览 7提问于2021-12-17得票数 0
回答已采纳
1回答
这是一个区间图吗？
、、、
每个顶点表示一个区间，如果对应的间隔重叠，则两个顶点之间存在一条边。下面是一个具有相应间隔的区间图示例。多个线性时间算法可以确定给定的图是否为区间图。这些图的许多其他图论问题在线性时间内也是可解的.有关详细信息，请参阅维基百科和GraphClasses链接。图可以使用无向图的任何标准化结构作为输入，其中包括
邻接矩阵/
浏览 0提问于2021-08-12得票数 13
4回答
我的问题涉及创建有向图，通过与包含图形的文本文件进行比较来检查它是否唯一，如果它是唯一的，则将其附加到文件中。在这种情况下，最好的图形表示是什么？我正在使用Python，并且我将使用蛮力来检查图是否同构，因为图很小并且有一些限制。
浏览 0提问于2017-08-24得票数 5
“算法设计手册”，第二版，问题5-22：
因为问题出现在关于无向图的章节中，假设我们的图是无向的。g->edgesv是指向v的邻接列表的指针.g->Mu返回g邻接
浏览 3提问于2017-02-19得票数 1
2回答
图可选性C++
、、
所以我有个家庭作业问题：
调用G可排序，如果顶点可以从1明显编号到n (没有两个顶点有相同的编号)，那么每个具有传入边的顶点至少有一个前驱体和一个较低的数字。例如，假设NUM(v)是分配给顶点v的数字，并考虑一个顶点x，其中有来自另外三个顶点r、y和z的传入边。那么NUM(x)必须大于NUM(r)、NUM(y)和NUM(z)的至少一个。此外，算法必须是线性的，O(|V|+|E|)。
遍历这个图是很容易的，但是我不知道如何检
浏览 5提问于2013-09-29得票数 1
. + vn + (incident edges) 首先，我所说的是正确的吗？其次，这是怎样的O(N + E)，以及为什么会很好的直觉。谢谢
浏览 0提问于2012-07-13得票数 161
回答已采纳
1回答
考虑一个多图G，其中需要进行以下三项裁减：
从图中删除具有两个邻居的顶点，并通过新的边将它们的邻居连接起来；从图中移除具有一个邻居的顶点。这是一个家庭作业问题，我在最近的一次作业中被要求证明这三项削减可以在O(m+n)时间内完成。任何帮助，以更好地理解如何着手这样做，是非常感谢的。谢谢!
浏览 2提问于2022-02-21得票数 1
回答已采纳
1回答
我试图在C++中创建一个算法，它将用最多6种颜色对平面图的顶点进行着色。我只是在寻找一些伪代码来帮助我开始工作。任何帮助都是非常感谢的。谢谢。
浏览 1提问于2012-01-26得票数 2
因此，我正在尝试编写一个算法，用于计算在O(m + nlogn)时间内可以访问的顶点上的约束的最短路径。在这个问题中，我们给出了一个间接加权(非负)图G= (V，E)，一组顶点X⊂V，以及两个顶点s，t∈V\ X。这个图是用邻接表给出的，我们可以假设它需要O(1)时间来确定一个顶点是否在X中。我正在尝试编写一个算法，它可以计算G中s和t之间的最短路径，使得如果在O(m + nlogn)时间内存在这样的路径，则该路径最多包含从X到X的一
浏览 1提问于2020-05-08得票数 0
这是一个练习考试，我正在练习on...not确定如何回答这个问题：
考虑在图中存储边的三种数据结构(邻接矩阵、邻接列表、边列表)。每种数据结构最适合什么类型的应用程序？如果我错了，请纠正我，但据我所知，邻接矩阵是表示图的最低效率的方法，因为在二维数组中有一些元素表示不存在的边，而其他两个数据结构只包含表示存在边的元素，所以任何操作的遍历都会更慢。如果这是真的，那么为什么会有人想要使用它呢？对于邻接表，它比邻接矩阵更有效，但仍然包含冗余
浏览 2提问于2013-12-14得票数 0
我正在尝试实现karger随机收缩算法，它涉及到随机选择图中的2个相邻顶点，并对它们进行收缩，直到总共只剩下2个顶点。我正在使用此代码生成随机数#include <stdlib.h>
int r = rand() % v; (v is thenumber of vertices in the graph and will decrease by 1 for every contraction)1(1的
浏览 3提问于2014-11-13得票数 0
1回答
我对tree.If的BFS时间复杂度有点困惑，如果一个父节点没有n个子节点，那么找到这个值的时间复杂度是多少？我想用BFS算法找出顶点"K“，那么时间复杂度是多少？请解释一下。
浏览 1提问于2016-11-09得票数 0
扫码
添加站长 进交流群
领取专属 10元无门槛券
手把手带您无忧上云
相关资讯
热门标签
云服务器
ICP备案
对象存储
腾讯会议
云直播活动推荐
腾讯云开发者
