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

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实现图的拓扑排序的示例。通过这些步骤，你可以轻松地对有向无环图进行排序，从而更好地管理依赖关系和任务执行顺序。

转载地址：http://lpifk.baihongyu.com/