代码之家 › 专栏 › 技术社区 › user2754673

检查每一位都处于某个周期

graph-theory algorithm c

user2754673 · 技术社区 · 9 年前

我正在编写一个模型,其中:

节点表示为长度为10的位向量,每个位向量表示一些分子,边缘可以将源处存在的任何分子带到目标节点。

例如

S_节点:0b0100000011//节点上存在分子0、1、8

One_Edge:0b0000000010//分子1处于边缘

我必须强制执行以下条件 边缘上的每一个传出分子都会以某个周期返回源节点 分子必须在循环中返回,这意味着在循环的路径中,它必须存在于它所走的每个节点和每个边缘上。 *允许平行边。

分子1采取路径S_ Node->节点_1->节点_2…->S_节点。因此,分子1从边缘的S_Node出发,穿过节点_1…然后循环返回S_Node。因此,这个分子满足条件。类似地,我必须检查每个边缘上的每个分子。

我正在以一种微不足道的可能方式检查每个节点有哪些可能的边出去,然后检查每个边有哪些可能存在的位,并强制每个节点在某个周期内返回。

for  (i = 0; i < N; i++) {       // for each Node 
  for (j = 0; j < E; j++) {      // for each Edge going out frm node i
  // Lets say we have some way of finding E  
      if(edgeWeight & (1 << j)) {    //All outgoing bits
           // Enforcing that each will come  back 
           // On some Cycle

很容易看出,我必须遍历所有节点,然后遍历所有边,然后对这些边上的每一位,都必须编写代码来执行相同的操作。强制本身必须至少迭代no.Of Nodes#N。

有什么更好的方法可以有效地做到这一点?在图论中有没有其他方法来检查同样的东西?谢谢

2 回复 | 直到 9 年前

wich 9 年前

你似乎每个分子(每比特)都有一个有向图,只需做你的技巧,检查每个分子是否有任何非循环。

你可以用一种简单的方法来检查周期,另一种选择是 strongly connected components 你本质上希望每个子图(对于给定分子)都是一个图 connected component 实际上是强连接的。对于强连接组件,有一些很好的算法可以参考前面链接到的维基百科文章。

btilly 9 年前

节点的表示与问题无关。你有一个有向图。您希望验证每个节点和边是否存在包含该边的循环。并且您希望在这方面有合理的效率(而不是从所有边缘对所有可能的循环进行暴力搜索)。

这是一个观察。假设你在图中找到一个循环 G 。请考虑图表 G' 这与原始图形相同,只是循环已被分解为单个节点。你的问题的答案 G 与您问题的答案相同 G’ 因为任何循环 G 导致循环 G’ (可能是一个自交的循环,可以分成两个循环) G’ 导致循环 G (如果您点击了折叠的节点,则按照其循环,直到找到要继续的退出点)。

所以现在的问题从暴力发现循环到崩溃循环,直到你有一个很容易回答问题的小图表。因此,对于每个节点,对于每个边,都会开始一条路径。您的路径将继续,直到您发现循环。任何循环。(不必返回到原始节点!)折叠该循环,并继续行进,直到您必须回溯(在这种情况下,您的条件不满足),或者您设法循环回原始节点,折叠该循环并移动到另一条边。

如果你实现了这一点,你将有一个多项式算法,但不是你能做的最好的。问题是,在循环崩溃的情况下创建新的图是一项昂贵的操作。但有一个窍门是有用的。与其每次找到循环时都折叠图表,不如试着对它懒惰一点。为该循环创建一个新的“假节点”,并将该循环中的每个节点标记为指向该假节点。每次看到指向节点的边时,都要递归搜索这些映射到找到的最塌陷的节点,并将搜索中看到的所有内容标记为直接映射到那里。

如果你很好地实现了lazy位,你的整个算法应该会结束 O(E) 哪里 E 是图形中的边数。考虑到无论做什么,你都必须走遍每一个边缘,你实际上做得再好不过了。