标签: graph-algorithm

这是Vazirani的算法书中的一个问题

该问题的输入是树T,边缘上具有整数权重.权重可以是负数,零或正数.给出线性时间算法以找到T中最短的简单路径.路径的长度是路径中边缘权重的总和.如果没有重复顶点,则路径很简单.请注意,路径的端点不受约束.

提示:这与在树中查找最大独立集的问题非常相似.

如何在线性时间内解决这个问题？

这是我的算法,但我想知道它是否是线性时间,因为它与深度优先没什么不同:

1. 遍历树(深度优先)
2. 保留索引(节点)
3. 添加值
4. 做(1)直到树的尽头
5. 比较总和并打印路径和总和

这个问题与此主题类似,但没有确定的答案.

我正在构建一个表面看起来像Visio的应用程序,所以我需要能够将对象与连接器连接在一起.我想让连接器具有多个水平和垂直段,并且能够拖动连接器的角落并使它们"智能地"添加新角或在拖动时合并到连接器的现有部分.连接器缠绕其他物体而不是穿过它们也是很好的.

我认为至少他们必须是一个算法,如果我真的很幸运一些不错的c#代码!

有任何想法吗？

我正在寻找一种有效的算法,能够在双向N*M网格中找到尽可能随机的哈密​​顿路径.

有谁知道我在哪里可以找到,或者如何构建这样的算法？

我已经找到了一种有效的方法(见下图).这里的最终结果是哈密顿循环.删除随机边缘将使其成为哈密尔顿路径.该算法是有效的,但不提供足够的随机性.这种方法总是让路径的起点和终点彼此相邻,而我希望将它们放在随机位置. 空间填充曲线http://img593.imageshack.us/img593/8060/sfc.png 图片取自http://citeseerx.ist.psu.edu/viewdoc/download?doi=10.1.1.35.3648&rep=rep1&type= PDF格式

我正在使用OpenGL ES 2.0开发一个图像变形iOS应用程序.

我对设置,管道等有很好的把握,现在我正在进行数学运算.

由于我的图像变形经验是零,我正在寻求一些算法建议.

目前,我正在以网格类型的方式设置点的初始顶点,将图像均等地划分为正方形.然后,我在每个正方形的中间放置一个额外的顶点.当我绘制索引时,每个方块包含四个形状为X的三角形.请参见下图:

在玩了一点photoshop之后,我注意到adobe使用了一个稍微复杂的算法来实现他们的木偶扭曲,但是他们的标准扭曲算法更为简化.您觉得在这里申请/个人偏好最适合我？

其次,当我移动一个顶点时,我想对所有其他顶点应用加权变换以平滑边缘(而不是我在下面的内容,其中只有选定的顶点被转换).我应该在这里申请什么样的算法？

我需要为庞大的数据集找到连接的组件.(图形未指向)

一个显而易见的选择是MapReduce.但我是MapReduce的新手,我很安静,没时间去挑选它并自己编写代码.

我只是想知道是否有任何现有的API,因为它是社交网络分析中一个非常常见的问题？

或者至少如果有人知道任何可靠(经过试验和测试)的来源,至少我可以自己开始实施吗？

谢谢

我知道一些最小的生成树算法:Boruvka,Prim和Kruskal.哪些可以并行实现？

谢谢!

我正在寻找一种算法(或任何其他方式)来确定给定的加权图是否在O(ElogV)中具有唯一的MST(最小生成树)？

我对权重没有任何了解(例如权重(e1)!=权重(e2)),如果该图只有一个唯一的MST,算法只返回True,否则返回False.

我开始使用Kruskal的算法,并检查是否find-set(u)== find-set(v)所以在MST中有一个圆圈,但这种方式并没有涵盖我想的所有场景:(

非常感谢!托梅尔.

有没有一种有效的方法来使用Jaccard相似性来集群图中的节点,使得每个集群至少具有K节点？

节点之间的Jaccard相似i和j:
我们S是集合的邻居i和T是集合邻居j.然后之间的相似性i和j由下式给出 |(S ? T)| / |(S ? T)|.

我正在寻找算法上的线索,以推断出一系列小说的时间表/年表.我把文本拆分成几天并创建了一个关系数据库,例如:X是Y,Y和Z连续前的一个月,Z的日期已知,X是星期二,等等.有不确定性( '月'实际上只意味着大约30天),也是矛盾.我可以将某些关系标记为比其他关系更可靠,以帮助解决歧义和矛盾.

有哪种算法可以从这类数据中推导出最合适的年表,为每天分配最高概率的日期？至少时间是一维的,但处理具有不一致性的复杂关系图似乎是非平凡的.我有一个CS背景,所以我可以编写代码,但对适用算法的名称有所了解会有所帮助.我猜我所拥有的是一个图表,其中天为节点,关系为边缘.

无向图MST算法(Prim或Kruskal)是定向MST算法(Edmond/Chiu)的一般形式吗？为什么找到针对定向案例的MST源代码如此困难？我们可以使用无向解决方案在有向图中获取MST吗？

这与以下内容有关: 为什么不能在有向图上使用Prim或Kruskal的算法？