数据结构与算法-图论-DFS/BFS

图搜索算法在数据结构与算法领域中非常关键，用于在图形数据结构中搜索节点或路径。图是由节点（也称为顶点）以及连接这些节点的边组成的。在本文中，我们将详细探讨两种基础的图搜索算法：深度优先搜索（DFS）和广度优先搜索（BFS），并提供相应的C语言代码示例。

1.深度优先搜索（DFS）

深度优先搜索（DFS）是一种遍历或搜索树或图的算法。DFS 探索尽可能深的分支路径，直到无法继续，然后回溯以探索未被访问的路径。

特点

• 使用栈实现，可以是显式的数据结构栈，或者利用递归调用的隐式栈。
• 常用于路径搜索，解决连通性问题和排序问题。

C 语言代码示例

假设图以邻接表形式给出，这里使用结构体和指针来定义图的结构。

实现一个完整的深度优先搜索（DFS）算法，我们需要添加图的创建、边的添加以及DFS本身的实现。以下代码段将完成这些部分，实现图的创建、添加边，并利用DFS遍历图：

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

// 定义图的节点
typedef struct node {
    int vertex;
    struct node* next;
} Node;

// 定义图结构
typedef struct {
    int numVertices;
    Node** adjLists;
    int* visited;
} Graph;

// 创建节点
Node* createNode(int v) {
    Node* newNode = malloc(sizeof(Node));
    newNode->vertex = v;
    newNode->next = NULL;
    return newNode;
}

// 创建图
Graph* createGraph(int vertices) {
    Graph* graph = malloc(sizeof(Graph));
    graph->numVertices = vertices;
    graph->adjLists = malloc(vertices * sizeof(Node*));
    graph->visited = malloc(vertices * sizeof(int));

    int i;
    for (i = 0; i < vertices; i++) {
        graph->adjLists[i] = NULL;
        graph->visited[i] = 0;
    }
    return graph;
}

// 添加边
void addEdge(Graph* graph, int src, int dest) {
    // 添加从src到dest的边
    Node* newNode = createNode(dest);
    newNode->next = graph->adjLists[src];
    graph->adjLists[src] = newNode;

    // 由于是无向图，添加从dest到src的边
    newNode = createNode(src);
    newNode->next = graph->adjLists[dest];
    graph->adjLists[dest] = newNode;
}

// 深度优先搜索实现
void DFS(Graph* graph, int vertex) {
    Node* adjList = graph->adjLists[vertex];
    Node* temp = adjList;

    graph->visited[vertex] = 1;
    printf("已访问 %d\n", vertex);

    while (temp != NULL) {
        int connectedVertex = temp->vertex;
        if (graph->visited[connectedVertex] == 0) {
            DFS(graph, connectedVertex);
        }
        temp = temp->next;
    }
}

int main() {
    Graph* graph = createGraph(6);
    addEdge(graph, 0, 1);
    addEdge(graph, 0, 2);
    addEdge(graph, 1, 2);
    addEdge(graph, 1, 3);
    addEdge(graph, 2, 4);
    addEdge(graph, 3, 4);
    addEdge(graph, 3, 5);
    addEdge(graph, 4, 5);

    DFS(graph, 0);  // 从顶点0开始深度优先搜索

    return 0;
}

代码说明

1. 图的结构：使用邻接表来表示图，其中每个节点包含顶点编号和指向下一个邻接顶点的指针。
2. 创建图和节点：提供函数来创建图和其节点。
3. 添加边：因为是无向图，所以每添加一个方向的边时，也要添加反方向的边。
4. DFS函数：使用递归实现深度优先搜索。开始时，标记当前节点为已访问，并递归地访问所有未被访问的邻接节点。

这段代码能够遍历给定图的所有顶点，显示每个访问的顶点。这是深度优先搜索常见的用法，可以用于检测图的连通性、查找图中的路径等。

2. 广度优先搜索（BFS）

广度优先搜索（BFS）是另一种图的遍历算法，它从根节点开始，逐层遍历图中的所有节点，先访问近邻节点，再访问更远的节点。

特点

• 使用队列实现。
• 常用于找到最短路径或任何层次遍历的场景。

C 语言代码示例

基于上面的图结构，我们可以实现 BFS：

以下是完整的广度优先搜索（BFS）的C语言实现，包括定义图结构、队列的操作函数（入队、出队、判断是否为空）以及广度优先搜索的具体实现。我们将继续从之前的代码段扩展，完善队列的操作和图的遍历逻辑。

C 语言代码示例

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

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

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

// 检查队列是否为空
bool isEmpty(Queue* q) {
    if(q->rear == -1)
        return true;
    else
        return false;
}

