首页 文章

在无向图中查找所有非重叠循环

提问于
浏览 次
3

我需要在无向图上找到所有简单的非重叠循环 . 为了找到所有现有周期，我在这里找到了算法的Objective-C版本：

Finding all cycles in undirected graphs

@interface HSValue : NSObject
@property (nonatomic, assign) CGPoint point;
@end
@implementation HSValue
@end


@interface CyclesFinder ()
@property (nonatomic, strong) NSMutableArray <NSArray<HSValue *>*> *cycles;
@property (nonatomic, strong) NSArray <NSArray<HSValue*>*> *edges;
@end

@implementation CyclesFinder

-(void)findCyclesInGraph:(NSArray <NSArray<HSValue*>*> *)edges {
   self.edges = edges;
   for (NSInteger i=0; i < self.edges.count; i++) {
        for (NSInteger j=0; j < self.edges[i].count; j++) {
            [self findNewCycles:@[self.edges[i][j]]];
        }
    }
}

-(void)findNewCycles:(NSArray <HSValue *> *)path {

    HSValue *startNode = path[0];
    HSValue *nextNode;
    NSArray <HSValue *> *sub;

    for (NSInteger i=0; i < self.edges.count; i++) {
        NSArray <HSValue *> *edge = self.edges[i];
        if ([edge containsObject:startNode]) {
            if ([edge[0] isEqual:startNode]) {
                nextNode = edge[1];
            }
            else {
                nextNode = edge[0];
            }
        }
        else {
            nextNode = nil;
        }

        if (![path containsObject:nextNode] && nextNode) {
            sub = @[nextNode];
            sub = [sub arrayByAddingObjectsFromArray:path];
            [self findNewCycles:sub];
        }
        else if (path.count > 2 && [nextNode isEqual:path.lastObject]) {
            if (![self cycleExist:path]) {
                [self.cycles addObject:path];
                break;
            }
        }
    }
}

-(BOOL)cycleExist:(NSArray <HSValue*> *)path {
    path = [path sortedArrayUsingSelector:@selector(compare:)];
    for (NSInteger i=0; i < self.cycles.count; i++) {
        NSArray <HSValue *> *cycle = [self.cycles[i] sortedArrayUsingSelector:@selector(compare:)];
        if ([cycle isEqualToArray:path]) {
            return TRUE;
        }
    }

    return FALSE;
}

上面的算法工作正常（即使效率不高），它可以从附图上的图表中找到所有可能的周期（请参见下图）：

A-B-H-G-F-D-E-A（有效）

B-C-I-H-B（有效）

G-H-I-L-K-G（有效）

F-G-K-J-F（有效）

F-G-H-I-L-K-J-F（无效）

A-B-C-I-H-G-F-D-E-A（无效）

A-B-C-I-L-K-J-F-D-E-A（无效）

A-B-C-I-H-G-K-J-F-D-E-A（无效）

A-B-H-I-L-K-G-F-D-E-A（无效）

A-B-H-G-K-J-F-D-E-A（无效）

A-B-C-I-L-K-G-F-D-E-A（无效）

B-C-I-L-K-G-H-B（无效）

B-C-I-L-K-J-F-G-H-B（无效）

但是当我运行上面的算法时，我想最终只得到我在左侧示例中用彩色多边形突出显示的周期 . 我不想要的是像右侧示例中的循环 .

enter image description here

我的第一个想法是重叠循环将是一个包含来自任何其他循环的所有点的循环，但这并非总是如此 . 有人能指出我正确的方向吗？是否有可能修改上述算法，以便它只找到非重叠的循环，或者如果不能找到所有循环来过滤它们后我应该做什么？

ios objective-c algorithm graph cycle

2 回答

  • 0

    在无向图本身中没有足够的信息来确定哪些周期 . 例如，请考虑以下2个图表生成相同的无向图：

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

    但是对于左侧的图表，您需要循环ABDCA和CDFEC，而对于右侧的图表，您需要循环ABDCA和EFDBACE . 因此，从图中推断出的无向图是不够的 - 您需要以某种方式合并原始图中的空间信息 .

    回复于
  • 2

    我正在研究同样的问题，你的很多评论都很有帮助，特别是评论说所有边都会在每一边都有一个区域 . 因此，您可以说每条边都有一个“左侧区域”和一个“右侧区域” .

    您可以按任何顺序将所有图形边添加到队列中 . 窥视第一个边缘，选择靠近原点的顶点 . 移动到逆时针最多的邻居 . 继续这个直到你到达起始顶点 . 所有这些边缘都绑定了您的第一个区域 . 我会给它一个唯一的ID并将其分配给那些边缘的“左侧区域”属性 .

    查看队列中的第一个边缘并检查它是否有“左侧区域” . 如果它没有以顺时针方式进行并找到正确的区域，它会检查它是否有“正确的区域” . 如果它分配了两个区域，则将其取出并 grab 下一个区域 .

    应该是O（e v）这么快，对吗？

    这是一点意识流，但我想把它写下来 . 我将为我的实际应用程序编写算法，并且当我发现问题时我将进行调整 .

    当然我愿意接受反馈和建议:)

    回复于

相关问题