跳到主要内容

图的深度优先遍历（DFS）和广度优先遍历（BFS）详解

1. 图的基本定义​

图（Graph）是由顶点（Vertex）和边（Edge）组成的集合。图可以分为无向图和有向图，根据是否带权重可以进一步分为带权图和无权图。

2. 深度优先遍历（DFS）​

定义​

深度优先遍历（Depth First Search, DFS）是一种图的遍历方式，它从一个起始顶点出发，尽可能深地探索每一个分支，直到不能前进为止，然后回溯到上一个顶点继续探索未访问的分支，直至所有顶点都被访问。

操作步骤​

  1. 从起始顶点开始，将该顶点标记为已访问。
  2. 递归地访问所有未被访问的邻接顶点。
  3. 回溯到上一个顶点，继续访问未被访问的邻接顶点。

代码实现（C语言）​

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

#define MAX 100

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

// 图的邻接矩阵表示
typedef struct Graph {
    int vertices;
    int adjMatrix[MAX][MAX];
} Graph;

// 初始化图
void initGraph(Graph* g, int vertices) {
    g->vertices = vertices;
    for (int i = 0; i < vertices; i++) {
        for (int j = 0; j < vertices; j++) {
            g->adjMatrix[i][j] = 0;
        }
    }
}

// 添加边
void addEdge(Graph* g, int src, int dest) {
    g->adjMatrix[src][dest] = 1;
    g->adjMatrix[dest][src] = 1; // 无向图
}

// 深度优先遍历
void DFS(Graph* g, int vertex) {
    visited[vertex] = 1;
    printf("%d ", vertex);

    for (int i = 0; i < g->vertices; i++) {
        if (g->adjMatrix[vertex][i] == 1 && !visited[i]) {
            DFS(g, i);
        }
    }
}

int main() {
    Graph g;
    initGraph(&g, 6);

    addEdge(&g, 0, 1);
    addEdge(&g, 0, 2);
    addEdge(&g, 1, 3);
    addEdge(&g, 1, 4);
    addEdge(&g, 2, 5);

    for (int i = 0; i < 6; i++) {
        visited[i] = 0;
    }

    printf("Depth First Search starting from vertex 0:\n");
    DFS(&g, 0);

    return 0;
}

3. 广度优先遍历（BFS）​

定义​

广度优先遍历（Breadth First Search, BFS）是一种图的遍历方式，它从一个起始顶点出发，首先访问该顶点的所有邻接顶点，然后依次访问这些邻接顶点的邻接顶点，直到所有顶点都被访问。

操作步骤​

  1. 从起始顶点开始，将该顶点标记为已访问，并将其加入队列。
  2. 从队列中取出一个顶点，访问其所有未被访问的邻接顶点，并将这些邻接顶点加入队列。
  3. 重复步骤2，直到队列为空。

代码实现（C语言）​

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

#define MAX 100

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

// 图的邻接矩阵表示
typedef struct Graph {
    int vertices;
    int adjMatrix[MAX][MAX];
} Graph;

// 队列结构定义
typedef struct Queue {
    int items[MAX];
    int front, rear;
} Queue;

// 初始化队列
Queue* createQueue() {
    Queue* q = (Queue*)malloc(sizeof(Queue));
    q->front = -1;
    q->rear = -1;
    return q;
}

// 队列判空
int isEmpty(Queue* q) {
    return q->rear == -1;
}

// 入队
void enqueue(Queue* q, int value) {
    if (q->rear == MAX - 1) {
        printf("Queue is full\n");
    } else {
        if (q->front == -1) q->front = 0;
        q->rear++;
        q->items[q->rear] = value;
    }
}

// 出队
int dequeue(Queue* q) {
    int item;
    if (isEmpty(q)) {
        printf("Queue is empty\n");
        return -1;
    } else {
        item = q->items[q->front];
        q->front++;
        if (q->front > q->rear) {
            q->front = q->rear = -1;
        }
        return item;
    }
}

// 初始化图
void initGraph(Graph* g, int vertices) {
    g->vertices = vertices;
    for (int i = 0; i < vertices; i++) {
        for (int j = 0; j < vertices; j++) {
            g->adjMatrix[i][j] = 0;
        }
    }
}

// 添加边
void addEdge(Graph* g, int src, int dest) {
    g->adjMatrix[src][dest] = 1;
    g->adjMatrix[dest][src] = 1; // 无向图
}

// 广度优先遍历
void BFS(Graph* g, int startVertex) {
    Queue* q = createQueue();
    visited[startVertex] = 1;
    enqueue(q, startVertex);

    while (!isEmpty(q)) {
        int currentVertex = dequeue(q);
        printf("%d ", currentVertex);

        for (int i = 0; i < g->vertices; i++) {
            if (g->adjMatrix[currentVertex][i] == 1 && !visited[i]) {
                visited[i] = 1;
                enqueue(q, i);
            }
        }
    }
}

int main() {
    Graph g;
    initGraph(&g, 6);

    addEdge(&g, 0, 1);
    addEdge(&g, 0, 2);
    addEdge(&g, 1, 3);
    addEdge(&g, 1, 4);
    addEdge(&g, 2, 5);

    for (int i = 0; i < 6; i++) {
        visited[i] = 0;
    }

    printf("Breadth First Search starting from vertex 0:\n");
    BFS(&g, 0);

    return 0;
}

4. 时间复杂度和空间复杂度分析​

深度优先遍历（DFS）​

  • 时间复杂度：O(V+E)O(V + E)，其中 VV 是顶点数，EE 是边数。每个顶点和每条边都会被访问一次。
  • 空间复杂度：O(V)O(V)，主要用于递归调用栈和存储访问标记。

广度优先遍历（BFS）​

  • 时间复杂度：O(V+E)O(V + E)，其中 VV 是顶点数，EE 是边数。每个顶点和每条边都会被访问一次。
  • 空间复杂度：O(V)O(V)，主要用于队列和存储访问标记。