圖

基礎(chǔ)知識

圖由頂點(vertex)和邊(edge)組成，通常表示為G=(V,E)

頂點集 V 又窮且非空

任意兩個頂點之間，都可以用邊來表示他們的關(guān)系，邊集 E 可以為空

有向圖

有向圖的邊是有明確方向的

有向無環(huán)圖（DAG）

如果一個有向圖，從任意頂點出發(fā)，無法經(jīng)過若干點邊回到該頂點，那么就為有向無環(huán)圖

出度 入度

出度和入度適用于有向圖

出度：一個頂點的出度為 X，指的是有 X 條邊以該頂點為起點

入度：一個頂點的入度為 X，指的是有 X 條邊以該頂點為終點

無向圖

無向圖的邊是沒有方向的

混合圖

混合圖的邊可以是有方向的，也可以是無方向的

平行邊

在無向圖中，關(guān)聯(lián)一對頂點的無向邊如果大于一條，則稱這些邊為平行邊

在有向圖中，關(guān)聯(lián)一對頂點的有向邊數(shù)量如果大于一，并且他們的方向是相同的，那么這些邊為平行邊

多重圖

有平行邊或者有自環(huán)的圖

簡單圖

既沒有平行邊也沒有自環(huán)的圖

無向完全圖

無向完全圖的任意兩個頂點之間都存在邊

n 個頂點的無向完全圖有n(n-1)/2條邊

有向完全圖

有向完全圖的任意兩個頂點之間都存在方向相反的兩條邊
n個頂點的有向完全圖，有n(n-1)條邊

有權(quán)圖

有權(quán)圖的邊可以擁有權(quán)值

連通圖

如果頂點 x 和 y 之間存在可以相互抵達的路徑（直接或者間接的路徑），則 x 和 y 是連通的

如果無向圖G中，任意兩個頂點都是連通的，則G為連通圖

連通分量

連通分量：無向圖中的極大連通子圖

連通圖只有一個連通分量，是它本身。

非連通的無向圖有多個連通分量

強連通圖

如果有向圖G中，任意兩個頂點都是連通的，則為強連通圖

強連通分量

強連通分量：有向圖的極大強連通子圖

強連通圖只有一個強連通分量，他本身，非強連通的有向圖有多個強連通分量

圖的遍歷

從圖中某一頂點出發(fā)訪問圖中其余頂點，且每個頂點僅被訪問一次

廣度優(yōu)先搜索（Breadth First Search,BFS)，又稱寬度優(yōu)先搜索，橫向優(yōu)先搜索

如之前的二叉樹遍歷，就是廣度優(yōu)先搜索，一層一層遍歷

深度優(yōu)先搜索(Depth First Search,DFS)

二叉樹的前序遍歷，就相當于深度優(yōu)先搜索,根左右

拓撲排序

代碼

接口：

//
//  SCXGraph.h
//  TestArithmetic
//
//  Created by 孫承秀 on 2020/8/2.
//  Copyright ? 2020 孫承秀. All rights reserved.
//

#import <Foundation/Foundation.h>

NS_ASSUME_NONNULL_BEGIN

/// V:頂點 E:邊
@interface SCXGraph<V,E> : NSObject

/// 頂點數(shù)
- (NSUInteger)verticesSize;

/// 邊的個數(shù)
- (NSUInteger)edgesSize;

/// 添加頂點
/// @param v 頂點
- (void)addVertex:(V)v;

/// 添加邊
/// @param from 邊的起點
/// @param to 邊的終點
- (void)addEdge:(V)from to:(V)to;

/// 添加邊，帶有權(quán)重
/// @param from 邊的起點
/// @param to 邊的終點
/// @param weight 權(quán)值
- (void)addEdge:(V)from to:(V)to weigth:(E)weight;

/// 移除頂點
/// @param v 要移除的頂點
- (void)removeVertex:(V)v;

/// 移除一條邊
/// @param from 邊的起點
/// @param to 邊的終點
- (void)removeEdge:(V)from to:(V)to;

/// 打印圖
- (void)printGraph;

/// 廣度優(yōu)先搜索
/// @param begin 遍歷的起始節(jié)點
- (void)BFS:(V)begin;

