深度优先搜索算法：图遍历的经典策略

算法原理

深度优先搜索（Depth-First Search, DFS）是一种用于遍历或搜索树或图的算法。它沿着树的深度遍历树的节点，尽可能深地搜索树的分支。当节点v的所有边都已被探测过，搜索将回溯到发现节点v的那条边的起始节点。

基本思想

1. 选择起始节点：从图中的某个节点开始
2. 深度探索：尽可能深地访问未访问的相邻节点
3. 回溯：当当前节点没有未访问的相邻节点时，回退到上一个节点
4. 重复过程：继续探索其他未访问的路径，直到所有可达节点都被访问

遍历过程

DFS使用栈（显式或递归调用栈）来记住要访问的下一个顶点：

1. 将起始顶点压入栈并标记为已访问
2. 从栈顶弹出一个顶点
3. 访问该顶点的所有未访问的相邻顶点，将它们压入栈并标记为已访问
4. 重复步骤2-3，直到栈为空

优缺点分析

优点

1. 内存效率高：相比BFS，DFS的空间复杂度更低
2. 实现简单：递归实现非常直观
3. 路径记录容易：天然保存了从起始到当前节点的路径
4. 适合解空间大的问题：可以快速找到一个解
5. 便于剪枝优化：容易实现各种剪枝策略

缺点

1. 可能陷入无限深度：在无限图或很深的图中可能栈溢出
2. 不保证最短路径：找到的解不一定是最优的
3. 可能错过解：在某些情况下可能走错方向
4. 对于最短路径问题效率低：需要遍历所有可能路径

使用场景

适用场景

1. 拓扑排序：有向无环图的线性排序
2. 连通性检测：检查图的连通分量
3. 路径查找：在迷宫或图中查找路径
4. 强连通分量：Tarjan算法和Kosaraju算法
5. 解决组合问题：排列、组合、子集生成
6. 树的遍历：前序、中序、后序遍历

不适用场景

1. 最短路径问题：BFS更适合无权图的最短路径
2. 层次遍历：需要按层访问节点时
3. 有环图的无限深度搜索：需要特殊处理

C语言实现

基础图结构定义

#include <stdio.h>
#include <stdlib.h>
#include <stdbool.h>
#include <string.h>

#define MAX_VERTICES 100

// 邻接表节点
typedef struct AdjListNode {
    int dest;
    struct AdjListNode* next;
} AdjListNode;

// 邻接表
typedef struct AdjList {
    AdjListNode* head;
} AdjList;

// 图结构
typedef struct Graph {
    int vertices;
    AdjList* array;
} Graph;

// 创建新的邻接表节点
AdjListNode* create_adj_list_node(int dest) {
    AdjListNode* new_node = (AdjListNode*)malloc(sizeof(AdjListNode));
    new_node->dest = dest;
    new_node->next = NULL;
    return new_node;
}

// 创建图
Graph* create_graph(int vertices) {
    Graph* graph = (Graph*)malloc(sizeof(Graph));
    graph->vertices = vertices;
    graph->array = (AdjList*)malloc(vertices * sizeof(AdjList));
    
    for (int i = 0; i < vertices; i++) {
        graph->array[i].head = NULL;
    }
    
    return graph;
}

// 添加边（无向图）
void add_edge(Graph* graph, int src, int dest) {
    // 添加从src到dest的边
    AdjListNode* new_node = create_adj_list_node(dest);
    new_node->next = graph->array[src].head;
    graph->array[src].head = new_node;
    
    // 添加从dest到src的边（无向图）
    new_node = create_adj_list_node(src);
    new_node->next = graph->array[dest].head;
    graph->array[dest].head = new_node;
}

// 添加有向边
void add_directed_edge(Graph* graph, int src, int dest) {
    AdjListNode* new_node = create_adj_list_node(dest);
    new_node->next = graph->array[src].head;
    graph->array[src].head = new_node;
}

/**
 * DFS递归实现
 * @param graph 图结构
 * @param vertex 当前访问的顶点
 * @param visited 访问标记数组
 */
void dfs_recursive(Graph* graph, int vertex, bool visited[]) {
    // 标记当前节点为已访问并打印
    visited[vertex] = true;
    printf("%d ", vertex);
    
    // 递归访问所有未访问的相邻节点
    AdjListNode* current = graph->array[vertex].head;
    while (current != NULL) {
        if (!visited[current->dest]) {
            dfs_recursive(graph, current->dest, visited);
        }
        current = current->next;
    }
}