// 入队
void enqueue(Queue* q, int value) {
    if(q->rear == 99)
        printf("队列已满.\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("队列为空.\n");
        item = -1;
    } else {
        item = q->items[q->front];
        q->front++;
        if(q->front > q->rear) {
            q->front = -1;
            q->rear = -1;
        }
    }
    return item;
}

typedef struct node {
    int vertex;
    struct node* next;
} Node;

typedef struct {
    int numVertices;
    Node** adjLists;
    int* visited;
} Graph;

Node* createNode(int v) {
    Node* newNode = malloc(sizeof(Node));
    newNode->vertex = v;
    newNode->next = NULL;
    return newNode;
}

Graph* createGraph(int vertices) {
    Graph* graph = malloc(sizeof(Graph));
    graph->numVertices = vertices;
    graph->adjLists = malloc(vertices * sizeof(Node*));
    graph->visited = malloc(vertices * sizeof(int));
    
    for(int i = 0; i < vertices; i++) {
        graph->adjLists[i] = NULL;
        graph->visited[i] = 0;
    }
    return graph;
}

void addEdge(Graph* graph, int src, int dest) {
    Node* newNode = createNode(dest);
    newNode->next = graph->adjLists[src];
    graph->adjLists[src] = newNode;
    
    newNode = createNode(src);
    newNode->next = graph->adjLists[dest];
    graph->adjLists[dest] = newNode;
}

void BFS(Graph* graph, int startVertex) {
    Queue* queue = createQueue();
    
    graph->visited[startVertex] = 1;
    enqueue(queue, startVertex);
    
    while(!isEmpty(queue)) {
        int currentVertex = dequeue(queue);
        printf("已访问 %d\n", currentVertex);
        
        Node* temp = graph->adjLists[currentVertex];
        
        while(temp) {
            int adjVertex = temp->vertex;
            
            if(graph->visited[adjVertex] == 0) {
                graph->visited[adjVertex] = 1;
                enqueue(queue, adjVertex);
            }
            temp = temp->next;
        }
    }
}

int main() {
    Graph* graph = createGraph(6);
    addEdge(graph, 0, 1);
    addEdge(graph, 0, 2);
    addEdge(graph, 1, 3);
    addEdge(graph, 1, 4);
    addEdge(graph, 2, 5);

    BFS(graph, 0);

    return 0;
}

说明

这段代码首先定义了一个图和一个队列，然后实现了广度优先搜索（BFS）。在BFS中，我们首先将起始顶点放入队列，并标记为已访问。然后，我们依次从队列中取出顶点，并访问其所有未访问的邻接点，将它们加入队列并标记为已访问。这个过程重复进行，直到队列为空。通过这种方式，BFS可以按层次访问图中的所有顶点。

在实际生活应用中，深度优先搜索（DFS）可用于解决如解迷宫问题。这个案例使用深度优先搜索算法探索从迷宫的入口到出口的路径。迷宫可以视为一个由格子组成的网格，其中一些格子是可通过的，而其他格子则可能被墙阻挡。

3. C 语言实现 DFS 解迷宫

以下是用C语言实现的迷宫探索代码。我们将使用深度优先搜索来尝试每一条可能的路径，直到找到出口。如果找到出口，我们将打印出一条路径。

C语言代码示例

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

#define ROW 5
#define COL 5

// 迷宫地图，0可走，1不可走
int maze[ROW][COL] = {
    {0, 1, 0, 0, 0},
    {0, 1, 0, 1, 0},
    {0, 0, 0, 0, 0},
    {0, 1, 1, 1, 0},
    {0, 0, 0, 1, 0}
};

// 访问标记
int visited[ROW][COL] = {0};

// 移动方向（上下左右）
int moveX[4] = {0, 0, -1, 1};
int moveY[4] = {-1, 1, 0, 0};

// 检查当前位置是否合法
bool isValid(int x, int y) {
    if (x < 0 || x >= ROW || y < 0 || y >= COL) return false;
    if (maze[x][y] == 1 || visited[x][y] == 1) return false;
    return true;
}

// DFS搜索迷宫路径
bool dfs(int x, int y) {
    // 如果达到右下角出口
    if (x == ROW - 1 && y == COL - 1) {
        visited[x][y] = 1;
        return true;
    }

    // 检查当前位置是否可走
    if (isValid(x, y)) {
        visited[x][y] = 1;  // 标记为已访问

        // 尝试每一个方向
        for (int i = 0; i < 4; i++) {
            int nextX = x + moveX[i];
            int nextY = y + moveY[i];
            if (dfs(nextX, nextY)) return true;
        }

        visited[x][y] = 0;  // 回溯，标记为未访问
    }
    return false;
}