/// 深度優(yōu)先搜索
/// @param begin 遍歷的起始節(jié)點
- (void)DFS:(V)begin;


/// 拓撲排序
- (NSArray *)topologicalSort;
@end

NS_ASSUME_NONNULL_END

實現(xiàn)：

//
//  SCXListGraph.m
//  TestArithmetic
//
//  Created by 孫承秀 on 2020/8/2.
//  Copyright ? 2020 孫承秀. All rights reserved.
//

#import "SCXListGraph.h"
#import "SCXCircleArrayQueue.h"
#import "SCXStack.h"
#import "SCXCircleArrayQueue.h"
#pragma mark - vertex
@class SCXGraphEdge;
/// 圖的頂點：V->SCXGraphVertex
@interface SCXGraphVertex<V,E> : NSObject<NSCopying>

/// 頂點的值
@property (nonatomic,strong) V vertex;

/// 所有以該頂點為終點的邊,入度的邊
@property (nonatomic , strong)NSHashTable<SCXGraphEdge *> *inEdges;

/// 所有以該頂點為起點的邊，出度的邊
@property (nonatomic , strong)NSHashTable<SCXGraphEdge *> *outEdges;

- (instancetype)initWithVertex:(V)vertex;

@end

@implementation SCXGraphVertex
// 這樣就可以這個對象當做key放到字典中了。
- (id)copyWithZone:(NSZone *)zone {
    SCXGraphVertex *ver = [[SCXGraphVertex alloc] init];
//    ver.inEdges = self.inEdges;
//    ver.outEdges = self.outEdges;
    ver.vertex = self.vertex;
    return ver;
}
- (instancetype)initWithVertex:(id)vertex{
    if (self = [super init]) {
        self.vertex = vertex;
        self.inEdges = [NSHashTable hashTableWithOptions:(NSPointerFunctionsStrongMemory)];
        self.outEdges = [NSHashTable hashTableWithOptions:NSPointerFunctionsStrongMemory];
    }
    return self;
}
/// 頂點的值相等就認為是一個頂點
- (BOOL)isEqual:(id)object{
    SCXGraphVertex *vertex = (SCXGraphVertex *)object;
    return [vertex.vertex isEqual:self.vertex];
}
- (NSUInteger)hash{
    return [super hash];
}
- (NSString *)description{
    return self.vertex;
}
@end



#pragma mark - edge

/// 圖的邊：E->SCXGraphEdge
@interface SCXGraphEdge<V,E> : NSObject
// 邊的權(quán)重
@property (nonatomic , strong) E weigth;
// 邊的起點
@property (nonatomic , strong) SCXGraphVertex<V , E> *from;

/// 邊的終點
@property (nonatomic , strong) SCXGraphVertex<V , E> *to;

@end

@implementation SCXGraphEdge

- (instancetype)initWithFrom:(id)from to:(id)to{
    if (self = [super init]) {
        self.from = from;
        self.to = to;
    }
    return self;
}

/// 邊的起點和終點相等，就認為是同一條邊
- (BOOL)isEqual:(id)object{
    SCXGraphEdge *edge = (SCXGraphEdge *)object;
    return [self.from isEqual:edge.from] && [self.to isEqual:edge.to];
}
- (NSUInteger)hash{
    return self.from.hash ^ self.to.hash;
}
- (NSString *)description{
    return [NSString stringWithFormat:@"from:%@,to:%@,weigth:%@",self.from,self.to,self.weigth];
}
@end

#pragma mark - graph
@interface SCXListGraph ()

/// 所有頂點的集合,v->SCXGraphVertex，一個頂點對應(yīng)一個對象
@property (nonatomic , strong) NSMapTable<id , SCXGraphVertex *> *vertices;

/// 存放所有的邊
@property (nonatomic , strong) NSHashTable<SCXGraphEdge *> *edges;
@end
@implementation SCXListGraph
- (instancetype)init{
    if (self = [super init]) {
        self.vertices = [NSMapTable mapTableWithKeyOptions:(NSPointerFunctionsStrongMemory) valueOptions:(NSPointerFunctionsStrongMemory)];
        self.edges = [NSHashTable hashTableWithOptions:NSPointerFunctionsStrongMemory];
    }
    return self;;
}
- (NSUInteger)verticesSize{
    return self.vertices.count;
}
- (NSUInteger)edgesSize{
    return self.edges.count;
}