/**
 * DFS迭代实现（使用显式栈）
 * @param graph 图结构
 * @param start_vertex 起始顶点
 */
void dfs_iterative(Graph* graph, int start_vertex) {
    bool* visited = (bool*)calloc(graph->vertices, sizeof(bool));
    int* stack = (int*)malloc(graph->vertices * sizeof(int));
    int top = -1;
    
    // 将起始顶点压入栈
    stack[++top] = start_vertex;
    
    printf("DFS迭代遍历: ");
    
    while (top >= 0) {
        // 弹出栈顶顶点
        int vertex = stack[top--];
        
        if (!visited[vertex]) {
            visited[vertex] = true;
            printf("%d ", vertex);
            
            // 将所有未访问的相邻顶点压入栈
            AdjListNode* current = graph->array[vertex].head;
            while (current != NULL) {
                if (!visited[current->dest]) {
                    stack[++top] = current->dest;
                }
                current = current->next;
            }
        }
    }
    
    printf("\n");
    free(visited);
    free(stack);
}

/**
 * 查找路径的DFS实现
 * @param graph 图结构
 * @param start 起始顶点
 * @param target 目标顶点
 * @param visited 访问标记数组
 * @param path 路径数组
 * @param path_index 路径索引
 */
bool dfs_find_path(Graph* graph, int start, int target, bool visited[], 
                   int path[], int* path_index) {
    // 添加当前节点到路径
    visited[start] = true;
    path[(*path_index)++] = start;
    
    // 如果找到目标节点
    if (start == target) {
        return true;
    }
    
    // 递归搜索所有相邻节点
    AdjListNode* current = graph->array[start].head;
    while (current != NULL) {
        if (!visited[current->dest]) {
            if (dfs_find_path(graph, current->dest, target, visited, path, path_index)) {
                return true;
            }
        }
        current = current->next;
    }
    
    // 回溯：移除当前节点并标记为未访问
    (*path_index)--;
    visited[start] = false;
    
    return false;
}

/**
 * 检测环的DFS实现
 * @param graph 图结构
 * @param vertex 当前顶点
 * @param visited 访问标记数组
 * @param recursion_stack 递归栈标记数组
 */
bool dfs_has_cycle_directed(Graph* graph, int vertex, bool visited[], bool recursion_stack[]) {
    visited[vertex] = true;
    recursion_stack[vertex] = true;
    
    AdjListNode* current = graph->array[vertex].head;
    while (current != NULL) {
        // 如果相邻节点未访问，递归检查
        if (!visited[current->dest]) {
            if (dfs_has_cycle_directed(graph, current->dest, visited, recursion_stack)) {
                return true;
            }
        }
        // 如果相邻节点在当前递归栈中，存在环
        else if (recursion_stack[current->dest]) {
            return true;
        }
        current = current->next;
    }
    
    recursion_stack[vertex] = false; // 移出递归栈
    return false;
}

/**
 * 无向图环检测
 */
bool dfs_has_cycle_undirected(Graph* graph, int vertex, bool visited[], int parent) {
    visited[vertex] = true;
    
    AdjListNode* current = graph->array[vertex].head;
    while (current != NULL) {
        if (!visited[current->dest]) {
            if (dfs_has_cycle_undirected(graph, current->dest, visited, vertex)) {
                return true;
            }
        }
        // 如果相邻节点已访问且不是父节点，存在环
        else if (current->dest != parent) {
            return true;
        }
        current = current->next;
    }
    
    return false;
}

/**
 * 拓扑排序的DFS实现
 */
void topological_sort_util(Graph* graph, int vertex, bool visited[], int stack[], int* top) {
    visited[vertex] = true;
    
    AdjListNode* current = graph->array[vertex].head;
    while (current != NULL) {
        if (!visited[current->dest]) {
            topological_sort_util(graph, current->dest, visited, stack, top);
        }
        current = current->next;
    }
    
    // 当前节点处理完毕，压入栈
    stack[++(*top)] = vertex;
}

void topological_sort(Graph* graph) {
    int* stack = (int*)malloc(graph->vertices * sizeof(int));
    bool* visited = (bool*)calloc(graph->vertices, sizeof(bool));
    int top = -1;
    
    // 对所有未访问的节点调用DFS
    for (int i = 0; i < graph->vertices; i++) {
        if (!visited[i]) {
            topological_sort_util(graph, i, visited, stack, &top);
        }
    }
    
    printf("拓扑排序结果: ");
    while (top >= 0) {
        printf("%d ", stack[top--]);
    }
    printf("\n");
    
    free(stack);
    free(visited);
}