void printPath() {
    for (int i = 0; i < ROW; i++) {
        for (int j = 0; j < COL; j++) {
            printf("%d ", visited[i][j]);
        }
        printf("\n");
    }
}

int main() {
    if (dfs(0, 0)) {
        printf("找到了通往出口的路径:\n");
        printPath();
    } else {
        printf("没有找到通往出口的路径.\n");
    }
    return 0;
}

说明

上述代码定义了一个5x5的迷宫和一个相应的访问数组。DFS函数尝试从入口（0,0）开始探索，使用一个递归方法来尝试所有可能的路径。如果找到一条到达出口（ROW-1, COL-1）的路径，该函数将返回true，并通过visited数组标记路径。

此代码还包括一个printPath函数，用于打印出到达终点的路径。这个解决方案可以直接应用于任何通过二维网格模拟的迷宫探索问题，非常适合需要路径查找的

4.C 语言实现 BFS 解迷宫

在生活中应用图搜索算法的一个常见场景是地图导航系统，如何在城市道路网中找到两点之间的最短路径。在这个实例中，我们将使用广度优先搜索（BFS）来模拟在城市的道路网络中寻找从一个地点到另一个地点的最短路径的情况。

在C语言中实现这样的模型，我们首先需要设置一个城市的道路网络图，然后使用 BFS 算法来找出两点之间的最短路径。

定义城市地图道路网络

我们首先定义一个图结构来表示城市中的路口（节点）和道路（边），然后实现 BFS 搜索找到最短路径。

C 语言代码示例

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

typedef struct node {
    int vertex;
    struct node* next;
} Node;

typedef struct {
    int numVertices;
    Node** adjLists;
    int* visited;
    int* distance;  // 用于存储起点到每个顶点的距离
} Graph;

Node* createNode(int v) {
    Node* newNode = (Node*)malloc(sizeof(Node));
    newNode->vertex = v;
    newNode->next = NULL;
    return newNode;
}

Graph* createGraph(int vertices) {
    Graph* graph = (Graph*)malloc(sizeof(Graph));
    graph->numVertices = vertices;
    graph->adjLists = (Node**)malloc(vertices * sizeof(Node*));
    graph->visited = (int*)malloc(vertices * sizeof(int));
    graph->distance = (int*)malloc(vertices * sizeof(int));

    for (int i = 0; i < vertices; i++) {
        graph->adjLists[i] = NULL;
        graph->visited[i] = 0;
        graph->distance[i] = INT_MAX;
    }
    return graph;
}

void addEdge(Graph* graph, int src, int dest) {
    Node* newNode = createNode(dest);
    newNode->next = graph->adjLists[src];
    graph->adjLists[src] = newNode;

    newNode = createNode(src);
    newNode->next = graph->adjLists[dest];
    graph->adjLists[dest] = newNode;
}

void BFS(Graph* graph, int startVertex) {
    int queue[1000], front = 0, rear = -1;

    graph->visited[startVertex] = 1;
    graph->distance[startVertex] = 0;
    queue[++rear] = startVertex;

    while (front <= rear) {
        int currentVertex = queue[front++];
        Node* temp = graph->adjLists[currentVertex];

        while (temp) {
            int adjVertex = temp->vertex;

            if (graph->visited[adjVertex] == 0) {
                graph->visited[adjVertex] = 1;
                graph->distance[adjVertex] = graph->distance[currentVertex] + 1; // 计算距离
                queue[++rear] = adjVertex;
            }
            temp = temp->next;
        }
    }
}

int main() {
    Graph* graph = createGraph(8); // 假设城市有8个重要交叉路口
    addEdge(graph, 0, 1);
    addEdge(graph, 0, 3);
    addEdge(graph, 1, 2);
    addEdge(graph, 1, 4);
    addEdge(graph, 2, 5);
    addEdge(graph, 3, 4);
    addEdge(graph, 4, 5);
    addEdge(graph, 5, 6);
    addEdge(graph, 6, 7);

    BFS(graph, 0);  // 从路口0开始搜索

    printf("从0到7的最短路径是%d步.\n", graph->distance[7]);

    return 0;
}

说明

在上面的代码中，我们构建了一个模拟的城市道路网络，并通过广度优先搜索算法找到从节点 0 到节点 7 的最短路径。每个节点代表一个路口，每条边代表两个路口之间的直接道路。distance 数组用于存储从起始点到图中每个其他顶点的最短路径长度。

这种类型的实现在现实世界的导航