/// 添加頂點，將頂點全局保存一份，頂點的值為key，value為SCXGraphVertex對象
/// @param v 頂點的值
- (void)addVertex:(id)v{
    if (!v) {
        return;
    }
    if ([self.vertices objectForKey:v]) {
        return;
    }
    [self.vertices setObject:[[SCXGraphVertex alloc] initWithVertex:v] forKey:v];
}

/// 添加邊
/// @param from 邊的起點
/// @param to 邊的終點
- (void)addEdge:(id)from to:(id)to{
    [self addEdge:from to:to weigth:[NSNumber numberWithInteger:NSIntegerMax]];
}
- (void)addEdge:(id)from to:(id)to weigth:(id)weight{
    if (!from || !to) {
        return;
    }
    // 找到之前存在的起點和終點
    SCXGraphVertex *fromVeretex = [self.vertices objectForKey:from];
    SCXGraphVertex *toVeretex = [self.vertices objectForKey:to];
    if (!fromVeretex) {
        fromVeretex = [[SCXGraphVertex alloc] initWithVertex:from];
        [self.vertices setObject:fromVeretex forKey:from];
    }
    if (!toVeretex) {
        toVeretex = [[SCXGraphVertex alloc] initWithVertex:to];
        [self.vertices setObject:toVeretex forKey:to];
    }
    
    // 先找邊，將之前刪除，有可能有邊，但是權(quán)值不同
    SCXGraphEdge *edge = [[SCXGraphEdge alloc] initWithFrom:fromVeretex to:toVeretex];
    edge.weigth = weight;
    // 調(diào)用 isEqual 判斷邊是否相等。
    // 將原來的邊刪除，將新的邊加進去
    // 出
    if ([fromVeretex.outEdges containsObject:edge]) {
        [fromVeretex.outEdges removeObject:edge];
    }
    [fromVeretex.outEdges addObject:edge];
    
    // 入
    if ([toVeretex.inEdges containsObject:edge]) {
        [toVeretex.inEdges removeObject:edge];
    }
    [toVeretex.inEdges addObject:edge];
    
    // 總
    if ([self.edges containsObject:edge]) {
        [self.edges removeObject:edge];
    }
    [self.edges addObject:edge];
}
- (void)removeVertex:(id)v{
    // 先從所有頂點緩存中刪除這個頂點
    SCXGraphVertex *vertex = [self.vertices objectForKey:v];
    if (!vertex) {
        return;
    }
    
    // 刪除和這個頂點有關(guān)的邊
    // 先刪除以這個頂點為起點的邊
    NSEnumerator *outObjEnumerator = vertex.outEdges.objectEnumerator;
    SCXGraphEdge *outEdge;
    while ((outEdge = outObjEnumerator.nextObject) != nil) {
        // 取出每一條邊
        // 取出這條邊之后，將這條邊的終點的頂點，到這個終點的頂點的邊刪除
        [outEdge.to.inEdges removeObject:outEdge];
        [self.edges removeObject:outEdge];
    }
    [vertex.outEdges removeAllObjects];
    // 先刪除以這個頂點為終點的邊
    NSEnumerator *inObjEnumerator = vertex.inEdges.objectEnumerator;
    SCXGraphEdge *inEdge;
    while ((inEdge = inObjEnumerator.nextObject) != nil) {
        // 取出每一條邊
        // 取出這條邊之后，將這條邊的終點的頂點，到這個終點的頂點的邊刪除
        [inEdge.from.outEdges removeObject:inEdge];
        [self.edges removeObject:inEdge];
    }
    [vertex.inEdges removeAllObjects];
    [self.vertices removeObjectForKey:v];
}

