标签: graph-algorithm

Set A有n个设备.B组有m个设备.A中的某些设备与B中的设备兼容,B中的某些设备与A中的设备兼容.

我希望尽可能多的兼容设备相互连接.(没有必要让A中的设备a和B中的b相互兼容.)

为清晰起见编辑:任何设备都可以链接到0,1或2个其他设备,但不能链接到自身.

最终所有设备(或除了两个,如果"结束"不符合)应该在1对1链接在一起.可以将任何一个设备链接到任何其他设备.但是A中的任何设备都不与A中的任何设备兼容(但它们是可链接的),并且B中的设备也是如此.

If I have A = {a1,a2,a3}, B = {b1,b2,b3} and n=m=3

a1 is compatible with b1,b2
a2 is compatible with b1
a3 is compatible with b1
b1 is compatible with a1,a3
b2 is compatible with a1
b3 is compatible with a1

然后是图G

a1 <-> b2 <-> a2 <-> b1 <-> a3 <-> b3 <-> a1

是一个最佳图表.

G不必是循环的,但也可以.

有没有聪明的方法来解决这个问题？

有没有人知道用于生成DAG的拓扑排序的随机算法,其中算法的每次调用都具有生成DAG的每个有效拓扑类型的非零概率.

至关重要的是,算法不排除任何有效的拓扑排序,因为它是更大算法的一部分,在给定足够的迭代的情况下,必须能够证明能够探索给定DAG的所有拓扑类型.

有谁知道这样的算法是否已经开发出来了吗？

(或者,如果有人知道一个合理有效的算法可以保证生成给定DAG的所有拓扑类型,我可以调整它以获得我需要的东西.)

给定图G(V,E)和顶点v,我如何找到长度正好为k的简单路径(路径上没有顶点重复)可到达的所有顶点.

邻接矩阵的幂给出了顶点之间的路径数,但它包括非简单路径.

这个问题在多项式时间内是否可以解决？如果没有,是否有任何已知的近似算法.任何文学指针都会很棒.

我在编写一个算法时遇到了一些麻烦,该算法返回在无向图上形成简单循环的所有路径.

我首先考虑从顶点A开始的所有循环,对于下图

A,B,E,G,F
A,B,E,D,F
A,B,C,D,F
A,B,C,D,E,G,F

额外的周期将是

B,C,D,E
F,D,E,G

但是这些可以通过例如再次调用相同的算法但分别从B和D开始来找到.

该图如下所示 -

我目前的方法是通过访问A的所有邻居,然后访问邻居的邻居等来构建A的所有可能路径,同时遵循以下规则:

• 每次存在多个邻居时,就会找到一个分叉,并创建并探索来自A的新路径.
  

• 如果任何创建的路径访问原始顶点,则该路径是循环.
  

• 如果任何创建的路径访问相同的顶点两次(不同于A),则丢弃该路径.
  

• 继续,直到探索了所有可能的路径.

我目前在尝试避免不止一次发现相同的循环时遇到问题,我试图通过查看新邻居是否已经是另一个现有路径的一部分来解决这个问题,以便两个路径组合(如果是独立的)构建一个周期.

我的问题是:我是否遵循正确/更好/更简单的逻辑来解决这个问题.

我很感激你的意见

如果您有一组范围,例如以下简单示例......

[
    [12, 25], #1
    [14, 27], #2
    [15, 22], #3
    [17, 21], #4
    [20, 65], #5
    [62, 70], #6
    [64, 80]  #7
]

...你如何计算最大交叉子集(不确定如何短语,但我的意思是"相交且具有最高基数的范围的子集")并确定交集的程度(该子集中范围的基数) )？

逻辑上我可以解决它,并且可能能够将其转换为天真的算法.沿着列表,我们看到1-5相交,5-7相交,#5与两组相交.

我想要的结果只是子集,因为它给了我关于基数的信息,只要它们都相交,我就可以轻松地计算集合的交集.在上面的例子中,它将是[[14, 27],[15, 22],[12, 25],[17, 21],[20, 65]].

在我的脑海中,我可能会尝试将每个范围转换为图形节点,连接相交的图形节点,并找到最大的完全连接图形.

