當(dāng)前位置：首頁 > 编程资源 > 综合教程 >内容正文

综合教程

算法-无向图(连通分量，是否有环和二分图)

發(fā)布時間：2023/12/15 综合教程 25 生活家

生活随笔收集整理的這篇文章主要介紹了算法-无向图(连通分量，是否有环和二分图) 小編覺得挺不錯的,現(xiàn)在分享給大家,幫大家做個參考.

前面的文章實(shí)現(xiàn)了無向圖深度優(yōu)先搜索和廣度優(yōu)先搜索解決了無向圖中的路徑尋找，不過無向圖中還有幾個比較常見的問題需要解決，判斷圖中的連通分量，在無向圖中，如果從頂點(diǎn)vi到頂點(diǎn)vj有路徑，則稱vi和vj連通。如果圖中任意兩個頂點(diǎn)之間都連通，則稱該圖為連通圖，否則，稱該圖為非連通圖，則其中的極大連通子圖稱為連通分量，這里所謂的極大是指子圖中包含的頂點(diǎn)個數(shù)極大。

連通分量

為了編程和理解，我們還是使用之前文章的非連通圖，如下圖所示，圖中有三個連通分量，看著這個圖對照上文中的概念比較好理解:

代碼中跟深度優(yōu)先搜索有所改動，需要一個新的數(shù)組存儲對應(yīng)的值，數(shù)組中0-6都屬于一個連通分量，那么我們可以將數(shù)組中索引在0-6之間的變量賦值為0，代碼如下:

@interface GraphCC : NSObject

//記錄頂點(diǎn)是否被標(biāo)記
@property  (strong,nonatomic)  NSMutableArray  *marked;

@property (assign,nonatomic)  NSInteger count;//連通的分量

@property  (strong,nonatomic)  NSMutableArray  *ids;//頂點(diǎn)所在的連通分量的標(biāo)識符

//連通分量遞歸初始化
-(instancetype)initWithGraph:(Graph *)graph;

-(void)depthSearch:(Graph *)graph  vertex:(NSInteger)vertex;


@end

實(shí)現(xiàn)代碼如下:

@implementation GraphCC

#pragma mark  getter and setter
-(NSMutableArray *)marked{
    if (!_marked) {
        _marked=[[NSMutableArray alloc]initWithCapacity:1];
    }
    return _marked;
}

-(NSMutableArray *)ids{
    if (!_ids) {
        _ids=[[NSMutableArray alloc]initWithCapacity:1];
    }
    return _ids;
}

-(instancetype)initWithGraph:(Graph *)graph{
    self=[super init];
    if (self) {
        for (NSInteger i=0; i<graph.vertexs;i++) {
            [self.marked addObject:[NSNull null]];
            [self.ids addObject:[NSNull null]];
        }
        //遍歷圖的頂點(diǎn)
        for (NSInteger j=0; j<graph.vertexs; j++) {
            if (![self isMarked:j]) {
                [self depthSearch:graph vertex:j];
                self.count++;
            }
        }
    }
    return self;
}
//博客園-FlyElephant:http://www.cnblogs.com/xiaofeixiang/
-(void)depthSearch:(Graph *)graph vertex:(NSInteger)vertex{
    self.marked[vertex]=[NSNumber numberWithBool:true];
    //同一分量中頂點(diǎn)的賦值
    self.ids[vertex]=[NSNumber numberWithInteger:self.count];
    for (NSInteger i=0; i<[graph.adjDataSource[vertex] count]; i++) {
        NSInteger temp=[[graph.adjDataSource[vertex] objectAtIndex:i] integerValue];
        if (![self isMarked:temp]) {
            [self depthSearch:graph vertex:temp];
        }
    }
}

-(Boolean)isMarked:(NSInteger)vertex{
    return self.marked[vertex]==[NSNull null]?false:[self.marked[vertex] boolValue];
}

@end