/// 移除一條邊
/// @param from 邊的起點
/// @param to 邊的終點
- (void)removeEdge:(id)from to:(id)to{
    // 找到起點和終點對應(yīng)的頂點值
    SCXGraphVertex *fromVertex = [self.vertices objectForKey:from];
    SCXGraphVertex *toVertex = [self.vertices objectForKey:to];
    if (!fromVertex || !toVertex) {
        return;
    }
    
    // 根據(jù)這兩個頂點構(gòu)建一條邊
    // 邊的起點和終點相等，就認為是同一條邊
    SCXGraphEdge *edge = [[SCXGraphEdge alloc] initWithFrom:from to:to];
    if ([fromVertex.outEdges containsObject:edge]) {
        [fromVertex.outEdges removeObject:edge];
    }
    if ([toVertex.inEdges containsObject:edge]) {
        [toVertex.inEdges removeObject:edge];
    }
    if ([self.edges containsObject:edge]) {
        [self.edges removeObject:edge];
    }
}
- (void)BFS:(id)begin{
    // 廣度優(yōu)先搜索，就和之前的二叉樹遍歷一樣，利用隊列，先將一個頂點入隊，然后將這個頂點出對，然后將這個頂點相關(guān)聯(lián)的子節(jié)點，這里是以這個頂點為起點的邊，也就是outEdges里面的邊，依次再入隊，然后這樣循環(huán)下去
    SCXGraphVertex *beginVertex = [self.vertices objectForKey:begin];
    if (!beginVertex) {
        return;
    }
    // 創(chuàng)建隊列
    SCXCircleArrayQueue *queue = [SCXCircleArrayQueue arrayQueue];
    // 入隊
    [queue enqueue:beginVertex];
    // 保存已經(jīng)訪問過的頂點
    NSMutableArray *visitedVertex = [NSMutableArray array];
    [visitedVertex addObject:beginVertex];
    
    while (!queue.isEmpty) {
        // 出對一個
        SCXGraphVertex *v = queue.dequeue;
        NSLog(@"%@",v.vertex);
        
        // 將跟這個頂點有關(guān)的邊入隊
        for (SCXGraphEdge *edge in v.outEdges) {
            if ([visitedVertex containsObject:edge.to]) {
                continue;
            }
            [queue enqueue:edge.to];
            [visitedVertex addObject:edge.to];
        }
    }
}
// 深度優(yōu)先搜索，利用遞歸
- (void)DFS:(id)begin{
    SCXGraphVertex *beginVertex = [self.vertices objectForKey:begin];
    // 防止重復(fù)訪問
    NSMutableArray *visitedVertices = [NSMutableArray array];
    if (!beginVertex) {
        return;
    }
    //    [self DFSrecursion:beginVertex visitedVertices:visitedVertices];
    [self DFSStack:beginVertex visitedVertices:visitedVertices];
}
/// 利用遞歸來實現(xiàn)
- (void)DFSrecursion:(SCXGraphVertex *)vertex visitedVertices:(NSMutableArray *)visited{
    // 沿著根節(jié)點，一直向下找，直到，到底，到底了之后，一次向上回退，然后再找另一個條路徑，也就相當于左右節(jié)點路徑，這里是相當于每一條邊,利用遞歸可以做到，一直向下找，然后回退
    NSLog(@"%@",vertex.vertex);
    [visited addObject:vertex];
    for (SCXGraphEdge *edge in vertex.outEdges) {
        if ([visited containsObject:edge.to]) {
            continue;
        }
        [self DFSrecursion:edge.to visitedVertices:visited];
    }
}
/// 利用棧來實現(xiàn)
- (void)DFSStack:(SCXGraphVertex *)veretex visitedVertices:(NSMutableArray *)visited{
    // 然后將當前節(jié)點添加到已經(jīng)訪問的集合中去
    [visited addObject:veretex];
    // 創(chuàng)建棧
    SCXStack *stack = [[SCXStack alloc] init];
    // 入棧
    [stack push:veretex];
    // 將第一個節(jié)點打印
    NSLog(@"%@",veretex.vertex);
    
    while (!stack.isEmpty) {
        // 出棧
        SCXGraphVertex *cur = [stack pop];
        // 將出棧的這個頂點的from 和 to 入棧，from 入棧的原因是
        // 訪問到頭了的時候，回退，當回退到這個頂點的時候，訪問這個頂點的其余路徑
        // 判斷是否訪問過to，如果訪問過，那么這條路徑就訪問過，如果沒有訪問過就訪問to
        // 從當前節(jié)點依次找每一條路徑，找到一條路徑就break，沿著to繼續(xù)向下找
        for (SCXGraphEdge *edge in cur.outEdges) {
            if ([visited containsObject:edge.to]) {
                continue;
            }
            // from 入棧
            [stack push:edge.from];
            // to 入棧
            [stack push:edge.to];
            // 將to添加到訪問過得節(jié)點中
            [visited addObject:edge.to];
            // 打印to
            NSLog(@"%@",edge.to.vertex);
            // 退出這條路徑，繼續(xù)沿著to訪問
            break;
        }
    }
}
- (void)printGraph{
    NSEnumerator *enumerator = self.vertices.keyEnumerator ;
    id obj;
    NSLog(@"【頂點-------】");
    while ((obj = enumerator.nextObject) != nil) {
        SCXGraphVertex *v = [self.vertices objectForKey:obj];
        NSLog(@"key:%@",obj);
        NSLog(@"outEdges:%@",v.outEdges);
        NSLog(@"inEdgesL%@",v.inEdges);
    }
    NSLog(@"【邊-------】");
    NSEnumerator *edgeEnumerator = self.edges.objectEnumerator;
    SCXGraphEdge *edge ;
    while ((edge = edgeEnumerator.nextObject) != nil) {
        NSLog(@"%@",edge);
    }
}

