2回答
我正在编写用于选择排序和插入排序的实现。然后用一个自动生成的阵列对它们进行测试，并在MAC OS下用Posix MAC OS以u秒的精度评估所需时间。
但是在大多数情况下，在总65525和从-65525和+65525输入数组的范围内，插入排序要比选择排序快得多，大约有一半的时间表示。
执行情况见下文：
void selectionSort (vector<int>& ns) {
uint_t j, minInd;
for (uint_t i = 0; i< ns.size() - 1; i++) {
j = i + 1;
minIn
浏览 3提问于2015-11-17得票数 1
回答已采纳
1回答
问题描述
给定的顶点V，它可以被称为“命题”。
给定的权重：
data W
= Requires -- ^ Denotes that a "proposition" depends on another.
| Invalidates -- ^ Denotes that a "proposition" invalidates another.
在线性序中，如果A要求B，则B必须在A之前，反之，如果A使B无效，则B必须在A之后。
给出了一个加权有向多图(多重图)，它最多有2条平行边.其中一个顶点只能要求包含另一个顶点一次，并且只
浏览 5提问于2017-06-02得票数 3
1回答
使用基于图形的方法创建平面图是我的一项作业。
基于图的方法是将各部门之间的权重最大化。
图法的步骤
步骤1:选择一个重量最大的部门对。
步骤2:根据权重之和选择第三个部门
选定的两个部门
步骤3:选择下一个未选择的部门，通过评估权重之和输入，并将该部门放置在图表的面板上。
步骤4:计算step3，直到选择所有的退房
我完成了Step3。
这是一个创建规划图的关系图。
我的代码：
for (int i = 0; i <= in_step4_1.size() - 1; i++)
{
for (int j = 0; j <= in_step4_1.size
浏览 1提问于2019-05-22得票数 0
1回答
第一个问题是，我找不到一个算法，它以有向图作为输入，作为输出给出图中所有循环的列表。(这个问题应该是NP-完全的)。
经过一段时间的思考，我意识到我可能真正需要的是找到最大权重(边的权重之和)的电路(它可以有重复的顶点，但不能有重复的边)。
这也应该是一个NP-完全问题，一种处理方法可以是列出图中的所有电路，然后根据边权和排序它们。
你知道有哪些算法给出了一个有向图中所有电路的列表作为输出吗？还是能找到最大权重的电路？
我找到了这个，但这不是我所需要的。
但是，您确认了这些问题的计算复杂性吗？
浏览 0提问于2017-01-18得票数 2
回答已采纳
2回答
合并排序与快速排序实现
、、、
我必须测量快速排序和合并排序在随机数文件中排序整数所需的时间。
我在网上读到，对于大量的数据，合并排序应该比快速排序更快，但我的测量结果恰恰相反，合并排序所需的时间几乎是快速排序的两倍。
这些算法的实现是我的问题吗？
测量结果：
快速排序：
5 milion int - 715,194,000 ns10 milion int - 1,383,187,400 ns50 milion int - 6,819,586,800 ns100 milion int - 14,159,986,000 ns</code>H 111</code>150 milion int - 22,4
浏览 1提问于2020-12-05得票数 0
回答已采纳
2回答
我是Haskell的新手，我正在尝试为图和其中的节点创建一个类型类。因为我同时需要有向图和无向图，所以我有
data Node = Node { label :: Char
, index :: Int
} deriving (Ord, Eq)
type Graph edgeType = ([Node], [edgeType])
data Edge = DirectedEdge {h :: Node, t :: Node}
| UndirectedEdge {a :: Node, b :: Node}
浏览 2提问于2011-06-07得票数 5
回答已采纳
1回答
使无向图有向
、、
我有一个无向图，完全图，并希望将它转换成一个有向无圈图，在每个节点之间有一个(单向)路径。为了开始，我想添加随机边和停止一旦所有节点连接。需要研究的是一个算法(使用Python，但任何语言都可以)。
因此，例如，这个图不再被进一步连接：
A ---- B A ---> B
\ / => /
\ / v
C C
，但在这种情况下，所有无向边都会变成有向边。
A ---- B A ---> B
\
浏览 5提问于2014-10-08得票数 1
1回答
我有一个无圈图，每个顶点都有数字标签，我想为这个图找到；然而，一个图可能包含几个拓扑顺序，但我想找到特定的顺序，哪个顶点数有数字顺序，见下图以获得更多解释。
如上图所示，这张图包含几个拓扑顺序。
4 5 6 1 2 3
1 4 2 5 6 3
1 2 4 5 3 6
1 2 3 4 5 6
.
但是我需要这个顺序1 2 3 4 5 6，我想知道如何改变拓扑排序算法，以找到这个特定的顺序。
下面是另一个例子：
在示例图中，这两个顺序是真的。
2 1 0
但是当我使用第一个应答排序函数时，它将交换2和0，最后的结果将是0 1 2，这是一个错误的答案。
浏览 2提问于2016-10-25得票数 2
回答已采纳
我有一个DAG (有向无环图)，它有多个有效的拓扑排序。我正在寻找一种方法来对它进行拓扑排序，并应用二次排序，以始终获得相同的、定义良好的结果。
例如，以下面的图为例：
A-->B
A-->C
B-->D
C-->D
拓扑排序有两种解决方案：
1: A、B、C、D和
2: A、C、B、D
我们注意到B和C可以按任何顺序排序。因此，我们选择字母排序作为二次排序，只得到一个解: A，B，C，D。
这可以推广到任何DAG吗?如何实现？
浏览 10提问于2016-08-16得票数 1
我需要的是的JavaScript实现。需要说明的是，我指的不是像或这样的图形可视化库。
我正在寻找的库将实现以下功能：
为图创建有向图和无向图的有向图和无向图objectscreation objectsadding/removing顶点和边的加权和未加权图为顶点和边添加标签(即，、、、和等基本图搜索和遍历算法的附加元图
有没有人知道它是否已经存在？
浏览 125提问于2013-01-23得票数 28
回答已采纳
1回答
这是我其他帖子的后续问题。
我正在研究一种聚类算法，经过一些重新聚类之后，现在我有了一组点，它们都不在它们的最佳集群中，但不能单独重新分配，因为这将违反约束。
我试图使用一个图结构来解决这个问题，但是在实现中遇到了一些问题。
我是初学者，如果我错了，请告诉我。
Per @Kittsil的回答
构建一个以集群为节点的有向图，这样，如果全局解决方案被A移动到B中的某个点最小化，则存在一个边(A，B)，在该图中查找循环将允许您找到潜在的移动(其中移动包括移动循环中的每个顶点)。
我修改了图，将权重加为从A到B的点数之和。
以下是一些我不确定如何决定重新分配的点的场景。
场景1。一个周期如下
浏览 2提问于2015-05-08得票数 3
回答已采纳
1回答
如果有一组节点N和一组顶点V_1定义具有一定拓扑顺序的图G_1，那么如何检查来自N的节点子集和定义图G_2的新顶点V_2是否保持G_1的拓扑顺序？
例如：
G_1:
D -> E
B -> C
A -> C
G_1：[A, B, C, D, E]的拓扑序
G_2:
D -> B
B -> E
G_2：[D, B, E]的拓扑序
我在考虑某种蛮力方法，生成G_1的所有拓扑顺序，从这些命令中删除在G_2中找不到的节点，并检查是否有任何与G_2的第一个排序相匹配的方法。
我的潜在解决方案正确吗？你有更好的建议吗？
浏览 1提问于2018-07-27得票数 1
回答已采纳
我有一种直觉，原始图的拓扑排序与转置图的dfs相同(反转所有边)
A -> B -> C
D -> B
拓扑排序是D、A、B、C或A、D、B、C
如果我转置图形(反转所有的边)
C -> B -> A
B -> D
dfs还给出了D、A、B、C或A、D、B、C
求求你，我不能从数学上证明/反驳它。如果命题不正确，举一个反例会很有帮助。
浏览 2提问于2020-04-25得票数 0
1回答
我正在处理图/网络，其中节点和边有一些属性。
我想知道存在哪些算法：
1)将图聚为k组:仅依赖于结构(只依赖边缘属性)
2)社区检测：(与图聚类相同)，但社区数量未知。
3)分类:一种有监督的方法，在这种方法中，我要根据节点的属性和连接(边)对节点进行分类。
4)页面排名:根据一个组(社区、集群)中最重要的节点的连接来检测它们。
非常感谢。
浏览 0提问于2018-07-06得票数 1
回答已采纳
1回答
我有一个任务是检查两个无向图是否同构。为了实现树，我使用简单的邻接列表示例。我需要做的第二件事是对树进行“字典序”排序，当对树的邻接表进行排序时，字典序排序和基数排序有区别吗？
浏览 6提问于2016-05-15得票数 0
2回答
我有一张图，我想要遍历这个图(不是所有顶点都需要的)，总是走权重很大的路。我不能通过相同的顶点两次，我停止，如果没有更多的动作，我可以。复杂程度有多大？我假设它是"n“(其中n是顶点的数目)，但我不确定。
浏览 4提问于2013-10-25得票数 0
回答已采纳
2回答
我有一个结构，看起来很像一个图表，但我可以对它进行“排序”。因此，我可以有两个等价的图，但一个是排序的，而不是另一个。我的目标是计算一个最小优势集(使用一个适合我的特定问题的自定义算法，所以请不要链接到其他“有效”算法)。 问题是，我搜索大小为1的优势集，然后是2，等等，直到我找到一个。如果没有一个主要的大小为i的集合，那么使用排序图的效率要高得多。如果有的话，使用未排序的图要好得多。 我考虑使用线程/多处理，这样两个图同时被探索，一旦一个找到答案(没有解决方案或特定的解决方案)，另一个停止，我们进入下一步或结束算法。这不起作用，它只会使过程变得更慢(即使我希望它只需要两倍的时间，每一步，与
浏览 25提问于2020-10-12得票数 0
我想在网络模拟器ns2中实现Delaunay三角剖分。到目前为止，我知道如何添加节点，如何使它们移动，如何设置流量，以及基本的内容。示例tcl脚本在nam(网络动画)中运行得很好。我感到困惑的是，要实现Delaunay三角剖分的Boyer算法，第一步是画一个包含所有节点的超三角形。我使用无线节点，能够得到随机分布节点的坐标。另外，我可以设法得到每个节点到所有其他节点之间的欧几里德距离。当我在ns2中搜索绘图时，所有的内容都是关于x图的。但我希望我能在南南实现它。那么，从哪里开始为我的无线传感器网络画一个超级三角呢？我想的有什么不对吗？张贴博耶沃森算法下面。有人能帮忙吗？
// pointLis
浏览 5提问于2021-08-15得票数 0
回答已采纳
2回答
我目前正在用C++实现动态DAG图-它将通过用户界面显示给用户，插入/删除节点/边将是常见的操作。
图形的大小可能从非常小的规模到大的规模--我的目标是支持数百万个节点。
因此，我正在寻找一种优化的数据结构，它不会占用内存中太多的空间，但也可以通过拓扑排序节点上的快速多线程迭代(因此多个节点可以并行执行)实现快速插入/删除。
我还没有做过任何分析，看一种天真的方法在每次修改时重新计算一个拓扑类型的完整图是否会减少它，但为了学习，我想我宁愿找到一种“更聪明”的方法。
我不知道如何处理图的多线程迭代，但首先，我偶然发现了一些与迭代/动态拓扑排序步骤有关的论文，问题是它们对我来说有点太聪明了。它深入
浏览 1提问于2014-07-15得票数 4
2回答
给定一个带权的无向连通图。w:E->{1,2,3,4,5,6,7} -意味着只有7个权重。我需要使用O(n+m)中的Prim算法和O( m*a(m，n))中的Kruskal算法找到一棵生成树。
我不知道如何做到这一点，真的需要一些指导，如何权重可以帮助我在这里。
浏览 4提问于2012-05-28得票数 0
1回答
递归排序字符串
、、
我发现，使用，排序顺序部分地通过字符串进行更改：
In [31]: import natsort as ns
In [32]: ns.natsorted(["01-08", "02-07", "01-06", "02-09"])
Out[32]: ['01-08', '01-06', '02-09', '02-07']
在这种情况下，我想要的行为是：
In [33]: sorted(["01-08", "02-07", "01-
浏览 5提问于2015-04-09得票数 0
回答已采纳
2回答
给出了图G=(V，E)的两个算法：
第一：
排序边从最低到最高。为每个边设置了T={}，按照以前的顺序，检查e Set是否没有任何循环。如果是，将e添加到T.，如果它是生成树，则返回T。
二：
排序边从最高到最低。为每个边e设置T=E，检查T{e}是否是连通图。如果是，请从T.中删除e，如果它是生成树，则返回T。。
这两种算法是否确实返回最小生成树？如果没有，我想看一个反例。
浏览 6提问于2022-07-31得票数 -1
回答已采纳
1回答
任意无向加权图的反馈集是边的子集，在去除子集中的边后，剩下的图是无圈的。
给定G= (V，E)，一个无向加权图和一个整数k，我如何确定是否有一个总权重不超过k的反馈集？
谢谢!
浏览 5提问于2020-03-17得票数 0
回答已采纳
1回答
我对闪电图(和js总体上)很陌生，我想显示基本的热图值(坐标和值{"x":-32，"y":-31，“热”：73.77} )，但其中160万是在json文件中的。
做这件事最好的方法是什么？至少这是最好的方法吗？
我找不到基本的资源来测试，只有复杂的模型。
提前谢谢你！
浏览 5提问于2022-01-13得票数 -1
1回答
我正在尝试验证图(G= V，E)的最小生成树(T = V，ET)。有没有一种方法可以验证它，比如return true，否则它就是一个MST，return False？谢谢
浏览 10提问于2021-06-27得票数 0
我正在阅读CLRS算法第3版，我的家庭作业有两个问题(我没有要求答案，我保证！)它们本质上是同一个问题，只适用于克鲁斯卡尔或普利姆。它们如下：
假设图中的所有边权都是从1到all的整数。你能让Prim/Kruskal的算法运行多快？如果边权值是从1到W的整数，对于一些常数W呢？
我可以看到我正在思考的答案背后的逻辑，以及我在网上发现的东西(即用线性排序来排序边缘权重，改变正在使用的数据结构等等)，所以我不需要帮助回答它。但我想知道，如果范围是1到v，1比W，为什么会有不同的答案，为什么问同样的问题两次？如果它是一个常数W，它可以是任何东西。但老实说，我们可以得到一个疯狂的大图，或者一个非常小
浏览 3提问于2021-12-02得票数 0
2回答
我正在尝试合并C中一个相当大的双链接列表中的一个键的排序a，这个列表中有大约10万个元素。以下是DLL元素的结构：
struct Pore {
int ns; /* voxel number */
int radius; /* effective radius of porosity surrounding a pore */
struct Pore *next;
struct Pore *prev;
};
在搜索算法之后，我发现最常用的算法包含三个函数：mergeSort、merge和split。我把他们也包括在这里..。请原谅merge函数中的多个m
浏览 2提问于2020-06-15得票数 0
回答已采纳
2回答
我正在使用对JS中的图执行拓扑排序。问题是，在极少数情况下，图中会包含圈。这些都是结构的次要部分，因此丢弃一些边缘不会对最终结果产生太大影响。然而，当它们出现时，算法就会中断。更新它的最有效方法是什么，这样如果有一两个周期，它就不会崩溃？
浏览 3提问于2013-08-17得票数 1
2回答
测量的插入排序速度太快了
、、、
我正在Java中快速测试各种排序算法，向它们提供随机生成的数字数组，并且我得到了插入排序的奇怪结果。
我使用System.nanoTime()来度量运行时，插入排序的值低于快速排序和合并排序，即使在排序大型数组时也是如此，这似乎是错误的。我在程序中看到了气泡排序或选择排序的正常(缓慢)运行时间，所以我认为我测量插入的速度不合适，但我不确定如何：
public static int[] insertionSort(int[] array) {
long startTime = System.nanoTime();
int current;
int innerIdx;
浏览 5提问于2017-04-04得票数 4
回答已采纳
例如，假设我有一个图G，它包含所有蓝色节点和一个红色节点。我还有一个图F，它有一个全蓝色和一个红色的节点。
我可以运行什么算法来验证这两个图相对于它们的着色节点是同构的？
浏览 4提问于2013-04-21得票数 2
我使用的是ms sql server。我有一个像这样的sql：
select ... from
(select ... from ... left join .... where ... order by ... offset 0 rows fetch next 50 rows only) a
left join ...
left join ...
当我将50更改为20或10时，执行速度很慢，当我使用50或100时，执行速度不会那么慢，这可能会导致什么结果？
我比较了sqlplan，两个图没有区别，除了每个节点中的参数(step？)。
另外，我更改了另一个数据库，问题
浏览 2提问于2018-03-29得票数 1
36回答
数据结构、算法、计算机原理是编程和实践的根基，看似枯燥和基础，却具有最长久的生命力。
作为人类高质量程序员，写代码精髓就是领略数学之美。
算法：
排序算法：快速排序、归并排序、计数排序
搜索算法：回溯、递归、剪枝
图论：最短路径、最小生成树、网络流建模
.......
数据结构：
数组和链表
栈与队列
树和图
.......
image.png
作为程序员的你，认为编程必须掌握哪些算法？快来分享你的见解吧！
内容要求
● 围绕算法，发表见解 50 字以上（需原创，禁止转载）
奖励
回答赞同数 TOP10 的用户将有机会获得精美定制小礼品一份
评选标准
回答需符合活动中所提及的要求，
浏览 4839提问于2021-09-02
2回答
我正在寻找一种在给定的包含圈的有向未加权图上执行拓扑排序的方法。结果不仅应该包含顶点的排序，还应该包含被给定排序违反的边集。这组边应该是最小的。
因为我的输入图可能很大，所以我不能使用指数时间算法。如果不可能在多项式时间内计算出最优解，那么对于给定的问题，什么启发式方法是合理的？
浏览 4提问于2013-06-17得票数 21
回答已采纳
1回答
动态最小生成树
、、
我想创建一个动态的最小生成树。我在n个顶点上有一个现有的MS树，并且我从这个新的顶点向所有现有的顶点添加了一个顶点和边。如何有效地更新新图的MST？O(n)将是最优的。我还可以使删除顶点操作更有效吗？
浏览 2提问于2012-03-22得票数 6
1回答
带环拓扑排序
、、、
我正在为组合电路和时序电路编写一个简单的数字模拟器，我选择了一种图形方法来模拟这个问题。
如果电路没有循环，我可以把它表示为DAG。在这种情况下，我至少可以想到两种方法来执行模拟:递归地，从输出向后或从图的位置选择。
当循环存在时，当我不能再对节点排序时，就会出现这个问题，但是由于电路是一个有向图，其边从输入到输出只有一个方向，所以循环是唯一“返回”的边。
因此，有了这些限制，我正在寻找一种方法来执行拓扑排序--“忽略循环”--给定邻接列表。
我的想法是:如果我试图对组件进行排序，而不考虑循环，我可以先评估循环驱动程序，然后进行模拟，就像没有循环一样。当我用手解决逻辑电路时，这种方法工作得很好
浏览 0提问于2019-07-31得票数 2
回答已采纳
1回答
我正在寻找一种算法，它可以对一个图进行拓扑排序，从而生成一组列表，每个列表包含一个不相交子图的拓扑排序顶点。
当节点依赖于两个不同列表中的节点时，困难的部分是合并列表。
这是我的不完整代码/伪代码，其中图是一个dict {node: [node, node, ...]}
拓扑排序图为不相交列表
sorted_subgraphs = []
while graph:
cyclic = True
for node, edges in list(graph.items()):
for edge in edges:
if edge in grap
浏览 3提问于2017-02-02得票数 0
回答已采纳
我最近读了一些关于典型微笑字符串的论文，对我来说，似乎大部分时间的规范化过程都依赖于将额外的化学信息添加到微笑字符串表示中。现在我在想：
有没有一种算法可以为一般的顶点和边标记图，即图，计算某种类型的规范微笑串？
由一组顶点定义
一组有向边
顶点标注函数
和边缘标记函数
，其中
是顶点和边标签的数量吗？也就是说，有没有一种算法可以证明将同构的标记图映射到相同的规范微笑字符串？
提前谢谢你。
浏览 10提问于2021-09-15得票数 1
1回答
我想要一个可以返回k (k>=1)随机拓扑排序的函数。大多数图库中的内置算法只有一个返回一个拓扑排序的函数(topological_sort(G))或一个返回所有拓扑排序的函数(all_topological_sorts(G))。 我尝试过的一种方法是首先生成all_topological_sorts(G)，然后从其中随机选取k个结果。但当G较大(>20个节点)时，函数all_topological_sorts(G)的时间复杂度太高。 如果我调整函数topological_sort(G)以允许它找到一个随机拓扑排序。我可以重复这个过程很多次。每次它返回一个结果，如果它与以前的结果
浏览 23提问于2020-06-24得票数 1
1回答
给定一个图和一个数n，是否有算法通过删除n边来分割图，以最小化最长路径/直径的长度？
例如，如果我有以下图表：
A - B - C - D
\ E - F
而n= 2，您会想要在以下两个之间切分图：
B和C
B和E
因此，任何路径都不会超过2。如果该图是一个树/无圈无向图，这是否也会产生影响？
EDIT1:由树/无环无向图改变的重组图
浏览 1提问于2015-12-30得票数 2
假设图G的边权在[0，1]上均匀分布，.Which算法素数或Kruskals算法会更快吗？我认为这将是kruskals，因为我们可以利用特定的排序算法，因为排序是kruskals算法中的瓶颈步骤。
浏览 0提问于2013-06-10得票数 1
我有一个有大约10亿个顶点的图，每个顶点都随机连接到大约100个其他顶点。
我想找出两点之间最短路径的长度。我不在乎实际使用的路径。
备注：
有时边缘会被切断或添加。这种情况比查找的次数少500倍。如果它能让你获得更好的性能，也可以批量进行边缘更改。
我可以对图表进行预处理。
如果它需要超过6个步骤，你就可以带着无穷大返回。
这是可以接受的错误0.01%的时间，但只有在返回一个长度太长。
所有的边都有1的长度。
所有的边都是双向的。
我在找算法。Psuedocode、英语描述和实际代码都很棒。
我可以使用A*，但这似乎优化了路径查找。
我曾考虑过使用迪克斯特拉算法，但它有一个步骤，要求将每个
浏览 0提问于2013-04-03得票数 8
回答已采纳
我想知道算法和算法的区别。
他们的共同点是：
两者都在无向图中找到。
这两种方法都在现有树中添加最短边，直到找到MST为止。
与算法不同，这两种算法都从整体上看图，后者将一个节点一个接一个地添加到MST中。
这两种算法都很贪婪。
唯一的区别似乎是，Boruvkas透视图是每个节点(从那里寻找最便宜的边)，而不是查看整个图(就像Kruskal那样)。
因此，Boruvka应该相对容易并行(不像Kruskal)。这是真的吗？
浏览 0提问于2018-04-22得票数 5
2回答
我有一个函数，它可以接受两个元素并按升序返回它们：
void Sort2(int &a, int &b) {
if (a < b) return;
int t = a;
a = b;
b = t;
}
--如果不允许使用额外的条件运算符，使用这个函数对数组进行排序的最快方法是什么？，这意味着我的整个程序应该如下所示：
int main(){
int a[N];
// fill a array
const int NS = ...; // number of comparison, depending on N.
const
浏览 2提问于2013-10-23得票数 3
回答已采纳
2回答
module Main where
import Test.QuickCheck
import Data.Set as Set
data Edge v = Edge {source :: v, target :: v}
deriving (Show,Eq,Ord)
data Graph v = Graph {nodes :: Set v, edges :: Set (Edge v)}
deriving Show
instance Arbitrary v => Int-> Arbitrary (Edge
浏览 1提问于2016-04-04得票数 3
回答已采纳
1回答
假设你是一个自由职业者，一次只接受一份合同，那么从下面的列表中找出一种算法来选择最有利可图的、不重叠的工作：
potential_contract_jobs = [
{
"start_day": 1,
"end_day": 5,
"profit": 100
},
{
"start_day": 5,
"end_day": 6,
"profit": 10
},
{
"start_day": 15,
浏览 1提问于2015-10-24得票数 1
1回答
我正在考虑在配置文件中使用xml名称空间。如果我使用名称空间标记配置文件内容，则会标识程序版本的选项。
是否有方法选择具有特定命名空间版本号和较低的所有节点？这允许任何版本的应用程序读取任何版本的配置文件，而不改变。
示例：
<ns1:config xmlns:ns1="version 1.0">
<ns1:somesetting>blah</ns1:somesetting>
<ns2:SomeNewSetting xmlns:ns2="version 2.0">foob</ns2:S
浏览 0提问于2018-04-01得票数 0
回答已采纳
6回答
上周，我无意中发现了，作者在第二页中提到了这一点：
请注意，这将产生整数边权值的线性运行时间。
在第三页上也是如此：
这就产生了整数边权值的线性运行时间和基于比较排序的O(m log n)。
在第8页：
特别是，使用快速整数排序可能会大大加快GPA。
这是否意味着在特殊情况下存在整数值的O(n)排序算法？还是这是图论的专长？
PS:
可能是参考3可能有帮助，因为他们在第一页上说：
已经取得了进一步的改进。图类，如整数边权值3，
但我没有机会接触任何科学期刊。
浏览 14提问于2010-02-28得票数 62
回答已采纳
据我所知，如果对强连通组件有现成的高效黑匣子方法，那么进行拓扑排序的一种方法是：
(假设-没有自我循环)
运行强连接组件
如果您有一个或多个大小大于1的组件，则此图有循环。
否则(图中只有一个大小的组件)这是一个DAG，恭喜！
如果这是DAG运行拓扑排序，否则抱怨你做不到。
不管效率如何，以上是否是一种“技术正确”的拓扑排序方法？
我只想确认一下我对事情的正确理解。
浏览 5提问于2015-06-01得票数 1
回答已采纳
我正在修改一个测试，并遇到了两个问题，与最小生成树在图中，我不确定，并想测试我的答案。
第一个问题是:如果一个图有多个最小生成树，那么Kruskal和Prim的最小生成树算法会生成相同的树吗？我认为它们不一定是因为算法不同而产生的。Kruskal依赖于按权重排序的边，而Prim则不这样做，因此它们可以从不同的顶点开始，从而生成不同的树。
第二个问题是:如果一个图有多个最小生成树，那么Kruskal的算法应该如何才能产生所有这些？我认为，我们需要允许一个循环结构穿过顶点，这样开始顶点每次都会发生变化，因为边缘值可能是相同的。因此，通过将每个顶点依次作为起始顶点来生成树。换句话说，按顶点编号进行排
浏览 3提问于2014-04-29得票数 2
回答已采纳
扫码
添加站长 进交流群
领取专属 10元无门槛券
手把手带您无忧上云
相关资讯
热门标签
云服务器
ICP备案
对象存储
腾讯会议
实时音视频活动推荐
腾讯云开发者
