C语言实现图的搜索算法示例

在C语言中，我们可以使用邻接矩阵或邻接表来表示图，实现图的搜索算法，本篇文章将详细介绍如何使用C语言实现图的搜索算法，以及提供两个示例说明。

邻接矩阵表示图

邻接矩阵是使用二维数组表示图的一种方法，其中数组的每个元素代表图中的一个节点，如果两个节点之间存在边，则数组元素的值为1，否则为0。例如，下面是一个由邻接矩阵表示的无向图。

    0  1  2  3
0   0  1  1  0
1   1  0  1  1
2   1  1  0  1
3   0  1  1  0

在C语言中，我们可以使用二维数组来表示邻接矩阵，如下所示：

#define MAX_NODE 4
int graph[MAX_NODE][MAX_NODE] = {
    {0, 1, 1, 0},
    {1, 0, 1, 1},
    {1, 1, 0, 1},
    {0, 1, 1, 0}
};

深度优先搜索

深度优先搜索（DFS）是一种用于图遍历或树遍历的算法，其思路类似于前序遍历二叉树。DFS首先访问起始节点，然后访问与起始节点相连的第一个节点，再递归地访问这个节点的所有相邻节点。深度优先搜索一直进行到遇到一个没有未访问的相邻节点的节点，然后返回到前一个节点，继续访问未访问的相邻节点，直到所有节点都被访问。下面是一个使用邻接矩阵实现DFS的示例代码。

int visited[MAX_NODE] = {0};
void dfs(int node) {
    visited[node] = 1;
    printf("%d ", node);
    for (int i = 0; i < MAX_NODE; i++) {
        if (graph[node][i] == 1 && visited[i] == 0) {
            dfs(i);
        }
    }
}

广度优先搜索

广度优先搜索（BFS）是一种用于图遍历或树遍历的算法，其思路类似于层序遍历二叉树。BFS首先访问起始节点，然后访问起始节点的所有相邻节点，再递归地访问相邻节点的相邻节点。我们使用一个队列来存储要访问的节点。BFS在遍历到一个节点时，将该节点的所有相邻节点加入队列中，然后访问队列的第一个节点，并将其出队。下面是一个使用邻接矩阵实现BFS的示例代码。

void bfs(int node) {
    int queue[MAX_NODE];
    int front = -1, rear = -1;
    visited[node] = 1;
    queue[++rear] = node;
    while (front < rear) {
        int temp = queue[++front];
        printf("%d ", temp);
        for (int i = 0; i < MAX_NODE; i++) {
            if (graph[temp][i] == 1 && visited[i] == 0) {
                visited[i] = 1;
                queue[++rear] = i;
            }
        }
    }
}

示例1：使用邻接矩阵表示二分图

在算法设计中，常常用到二分图，其中每个节点被分为左右两部分，左部分的节点只与右部分的节点相连，右部分的节点只与左部分的节点相连。下面是一个由邻接矩阵表示的二分图。

    0  1  2  3  4
0   0  1  0  1  0
1   1  0  1  0  1
2   0  1  0  1  0
3   1  0  1  0  1
4   0  1  0  1  0

我们可以使用DFS或BFS遍历这个图，代码类似于上面的示例代码。

示例2：使用邻接矩阵表示迷宫的搜索

我们可以使用邻接矩阵来表示迷宫，其中每个元素表示一个迷宫格子，值为1表示这个格子是墙，不能通过，值为0表示这个格子是路，可以通过。我们可以用DFS或BFS来搜索迷宫中的通路。下面是一个由邻接矩阵表示的简单迷宫。

    0  1  2  3
0   1  1  1  1
1   1  0  0  1
2   1  1  0  1
3   1  1  1  1

在这个例子中，我们可以使用BFS来搜索迷宫中的通路，如果起点和终点可以通过路相连，则输出通路。下面是一个简单的BFS实现。

void bfs_maze(int sx, int sy, int tx, int ty) {
    int q[MAX_NODE * MAX_NODE];
    int front = -1, rear = -1;
    q[++rear] = sx * MAX_NODE + sy;
    visited[sx][sy] = 1;
    while (front < rear) {
        int temp = q[++front];
        int x = temp / MAX_NODE, y = temp % MAX_NODE;
        if (x == tx && y == ty) {
            printf("[");
            while (pre[x][y] != -1) {
                printf("(%d,%d)", x, y);
                int t = pre[x][y];
                x = t / MAX_NODE, y = t % MAX_NODE;
            }
            printf("(%d,%d)]", sx, sy);
            return;
        }
        for (int i = 0; i < 4; i++) {
            int nx = x + dx[i], ny = y + dy[i];
            if (nx >= 0 && nx < MAX_NODE && ny >= 0 && ny < MAX_NODE
                && graph[nx][ny] == 0 && visited[nx][ny] == 0) {
                visited[nx][ny] = 1;
                pre[nx][ny] = x * MAX_NODE + y;
                q[++rear] = nx * MAX_NODE + ny;
            }
        }
    }
}

上面的代码中，我们使用二维数组pre来记录BFS访问过程中所有被访问节点的前驱节点。在遇到终点时，从pre数组中可以逆向找到从起点到终点的路径。

总之，使用邻接矩阵表示图可以方便地实现图的搜索算法，我们可以将搜索算法应用于各种类型的问题中。