/// 拓撲排序
/*
 1. 每個頂點只出現(xiàn)依次
 2. 沒有一個節(jié)點指向他節(jié)點的前面
 
 
 1. 先遍歷所有的節(jié)點，將入度為0的節(jié)點，放在q1隊列里面，度不為0的節(jié)點，我們放到一個map里面，key為這個節(jié)點，value為這個節(jié)點的入度
 2. 從隊列q1中取出一個節(jié)點，如果隊列不為空，一直循環(huán)取
 3. 從上面隊列中取出一個度為0的節(jié)點后，放到我們最終要的結(jié)果數(shù)組里面arr1
 4. 拿到所有跟這個頂點有關(guān)的邊，將這些變得終點的入度，減去1，這些頂點其實是都放在上面的map中
 5. 重復(fù)2，3，4
 */
- (NSArray *)topologicalSort{
    // 存放所有度為0的節(jié)點
    SCXCircleArrayQueue *queue = [SCXCircleArrayQueue arrayQueue];
    // 存放除了度為0的節(jié)點之外，其余的所有節(jié)點，key為這個節(jié)點，value為這個節(jié)點的入度
    //    NSMapTable *map = [NSMapTable mapTableWithKeyOptions:(NSPointerFunctionsStrongMemory) valueOptions:NSPointerFunctionsStrongMemory];
    NSMutableDictionary *map = [NSMutableDictionary dictionary];
    // 存放最終的結(jié)果
    NSMutableArray *result = [NSMutableArray array];
    
    // 先找出所有的入度為0的節(jié)點
    NSEnumerator *enumerator = self.vertices.keyEnumerator;
    id key ;
    while ((key = enumerator.nextObject) != nil) {
        SCXGraphVertex *vertex = [self.vertices objectForKey:key];
        NSInteger size = vertex.inEdges.count;
        if (size == 0) {
            [queue enqueue:vertex];
        } else {
            NSNumber *num = [NSNumber numberWithInteger:size];
            [map setValue:num forKey:vertex.vertex];
        }
        
    }
    // 挨個從隊列里面取出入度為0的節(jié)點，將它放到最終的結(jié)果數(shù)組里面去
    while (!queue.isEmpty) {
        SCXGraphVertex *zeroVertex = [queue dequeue];
        // 放到結(jié)果數(shù)組中去
        [result addObject:zeroVertex.vertex];
        
        // 將跟這個頂點有關(guān)的頂點的入度都減去1
        for (SCXGraphEdge *outEdge in zeroVertex.outEdges) {
            SCXGraphVertex *outVertext = outEdge.to;
            NSNumber *priSizeNum = [map objectForKey:outVertext.vertex];
            NSInteger outSize = priSizeNum.integerValue - 1;
            if (outSize == 0) {
                [queue enqueue:outVertext];
            } else {
                [map setValue:[NSNumber numberWithInteger:outSize] forKey:outVertext.vertex];
            }
        }
    }
    
    
    return result.copy;
}
@end

demo