測試代碼:

        Graph  *graph=[[Graph alloc]initWithVertex:13];
        [graph addEdges:0 endVertex:1];
        [graph addEdges:0 endVertex:2];
        [graph addEdges:0 endVertex:5];
        [graph addEdges:0 endVertex:6];
        [graph addEdges:3 endVertex:4];
        [graph addEdges:3 endVertex:5];
        [graph addEdges:4 endVertex:5];
        [graph addEdges:4 endVertex:6];
        [graph addEdges:7 endVertex:8];
        [graph addEdges:9 endVertex:10];
        [graph addEdges:9 endVertex:11];
        [graph addEdges:9 endVertex:12];
        [graph addEdges:11 endVertex:12];
        GraphCC  *graphCC=[[GraphCC alloc]initWithGraph:graph];
        for (NSInteger i=0; i<graphCC.count; i++) {
            NSMutableArray  *dataSource=[[NSMutableArray alloc]initWithCapacity:1];
            for (NSInteger j=0; j<graph.vertexs; j++) {
                if ([graphCC.ids[j] integerValue]==i) {
                    [dataSource addObject:[NSNumber numberWithInteger:j]];
                }
            }
            NSLog(@"分量%ld:%@",i,[dataSource componentsJoinedByString:@"--"]);
        }

效果如下:

是否有環(huán)

環(huán)簡單就是幾個頂點(diǎn)之間是否存在閉合，從頂點(diǎn)1通過若干個頂點(diǎn)是否可以返回到頂點(diǎn)1，此次判斷通過之前文章的一個連通圖:

@interface GraphCycle : NSObject

//記錄頂點(diǎn)是否被標(biāo)記
@property  (strong,nonatomic)  NSMutableArray  *marked;

@property (assign,nonatomic)  Boolean hasCycle;
//初始化
-(instancetype)initWithGraph:(Graph *)graph;

-(void)depthSearch:(Graph *)graph  vertex:(NSInteger)vertex nextVertex:(NSInteger)nextVertex;

@end

實(shí)現(xiàn)代碼:

@implementation GraphCycle
#pragma mark  getter and setter
-(NSMutableArray *)marked{
    if (!_marked) {
        _marked=[[NSMutableArray alloc]initWithCapacity:1];
    }
    return _marked;
}


-(instancetype)initWithGraph:(Graph *)graph{
    self=[super init];
    if (self) {
        for (NSInteger i=0; i<graph.vertexs;i++) {
            [self.marked addObject:[NSNull null]];
        }
        //遍歷圖的頂點(diǎn)
        for (NSInteger s=0; s<graph.vertexs; s++) {
            if (![self isMarked:s]) {
                [self depthSearch:graph vertex:s nextVertex:s];
            }
        }
    }
    return self;
}
//http://www.cnblogs.com/xiaofeixiang/
-(void)depthSearch:(Graph *)graph vertex:(NSInteger)vertex nextVertex:(NSInteger)nextVertex{
    self.marked[vertex]=[NSNumber numberWithBool:true];
    for (NSInteger i=0; i<[graph.adjDataSource[vertex] count]; i++) {
        NSInteger temp=[[graph.adjDataSource[vertex] objectAtIndex:i] integerValue];
        if (![self isMarked:temp]) {
            [self depthSearch:graph vertex:temp nextVertex:vertex];
        }
        //最開始檢測到的環(huán)是0-1-2
        else if (temp!=nextVertex) self.hasCycle=true;
    }
}

-(Boolean)isMarked:(NSInteger)vertex{
    return self.marked[vertex]==[NSNull null]?false:[self.marked[vertex] boolValue];
}

@end

測試代碼:

        Graph  *graph=[[Graph alloc]initWithVertex:6];
        [graph addEdges:0 endVertex:5];
        [graph addEdges:2 endVertex:4];
        [graph addEdges:2 endVertex:3];
        [graph addEdges:1 endVertex:2];
        [graph addEdges:0 endVertex:1];
        [graph addEdges:3 endVertex:4];
        [graph addEdges:5 endVertex:3];
        [graph addEdges:0 endVertex:2];
        GraphCycle *cycle=[[GraphCycle alloc]initWithGraph:graph];
        if ([cycle hasCycle]) {
            NSLog(@"圖中含有環(huán)");
        }else{
            NSLog(@"圖中不含有環(huán)");
        }
        NSLog(@"技術(shù)交流群:%@",@"228407086");
        NSLog(@"原文地址:http://www.cnblogs.com/xiaofeixiang");

測試效果:

二分圖

我們也許會看到過這么一個問題就是是否能夠用兩種顏色將圖中的所有頂點(diǎn)著色，，使得任意一條邊的兩個點(diǎn)都不相同，其實(shí)這個問題等價于圖是否是二分圖：

