怎么用邻接矩阵判断连同无向图中俩点之间有路径

Question

希望能用c语言解答怎么用邻接矩阵判断连同图中俩点之间有一条路径，回溯要怎么回溯

Answer 1

邻接矩阵是一种存储图中顶点和边的方法。每个顶点对应一个矩阵中的行和列，若顶点 u 和顶点 v 有边相连，则矩阵中第 u 行第 v 列的值为 1，否则为 0。

下面是一个用邻接矩阵表示图的简单示例：

// 图的邻接矩阵存储方法
#define MAX_VERTEX_NUM 20 // 图的最大顶点个数

typedef int Graph[MAX_VERTEX_NUM][MAX_VERTEX_NUM]; // 图的邻接矩阵类型

Graph G; // 图的邻接矩阵

int main()
{
    // 假设顶点 A 和顶点 B 有边相连，顶点 C 和顶点 D 有边相连
    G[0][1] = 1;
    G[1][0] = 1;
    G[2][3] = 1;
    G[3][2] = 1;

    // 打印邻接矩阵，可以看出顶点 A 和顶点 B 有边相连，顶点 C 和顶点 D 有边相连
    for (int i = 0; i < 4; i++)
    {
        for (int j = 0; j < 4; j++)
        {
            printf("%d ", G[i][j]);
        }
        printf("\n");
    }

    return 0;
}

若要判断图中两个点之间是否有路径，可以用图的深度优先搜索算法来实现。下面是一个判断两个点之间是否有路径的简单示例：

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

#define MAX_VERTEX_NUM 20 // 最大顶点数
#define OK 1
#define ERROR 0

typedef int Status; // 定义函数返回状态

// 邻接矩阵存储图
typedef struct
{
    int edges[MAX_VERTEX_NUM][MAX_VERTEX_NUM]; // 图中顶点之间的边
    int n; // 顶点个数
} Graph;

// 深度优先搜索，判断顶点 u 和顶点 v 之间是否有路径相连
void DFS(Graph G, int i, int n, int u, int v)
{
    static int visited[MAX_VERTEX_NUM]; // 访问标记
    int j; // 循环变量

    if (i == v) // 如果找到目标点，结束搜索
    {
        printf("从顶点 %d 到顶点 %d 有路径相连！\n", u, v);
        return;
    }

    visited[i] = 1; // 标记顶点 i 已被访问

    // 搜索顶点 i 的邻接点
    for (j = 0; j < n; j++)
    {
        if (G.edges[i][j] == 1 && visited[j] == 0) // 如果顶点 i 和顶点 j 有边相连且顶点 j 未被访问
        {
            DFS(G, j, n, u, v); // 递归调用
        }
    }

    visited[i] = 0; // 搜索结束，恢复访问标记
}

void Path(Graph G, int n, int u, int v)
{
    // 判断参数是否合法
    if (u < 0 || u >= n || v < 0 || v >= n)
    {
        printf("参数错误！\n");
        return;
    }

    if (u == v) // 如果 u 和 v 是同一个点
    {
        printf("顶点 %d 和顶点 %d 是同一个点！\n", u, v);
        return;
    }

    DFS(G, u, n, u, v); // 深度优先搜索，判断是否有路径相连
}

关于回溯：在搜索算法中，我们通常会使用递归的方法实现搜索，当搜索结束后，会返回上一层递归，并执行上一层递归中的下一个搜索，此过程称为回溯。

例如，在 DFS 函数中，递归调用会返回上一层递归，执行下一个循环，直到所有搜索结束，此过程就是回溯。