标签: 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,即j第 - 行中的所有1A
• O以DFS方式导航
• 如果从该导航生成的路径之一通向该节点i,则检测到循环

显然这个解决方案非常慢,因为我必须评估矩阵中的所有路径.如果A非常大,所需的开销非常大.我想知道是否有一种导航邻接矩阵的方法,以便在不使用昂贵的算法(如DFS)的情况下找到周期.

我想在MATLAB中实现我的解决方案.

提前致谢,

Eleanore.

我正在寻找一种方法来对给定的定向未加权图执行拓扑排序,其中包含循环.结果不仅应包含顶点的排序,还应包含给定排序违反的边集.这组边缘应该是最小的.

由于我的输入图可能很大,我不能使用指数时间算法.如果在多项式时间内无法计算最优解,那么对于给定的问题,什么启发式算法是合理的？

今天我们完成了在实验室完成的任务(两小时内完成).问题是:

• 你得到一个m*n矩阵.
• 矩阵有'h'住宅大厅和'b'主建筑入口.
• 这些'h'大厅和'b'入口的位置是已知的(以(x,y)坐标表示).
• 您需要铺设通道,使每个住宅大厅至少有一种方式到达其中一个'b'入口.
• 最多可以存在'b'这样的断开路径.
• 通路的长度必须最小.
• 您只能向上,向下,向左或向右移动.
• 解决方案绝不能是强力企图.

任务结束了.但我仍然在想如何解决这个问题.这些问题是否有标准术语？我该怎么读？

人们也会使用这种算法在城市铺设道路吗？

我有一个图论(也与组合学有关)问题,如下所示,并想知道设计算法解决它的最佳方法是什么.

给定4个不同的6个节点的图形(不同的,我的意思是不同的结构,例如STAR,LINE,COMPLETE等)和24个独特的对象,设计一种算法将这些对象分配给这4个图形4次,这样就可以了在4个分配上重复图形上的邻居被最小化.例如,如果对象A和B在一个分配中的4个图中的1个上是邻居,则在最佳情况下,A和B 在其他3个分配中将不再是邻居.

显然,这种最小化的程度取决于给定的特定图形结构.但是我对这里的一般解决方案更感兴趣,因此给定任何4个图形结构,这种最小化作为算法的结果得到保证.

任何解决这个问题的建议/想法都是受欢迎的,一些伪代码可能足以说明设计.谢谢.

我正在寻找一种并发算法,它可以帮助我检测有向图中的周期.

我知道顺序算法使用带着色的dfs,但我认为它会在多线程环境中失败.有向图的一个例子来说明它:

A - >(B,C),B->(D),D->(E),C->(E),E->(F)

                         A
                        / \
                       B   C
                       |   |
                       D   |
                        \ /
                         E
                         |
                         F

(我希望上面说清楚.图中的边缘都是顶部的)

对于上述有向图,在并发执行期间可以执行以下操作.

(我假设的着色方案是白色 - 未访问,灰色 - 执行dfs未完成和黑色 - 完成执行和访问)

Dfs(B)由线程1,最终将E颜色为灰色并执行dfs(E)(导致F).在此之前,线程2执行dfs(C).它意识到E是灰色的并报告一个明显不是这种情况的循环.

我检查过Tarjan的算法也可以用于循环检测,但我不认为它的执行在多线程环境中是正确的.

有人可以帮我解决这个问题吗？

谢谢.

我在依赖算法上有一个问题,依赖类似于maven依赖,除了它是基于严格的版本范围.

例如:

component A, version 1 depends on: component B, version 1~3; and component C, version 2~3
component D, version 1 depends on: component B, version 2~4; and component C, version 1~2

现在,我想在安装组件A,版本1和组件D,版本1时获得依赖关系.因为它们都依赖于组件B,C所以我需要一个正确的算法来获得正确的B和C版本

此外,我可能需要升级组件A和D.例如,现在我有以下新版本:

component A, version 2 depends on: component B, version 3~5; and component C, version 4~5
component A, version 3 depends on: component B, version 6~7; and component C, version 4~5
component D, version 2 depends on: component B, version 3~4; and component C, version 3~4

现在我需要一个算法来获取正确的A和D版本,我可以升级到它们的所有依赖项.这里的一个问题是组件A,版本3和组件D,版本2具有组件B的依赖冲突 …

   2           1
1----------2---------4
|          |         |
|3         |3        |1
|    6     |         |
3---------5 ---------

好的,这就是图表.我的源节点是1和目标节点5

我的问题是.

算法是否会提供相同的输出？也就是说,双方都会回归1->2->4->5吗？(除非在dijkstra中不允许负权重)

在此先感谢您的帮助.

我有一组节点和它们之间的有向边集.边缘没有重量.

如何找到必须添加的最小边数以使图形强连接(即应该有从每个节点到所有其他节点的路径)？这个问题有名字吗？

在Haskell的函数图像库(FGL),大部分的图形算法依赖于"匹配"功能,其中,由于一Node n和Graph g,退货c & g',其中c是Context的n,并且g'是图的其余部分(其中包含没有引用n).

我能看到这样做的唯一方法是检查每个上下文g并删除任何引用n并将它们添加到上下文中的边c.我相信,这需要线性时间.

马丁Erwig,谁写的图书馆,表明在这个文件,这个转换可以在不断的或至少子线性时间来完成.任何人都可以向我解释这是如何实现的吗？

我正在观看Robert Sedgewick关于快速联盟改进的视频.(https://youtu.be/sEo6LlPxpHE?t=267)

在那里他使用树的大小而不是高度.实际上问题是找到根节点.如果高度很高,发现将很困难.所以我们应该找到一种方法来减轻身高的影响.只有我们比较高度才能达到预期的效果？将较短的树连接到较高的树而不是解决问题而是:将具有较少节点数的树连接到具有较大节点数的树？

以下案例怎么样？

根据视频中的逻辑:

树的大小= 4

B树的大小= 7

如果你将A连接到B. 实际上我们正在使结果树更高(高度4).但是,如果我们基于树高度完成它,我们可以通过将树B连接到A来解决它.结果树的高度为3.

我对吗 ？如果错了我在哪里错了？