DFS算法

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

#define MAX_VERTEX_NUM 20
#define TRUE 1
#define FALSE 0

typedef char VertexType;

// 边节点（邻接表）
typedef struct ArcNode {
    int adjvex;               // 邻接顶点下标
    struct ArcNode* nextarc;  // 下一条边
} ArcNode;

// 顶点节点
typedef struct VNode {
    VertexType data;          // 顶点信息
    ArcNode* firstarc;        // 第一条边指针
} VNode, AdjList[MAX_VERTEX_NUM];

// 图结构
typedef struct {
    AdjList vertices;         // 顶点数组
    int vexnum, arcnum;       // 顶点数、边数
} ALGraph;

int visited[MAX_VERTEX_NUM];  // 访问标记数组


/**
 * @brief DFS核心算法（递归实现，邻接表存储）
 * 算法描述：
 * 1. 访问当前顶点v，标记为已访问；
 * 2. 遍历v的所有邻接顶点w；
 * 3. 若w未访问，则递归对w执行DFS；
 * 4. 递归终止条件：当前顶点的所有邻接顶点均已访问。
 */
void DFS(ALGraph G, int v) {
    printf("%c ", G.vertices[v].data);  // 访问顶点v
    visited[v] = TRUE;                  // 标记为已访问

    ArcNode* p = G.vertices[v].firstarc;  // 指向第一条邻接边
    while (p) {  // 遍历所有邻接顶点
        int w = p->adjvex;
        if (!visited[w]) {  // 若未访问，递归深入
            DFS(G, w);
        }
        p = p->nextarc;  // 下一个邻接顶点
    }
}

/**
 * @brief DFS全图遍历（处理非连通图）
 * 算法描述：对所有未访问的顶点，逐个执行DFS，确保所有连通分量都被遍历。
 */
void DFSTraverse(ALGraph G) {
    // 初始化访问标记
    for (int v = 0; v < G.vexnum; v++) {
        visited[v] = FALSE;
    }
    // 对每个未访问顶点执行DFS
    for (int v = 0; v < G.vexnum; v++) {
        if (!visited[v]) {
            DFS(G, v);
        }
    }
}

// 打印图的邻接表结构（与BFS代码一致，方便对比）
void PrintGraph(ALGraph G) {
    printf("\n图的结构（邻接表）：\n");
    for (int i = 0; i < G.vexnum; i++) {
        printf("顶点 %c -> ", G.vertices[i].data);
        ArcNode* p = G.vertices[i].firstarc;
        while (p) {
            printf("%c ", G.vertices[p->adjvex].data);
            p = p->nextarc;
        }
        printf("\n");
    }
}

int main() {
    // 构建与BFS相同的图（4个顶点A、B、C、D，边A-B、A-C、B-D）
    ALGraph G;
    G.vexnum = 4;
    G.arcnum = 3;
    G.vertices[0].data = 'A';
    G.vertices[1].data = 'B';
    G.vertices[2].data = 'C';
    G.vertices[3].data = 'D';

    // 构建无向图的邻接表（双向边）
    ArcNode* ab = (ArcNode*)malloc(sizeof(ArcNode));
    ab->adjvex = 1; ab->nextarc = NULL;
    G.vertices[0].firstarc = ab;

    ArcNode* ac = (ArcNode*)malloc(sizeof(ArcNode));
    ac->adjvex = 2; ac->nextarc = G.vertices[0].firstarc;
    G.vertices[0].firstarc = ac;

    ArcNode* bd = (ArcNode*)malloc(sizeof(ArcNode));
    bd->adjvex = 3; bd->nextarc = NULL;
    G.vertices[1].firstarc = bd;

    ArcNode* ba = (ArcNode*)malloc(sizeof(ArcNode));
    ba->adjvex = 0; ba->nextarc = G.vertices[1].firstarc;
    G.vertices[1].firstarc = ba;

    ArcNode* ca = (ArcNode*)malloc(sizeof(ArcNode));
    ca->adjvex = 0; ca->nextarc = NULL;
    G.vertices[2].firstarc = ca;

    ArcNode* db = (ArcNode*)malloc(sizeof(ArcNode));
    db->adjvex = 1; db->nextarc = NULL;
    G.vertices[3].firstarc = db;

    // 打印图结构
    PrintGraph(G);

    // 执行DFS遍历（与BFS对比结果）
    printf("\nDFS遍历结果：");
    DFSTraverse(G);  // 输出：A C B D （递归顺序决定，与BFS的逐层顺序不同）

    return 0;
}

算法描述总结

DFS（深度优先搜索）是一种深度优先的图遍历算法，核心逻辑基于递归（或栈） 实现“先深入探索，再回溯”的访问顺序：

1. 初始化：访问起点并标记为已访问；
2. 递归深入：对当前顶点的每个未访问邻接顶点，递归执行DFS（深入探索）；
3. 回溯过程：当一个顶点的所有邻接顶点均被访问，自动回溯到上一层顶点，继续探索其他未访问邻接顶点；
4. 非连通图兼容：通过外层循环遍历所有未访问顶点，确保所有连通分量都被处理。

时空复杂度分析

时间复杂度

对于邻接表存储的图，每个顶点被访问一次（时间复杂度 ​O(V)），每条边被遍历一次（时间复杂度 ​O(E)）

因此总时间复杂度为 ​\boxed{O(V+E)}（其中 ​V 为顶点数，​E 为边数）。

空间复杂度

主要开销来自递归栈和访问标记数组：

• 递归栈的深度取决于图的深度（最坏情况为线性链，栈深等于顶点数），空间复杂度 ​O(V)；
• 访问标记数组 visited 的空间复杂度为 ​O(V)； 因此总空间复杂度为 ​\boxed{O(V)}。

与BFS的核心区别

遍历顺序：DFS优先深入一条路径到底（如 A→C→回溯→A→B→D），BFS逐层扩散（如 A→B→C→D）； -

数据结构：DFS基于递归栈（或显式栈），BFS基于队列； -

应用场景：DFS适合拓扑排序、连通分量检测等，BFS适合最短路径（无权图）等。 上述代码与BFS代码使用相同的图结构，可直观对比两种算法的遍历结果差异。