/**
 * 强连通分量检测（Kosaraju算法的第一步）
 */
void fill_order(Graph* graph, int vertex, bool visited[], int stack[], int* top) {
    visited[vertex] = true;
    
    AdjListNode* current = graph->array[vertex].head;
    while (current != NULL) {
        if (!visited[current->dest]) {
            fill_order(graph, current->dest, visited, stack, top);
        }
        current = current->next;
    }
    
    stack[++(*top)] = vertex;
}

// 创建转置图
Graph* get_transpose(Graph* graph) {
    Graph* transposed = create_graph(graph->vertices);
    
    for (int v = 0; v < graph->vertices; v++) {
        AdjListNode* current = graph->array[v].head;
        while (current != NULL) {
            add_directed_edge(transposed, current->dest, v);
            current = current->next;
        }
    }
    
    return transposed;
}

/**
 * 查找所有路径
 */
void find_all_paths(Graph* graph, int start, int target, bool visited[], 
                   int path[], int path_index, int* path_count) {
    visited[start] = true;
    path[path_index] = start;
    path_index++;
    
    if (start == target) {
        printf("路径 %d: ", ++(*path_count));
        for (int i = 0; i < path_index; i++) {
            printf("%d ", path[i]);
        }
        printf("\n");
    } else {
        AdjListNode* current = graph->array[start].head;
        while (current != NULL) {
            if (!visited[current->dest]) {
                find_all_paths(graph, current->dest, target, visited, path, path_index, path_count);
            }
            current = current->next;
        }
    }
    
    path_index--;
    visited[start] = false;
}

// 测试和演示函数
void print_graph(Graph* graph) {
    printf("图的邻接表表示:\n");
    for (int v = 0; v < graph->vertices; v++) {
        AdjListNode* current = graph->array[v].head;
        printf("顶点 %d: ", v);
        while (current) {
            printf("-> %d ", current->dest);
            current = current->next;
        }
        printf("\n");
    }
    printf("\n");
}

void test_dfs_basic() {
    printf("=== DFS基础遍历测试 ===\n");
    
    Graph* graph = create_graph(5);
    add_edge(graph, 0, 1);
    add_edge(graph, 0, 4);
    add_edge(graph, 1, 2);
    add_edge(graph, 1, 3);
    add_edge(graph, 1, 4);
    add_edge(graph, 2, 3);
    add_edge(graph, 3, 4);
    
    print_graph(graph);
    
    bool* visited = (bool*)calloc(graph->vertices, sizeof(bool));
    
    printf("DFS递归遍历: ");
    dfs_recursive(graph, 0, visited);
    printf("\n");
    
    dfs_iterative(graph, 0);
    
    free(visited);
    printf("\n");
}

void test_path_finding() {
    printf("=== 路径查找测试 ===\n");
    
    Graph* graph = create_graph(6);
    add_edge(graph, 0, 1);
    add_edge(graph, 0, 2);
    add_edge(graph, 1, 3);
    add_edge(graph, 2, 4);
    add_edge(graph, 3, 5);
    add_edge(graph, 4, 5);
    
    bool* visited = (bool*)calloc(graph->vertices, sizeof(bool));
    int* path = (int*)malloc(graph->vertices * sizeof(int));
    int path_index = 0;
    
    int start = 0, target = 5;
    printf("查找从顶点 %d 到顶点 %d 的路径:\n", start, target);
    
    if (dfs_find_path(graph, start, target, visited, path, &path_index)) {
        printf("找到路径: ");
        for (int i = 0; i < path_index; i++) {
            printf("%d ", path[i]);
        }
        printf("\n");
    } else {
        printf("未找到路径\n");
    }
    
    // 重置访问标记
    memset(visited, false, graph->vertices * sizeof(bool));
    int path_count = 0;
    
    printf("\n所有可能的路径:\n");
    find_all_paths(graph, start, target, visited, path, 0, &path_count);
    
    free(visited);
    free(path);
    printf("\n");
}