@interface GraphTwoColor : NSObject

//標(biāo)記數(shù)組
@property  (strong,nonatomic)  NSMutableArray  *marked;

@property  (strong,nonatomic)  NSMutableArray  *color;

@property (assign,nonatomic)  Boolean isTwoColorable;
//初始化
-(instancetype)initWithGraph:(Graph *)graph;
//深度搜索
-(void)depthSearch:(Graph *)graph  vertex:(NSInteger)vertex;


@end

實(shí)現(xiàn)代碼:

@implementation GraphTwoColor
#pragma mark  getter and setter
-(NSMutableArray *)marked{
    if (!_marked) {
        _marked=[[NSMutableArray alloc]initWithCapacity:1];
    }
    return _marked;
}

-(NSMutableArray *)color{
    if (!_color) {
        _color=[[NSMutableArray alloc]initWithCapacity:1];
    }
    return _color;
}


-(instancetype)initWithGraph:(Graph *)graph{
    self=[super init];
    if (self) {
        for (NSInteger i=0; i<graph.vertexs;i++) {
            [self.marked addObject:[NSNull null]];
            [self.color addObject:[NSNull null]];
        }
        self.isTwoColorable=true;
        //遍歷圖的頂點(diǎn)
        for (NSInteger s=0; s<graph.vertexs; s++) {
            if (![self isMarked:s]) {
                [self depthSearch:graph vertex:s];
            }
        }
    }
    return self;
}
//http://www.cnblogs.com/xiaofeixiang/
-(void)depthSearch:(Graph *)graph vertex:(NSInteger)vertex{
    self.marked[vertex]=[NSNumber numberWithBool:true];
    
    for (NSInteger i=0; i<[graph.adjDataSource[vertex] count]; i++) {
        NSInteger temp=[[graph.adjDataSource[vertex] objectAtIndex:i] integerValue];
        if (![self isMarked:temp]) {
            //二分圖兩個相鄰的節(jié)點(diǎn)顏色不一樣
            self.color[temp]=[NSNumber numberWithBool:![self isColor:vertex]];
            [self depthSearch:graph vertex:temp];
        }
        //相鄰的節(jié)點(diǎn)顏色相同則不是二分圖
        else if ([self isColor:temp]==[self isColor:vertex]) self.isTwoColorable=false;
    }
}

-(Boolean)isMarked:(NSInteger)vertex{
    return self.marked[vertex]==[NSNull null]?false:[self.marked[vertex] boolValue];
}

-(Boolean)isColor:(NSInteger)vertex{
    return self.color[vertex]==[NSNull null]?false:[self.color[vertex] boolValue];
}

@end

測試代碼:

        Graph  *graph=[[Graph alloc]initWithVertex:6];
        [graph addEdges:0 endVertex:5];
        [graph addEdges:2 endVertex:4];
        [graph addEdges:2 endVertex:3];
        [graph addEdges:1 endVertex:2];
        [graph addEdges:0 endVertex:1];
        [graph addEdges:3 endVertex:4];
        [graph addEdges:5 endVertex:3];
        [graph addEdges:0 endVertex:2];
        GraphTwoColor  *graphColor=[[GraphTwoColor alloc]initWithGraph:graph];
        if ([graphColor isTwoColorable]) {
            NSLog(@"圖是一個二分圖");
        }else{
            NSLog(@"圖不是一個二分圖");
        }
        NSLog(@"技術(shù)交流群:%@",@"228407086");
        NSLog(@"原文地址:http://www.cnblogs.com/xiaofeixiang");

測試效果:

如果我們修改一下Graph，比如圖只有四個頂點(diǎn)，四條邊，肯定是一個二分圖:

                Graph  *graph=[[Graph alloc]initWithVertex:4];
                [graph addEdges:0 endVertex:1];
                [graph addEdges:0 endVertex:2];
                [graph addEdges:1 endVertex:3];
                [graph addEdges:2 endVertex:3];

總結(jié)

以上是生活随笔為你收集整理的算法-无向图(连通分量，是否有环和二分图)的全部內(nèi)容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網(wǎng)站內(nèi)容還不錯，歡迎將生活随笔推薦給好友。

上一篇： C语言高级编程：数组和指针作为函数形参
下一篇： C语言高级编程：汇编分析i++和++i