本文共 4011 字，大约阅读时间需要 13 分钟。

Objective-C实现图的拓扑排序

拓扑排序是一种用于对有向无环图（DAG）进行排序的重要算法。它能够帮助我们确定一系列任务的执行顺序，使得每一步都是可以执行的。以下是使用Objective-C实现图的拓扑排序的完整步骤指南。

创建Xcode项目

打开Xcode，选择“File” -> “New” -> “Project”。在弹出的新项目选择器中，选择“macOS”下的“Command Line Tool”模板，点击“Next”。接下来，输入项目名称（例如，命名为“TopologicalSortExample”），选择Objective-C语言，点击“Next”并选择保存位置。

实现图的拓扑排序代码

将以下代码添加到你的项目中，我们将创建一个图类并实现拓扑排序算法。

Step 1：创建Graph.h文件

#import 
   
    
@interface Graph : NSObject
{
    // 节点的数量
    int nodeCount;
    // 边的数量
    int edgeCount;
    // 依赖关系数组，每个节点存储其依赖节点
    NSMutableArray *dependencies;
}
// 初始化图，并添加节点
- (id)initWithNumberOfNodes:(int)nodes;
- (id)initWithNumberOfNodes:(int)nodes withDependsOn:(NSArray *)dependsOn;
- (void)addEdgeFromNode:(int)from toNode:(int)to;
- (void)removeEdgeFromNode:(int)from toNode:(int)to;
- (void)performTopologicalSort;
- (NSArray *)getTopologicalOrder;
@end
   

Step 2：创建Graph.m文件

#import "Graph.h"
@implementation Graph
- (id)initWithNumberOfNodes:(int)nodes
{
    self = [super init];
    self.nodeCount = nodes;
    self.edgeCount = 0;
    self.dependencies = [NSMutableArray new];
    return self;
}
- (id)initWithNumberOfNodes:(int)nodes withDependsOn:(NSArray *)dependsOn
{
    self = [super init];
    self.nodeCount = nodes;
    self.dependencies = [dependsOn mutableCopy];
    self.edgeCount = 0;
    return self;
}
- (void)addEdgeFromNode:(int)from toNode:(int)to
{
    // 添加边的逻辑
    self.edgeCount++;
}
- (void)removeEdgeFromNode:(int)from toNode:(int)to
{
    // 删除边的逻辑
    self.edgeCount--;
}
- (void)performTopologicalSort
{
    // 拓扑排序的实现逻辑
    // 1. 初始化每个节点的入度
    NSMutableArray *inDegree = [NSMutableArray new];
    for (int i = 0; i < self.nodeCount; i++)
    {
        [inDegree addObject:@(0)];
    }
    
    // 2. 构建依赖关系
    for (int i = 0; i < self.nodeCount; i++)
    {
        if (self.dependencies[i])
        {
            for (NSInteger dependant = 0; dependant < self.nodeCount; dependant++)
            {
                if ([self.dependencies[i] containsObject:@(dependant + 1)])
                {
                    [inDegree setObject:@(inDegree[dependant] + 1) forKey:@(i + 1)];
                }
            }
        }
    }
    
    // 3. 找出入度为0的节点
    NSIndexSet *zeroInDegree = [NSIndexSet indexSetWithIndexes:(id)inDegree
                                                     where: ^(NSUInteger index, id value) {
                                                         if ([value intValue] == 0) {
                                                             return index;
                                                         }
                                                     }];
    
    if ([zeroInDegree count] == 0)
    {
        // 不存在拓扑排序的可能路径
        return;
    }
    
    // 4. 初始化结果数组
    NSArray *topologicalOrder = [NSMutableArray new];
    
    // 5. 使用Kahn算法进行拓扑排序
    while (!zeroInDegree.isEmpty)
    {
        // 找出入度为0的节点
        NSInteger index = [zeroInDegree firstIndex];
        [zeroInDegree removeIndex:index];
        
        // 将该节点添加到结果数组
        [topologicalOrder addObject:@(index + 1)];
        
        // 遍历该节点的所有邻接节点
        for (NSInteger i = 0; i < self.nodeCount; i++)
        {
            if ([self.dependencies[i] containsObject:@(index + 1)])
            {
                [inDegree setObject:@(inDegree[i] - 1) forKey:@(i + 1)];
                
                if ([inDegree[inDegree.keyValue] intValue] == 0)
                {
                    [zeroInDegree addIndex:inDegree.keyValue];
                }
            }
        }
    }
    
    // 6. 返回拓扑排序结果
    return [topologicalOrder array];
}
- (NSArray *)getTopologicalOrder
{
    return [self performTopologicalSort];
}

Step 3：使用Graph类

在你的主代码中，创建一个Graph实例并调用拓扑排序方法：

Graph *graph = [[Graph alloc] init];
// 初始化图的节点数和依赖关系
graph.nodeCount = 4;
graph.dependencies = @[
    @[@2],
    @[@3],
    @[@4],
    @[]
];
[graph performTopologicalSort];
NSArray *result = [graph getTopologicalOrder];
NSLog(@"拓扑顺序：%@", result);

以上就是一个完整的Objective-C实现图的拓扑排序的示例。通过这些步骤，你可以轻松地对有向无环图进行排序，从而更好地管理依赖关系和任务执行顺序。