图的路径搜索问题 回溯法 c语言 完整代码

图的路径搜索问题，通常指的是寻找从起点到终点的一条路径，例如经典的最短路径问题（如Dijkstra算法）或回溯法解决的迷宫问题等。回溯法是一种递归策略，常用于求解组合优化问题，在图形搜索中用于解决0-1背包、八皇后等问题。

在C语言中，实现图的路径搜索特别是使用回溯法可能涉及到动态规划数组或邻接矩阵数据结构来存储图，以及递归来探索所有可能的路径。下面是一个简单的迷宫求解的回溯法代码示例，假设迷宫用二维数组表示：

#include <stdio.h>

#define ROW 5 // 迷宫行数
#define COL 5 // 迷宫列数
#define WALL 'X'
#define EMPTY '.'

void isSafe(int maze[ROW][COL], int x, int y) {
    if (x >= 0 && x < ROW && y >= 0 && y < COL && maze[x][y] != WALL)
        return true;
    else
        return false;
}

// 回溯函数
void backtracking(int maze[ROW][COL], int x, int y, char path[][ROW]) {
    if (x == ROW - 1 && y == COL - 1) {
        printf("Path found: %s\n", path);
        return;
    }

    // 尝试向四个方向移动
    if (isSafe(maze, x + 1, y)) path[x][y] = 'R'; // 右
    if (isSafe(maze, x, y + 1)) path[x][y] = 'D'; // 下
    if (isSafe(maze, x - 1, y)) path[x][y] = 'L'; // 左
    if (isSafe(maze, x, y - 1)) path[x][y] = 'U'; // 上

    for (int i = 0; i < 4; ++i) {
        if (path[x][y] == EMPTY) { // 如果当前位置未访问过，尝试一步
            path[x][y] = ('R' + i); // 更新路径
            backtracking(maze, x + (i == 0), y + (i == 1), path); // 递归下一层
            path[x][y] = EMPTY; // 撤销步骤，尝试其他方向
        }
    }
}

int main() {
    int maze[ROW][COL] = {
        {' ', ' ', ' ', ' ', ' '},
        {' ', ' ', ' ', ' ', ' '},
        {' ', ' ', ' ', ' ', ' '},
        {' ', ' ', ' ', ' ', ' '},
        {' ', ' ', ' ', ' ', ' '}
    };

    char path[ROW][COL];
    memset(path, '.', sizeof(path)); // 初始化全为墙壁

    backtracking(maze, 0, 0, path); // 从左上角开始搜索
    return 0;
}