我也在思考迭代地从头开始,继续建立一个相交范围的列表,每个交叉范围都有一个运行的交叉点来检查 - 直到你碰到一个不相交的元素,然后开始一个新的列表.继续针对现有交叉点检查每个项目.但是我不确定这是完整的.

我可以尝试实施某些东西(lang是ruby FWIW),但我很想听听其他人如何解决这个问题,以及最有效和最优雅的方式.

更新:

我认为这是最大集团问题的一个特例,它是NP难的,因此实际上很难.对于近似/实际使用的建议将非常感谢!

另请参阅:http://en.wikipedia.org/wiki/Maximum_clique/查找图表中的所有完整子图

更新2

在这里找到了这个问题的NP-硬度和NP-完整性的一个很好的证明:http://www.cs.bris.ac.uk/~popa/ipl.pdf

看起来这是行的结束.对不起人!我将使用足够好的贪婪近似.谢谢.

如答案所述,我不认为该论文描述了这个问题......我们可能会根据范围提供更多信息.

为什么DOM树奥得preorder,depth-first traversal？

与其他遍历如BFT相比,此设计选择有哪些优势？

我只是在研究DOM标准,并找到了前后的定义:

如果A和B在同一树中并且A以树顺序出现在B之前,则对象A在对象B之前.

如果A和B在同一树中,并且A以树顺序出现在B之后,则对象A跟随对象B.

就像大多数编程范例一样,Web平台具有有限的分层树结构,简称为树.树顺序是预订,深度优先遍历.

我试图找到一种检测给定图G是否具有两个不同的最小生成树的有效方法.我也试图找到一种方法来检查它是否有3种不同的最小生成树.我现在的天真解决方案是运行Kruskal算法一次并找到最小生成树的总重量.稍后,从图中移除边缘并再次运行Kruskal算法,并检查新树的权重是否是原始最小生成树的权重,对于图中的每个边都是如此.运行时是O(| V || E | log | V |),这根本不是很好,我认为有更好的方法.

任何建议都会有所帮助,在此先感谢

如何使用BFS或DFS算法设计算法以确定非连通图的连通分量,该算法必须能够表示每个连通分量的顶点集.

这是我的方法:

1)将所有顶点初始化为未访问.

2)从任意顶点开始对图进行DFS遍历v.如果DFS遍历不访问所有顶点,则返回false.

3)反转所有弧(或找到图的转置或反转)

4)在反转图中将所有顶点标记为未访问.

5)从相同的顶点v开始执行反向图的DFS遍历(与步骤2相同).如果DFS遍历不访问所有顶点,则返回false.否则返回true.

这个想法是,如果每个节点都可以从顶点v到达,并且每个节点都可以到达v,那么图形就是强连接的.在步骤2中,我们检查是否可以从v到达所有顶点.在步骤4中,我们检查所有顶点是否都可以到达v(在反向图中,如果所有顶点都可以从v到达,那么所有顶点都可以到达原始图中的v).

知道如何改进这个解决方案吗？

我有一个对象列表(无向边),如下所示:

pairs = [

 pair:["a2", "a5"],
 pair:["a3", "a6"],
 pair:["a4", "a5"],
 pair:["a7", "a9"]

];

我需要在不同的组中找到所有组件(连接的节点).所以从给定的对中我需要得到:

groups = [
  group1: ["a2", "a5", "a4"],
  group2: ["a3", "a6"],
  group3: ["a7", "a9"]
];

我实际上在这里阅读了一些答案并用Google搜索,这就是我学习它的方法,称为"在图中查找连接的组件",但是找不到任何示例代码.我在Node.js上使用JavaScript,但任何其他语言的样本都会非常有用.谢谢.

我想生成一个有向图,其中包含指定数量的周期及其各自的长度.例如,图表应包含:

2 cycles of the size 3 
1 cycle of the size 5

• 这样的算法是否已经存在？如果没有,那么解决这个问题的方法是什么？详细地,给出以下参数:

  1. 顶点的数量(例如,15)
  2. 组件数量(例如2)
  3. 必须在图中的循环(例如,{3循环,3循环,5循环})

• 我只发现了几种能够检测现有图形中循环的算法(例如,Tarjan).您是否认为可以使用循环检测算法生成具有特定循环量的图形？