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

Objective-C 中实现深度优先搜索（DFS）迭代算法

深度优先搜索（DFS）是一种常见的图遍历算法，其核心思想是从图的起点出发，尽可能深入地访问每一个节点，直到无法继续为止。在本文中，我们将使用 Objective-C 语言，通过栈数据结构来实现 DFS 算法。

算法概述

DFS 算法主要通过递归或迭代的方式遍历图的所有节点。与广度优先搜索（BFS）相比，DFS 更注重探索路径的深度。以下是 DFS 算法的基本步骤：

核心实现代码

#import 
   
    
@interface Node : NSObject
@property (nonatomic, strong) NSString *value;
@property (nonatomic, strong) NSArray *neighbors;
@property (nonatomic, assign) bool visited;
@end
@implementation Node
@end
@interface DFSAlgorithm : NSObject
@property (nonatomic, strong) Node *startNode;
@property (nonatomic, strong) NSMutableArray *stack;
@property (nonatomic, strong) NSMutableArray *visitedNodes;
- (void)performDFS;
- (void)visitNode:(Node *)node;
- (void)pushNeighborsToStack:(Node *)node;
@end
@implementation DFSAlgorithm
- (void)performDFS {
    self.stack = [NSMutableArray new];
    self.visitedNodes = [NSMutableArray new];
    
    [self visitNode:self.startNode];
}
- (void)visitNode:(Node *)node {
    node.visited = true;
    [self pushNeighborsToStack:node];
    
    while ([self.stack count] > 0) {
        Node *currentNode = [self.stack lastObject];
        [self.stack removeLast];
        
        for (Node *neighbor in currentNode.neighbors) {
            if (!neighbor.visited) {
                [self.stack push:neighbor];
                [self visitNode:neighbor];
            }
        }
    }
}
- (void)pushNeighborsToStack:(Node *)node {
    for (Node *neighbor in node.neighbors) {
        if (!neighbor.visited) {
            [self.stack push:neighbor];
        }
    }
}
@end
   

代码解释

使用示例

// 创建节点
Node *node1 = [[Node alloc] init];
node1.value = @"节点1";
node1.neighbors = [@["节点2"]];
Node *node2 = [[Node alloc] init];
node2.value = @"节点2";
node2.neighbors = [@["节点3", "节点4"]];
Node *node3 = [[Node alloc] init];
node3.value = @"节点3";
node3.neighbors = [@["节点4"]];
Node *node4 = [[Node alloc] init];
node4.value = @"节点4";
node4.neighbors = [@[]];
// 初始化 DFS 算法
DFSAlgorithm *dfs = [[DFSAlgorithm alloc] init];
dfs.startNode = node1;
// 开始 DFS 遍历
[dfs performDFS];

测试结果

运行上述代码，DFS 算法将依次访问节点1、节点2、节点3、节点4，完成整个图的遍历。栈中的操作确保了 DFS 的正确性。

总结

通过上述实现，我们可以清晰地看到 DFS 算法的核心逻辑。通过栈结构来管理遍历顺序，确保了深度优先的特性。这种方法适用于各种图的遍历任务，能够有效地展开节点的访问路径。