void test_cycle_detection() {
    printf("=== 环检测测试 ===\n");
    
    // 测试有向图环检测
    Graph* directed_graph = create_graph(4);
    add_directed_edge(directed_graph, 0, 1);
    add_directed_edge(directed_graph, 1, 2);
    add_directed_edge(directed_graph, 2, 3);
    add_directed_edge(directed_graph, 3, 1); // 创建环
    
    printf("有向图:\n");
    print_graph(directed_graph);
    
    bool* visited = (bool*)calloc(4, sizeof(bool));
    bool* rec_stack = (bool*)calloc(4, sizeof(bool));
    
    bool has_cycle = false;
    for (int i = 0; i < 4; i++) {
        if (!visited[i]) {
            if (dfs_has_cycle_directed(directed_graph, i, visited, rec_stack)) {
                has_cycle = true;
                break;
            }
        }
    }
    
    printf("有向图是否有环: %s\n", has_cycle ? "是" : "否");
    
    free(visited);
    free(rec_stack);
    
    // 测试无向图环检测
    Graph* undirected_graph = create_graph(3);
    add_edge(undirected_graph, 0, 1);
    add_edge(undirected_graph, 1, 2);
    add_edge(undirected_graph, 2, 0); // 创建环
    
    printf("\n无向图:\n");
    print_graph(undirected_graph);
    
    visited = (bool*)calloc(3, sizeof(bool));
    has_cycle = false;
    
    for (int i = 0; i < 3; i++) {
        if (!visited[i]) {
            if (dfs_has_cycle_undirected(undirected_graph, i, visited, -1)) {
                has_cycle = true;
                break;
            }
        }
    }
    
    printf("无向图是否有环: %s\n", has_cycle ? "是" : "否");
    
    free(visited);
    printf("\n");
}

void test_topological_sort() {
    printf("=== 拓扑排序测试 ===\n");
    
    Graph* dag = create_graph(6);
    add_directed_edge(dag, 5, 2);
    add_directed_edge(dag, 5, 0);
    add_directed_edge(dag, 4, 0);
    add_directed_edge(dag, 4, 1);
    add_directed_edge(dag, 2, 3);
    add_directed_edge(dag, 3, 1);
    
    printf("有向无环图(DAG):\n");
    print_graph(dag);
    
    topological_sort(dag);
    printf("\n");
}

int main() {
    test_dfs_basic();
    test_path_finding();
    test_cycle_detection();
    test_topological_sort();
    
    return 0;
}

算法应用实例

1. 迷宫求解

#define MAZE_SIZE 5

bool solve_maze(int maze[MAZE_SIZE][MAZE_SIZE], int x, int y, int sol[MAZE_SIZE][MAZE_SIZE]) {
    // 如果到达目标位置
    if (x == MAZE_SIZE - 1 && y == MAZE_SIZE - 1) {
        sol[x][y] = 1;
        return true;
    }
    
    // 检查当前位置是否有效
    if (x >= 0 && x < MAZE_SIZE && y >= 0 && y < MAZE_SIZE && maze[x][y] == 1) {
        sol[x][y] = 1;
        
        // 向右移动
        if (solve_maze(maze, x + 1, y, sol)) return true;
        
        // 向下移动
        if (solve_maze(maze, x, y + 1, sol)) return true;
        
        // 回溯
        sol[x][y] = 0;
    }
    
    return false;
}

2. N皇后问题

bool is_safe(int board[], int row, int col, int n) {
    for (int i = 0; i < row; i++) {
        if (board[i] == col || 
            board[i] - i == col - row || 
            board[i] + i == col + row) {
            return false;
        }
    }
    return true;
}

bool solve_n_queens(int board[], int row, int n) {
    if (row == n) return true;
    
    for (int col = 0; col < n; col++) {
        if (is_safe(board, row, col, n)) {
            board[row] = col;
            if (solve_n_queens(board, row + 1, n)) {
                return true;
            }
        }
    }
    
    return false;
}

复杂度分析

时间复杂度

• 邻接矩阵表示：O(V²) - 需要检查所有顶点对
• 邻接表表示：O(V + E) - 访问所有顶点和边一次

空间复杂度

• 递归实现：O(V) - 递归调用栈深度
• 迭代实现：O(V) - 显式栈和访问标记数组
• 最坏情况：O(V) - 当图是一条链时

实际应用

1. 编译器：语法分析、依赖关系检查
2. 网络分析：检测网络连通性、路由路径
3. 游戏开发：地图探索、AI路径规划
4. 数据库：查询优化、事务依赖分析
5. 社交网络：好友推荐、影响力分析

总结

深度优先搜索是图论中最基础和重要的算法之一。它的简单性和强大的表达能力使其成为解决各种图相关问题的基础工具。通过理解DFS的原理和实现，可以为学习更高级的图算法奠定坚实的基础。

DFS的递归特性使其特别适合解决需要探索所有可能性的问题，而其深度优先的特点则在解决路径查找、拓扑排序等问题时展现出独特的优势。

版权所有，如有侵权请联系我