习题1:C语言实现使用矩阵计算两个顶点之间(v1-v5)有多少⻓度小于5的通 路? 打印出邻接矩阵和所有通路，请给出具体代码

在C语言中，要实现这个功能，我们可以首先创建一个邻接矩阵来表示图，其中每个元素表示两个顶点之间的边是否存在以及长度。假设我们的顶点从0开始编号，且矩阵大小足够存储v1到v5之间的所有路径。下面是一个简单的示例，使用邻接矩阵并利用深度优先搜索（DFS）来找到所有长度小于5的通路：

#include <stdio.h>
#define V 6 // v1 to v5 + 1 (因为矩阵从0开始)

// 邻接矩阵，初始化为0表示无边，非0表示有边且包含长度信息
int adj[V][V] = {
    {0, 0, 0, 0, 0, 0},
    {0, 0, 4, 0, 0, 0}, // v1 - v2 has length 4
    {0, 4, 0, 8, 0, 0}, // v2 - v3 has length 8
    {0, 0, 8, 0, 5, 0}, // v3 - v4 has length 5
    {0, 0, 0, 5, 0, 7}, // v4 - v5 has length 7
    {0, 0, 0, 0, 7, 0}  // v5 has no outgoing edges
};

// 检查是否到达目标并且路径长度小于5
void checkPath(int src, int dest, int path[], int n, int &count, int pathLength)
{
    if (src == dest && pathLength < 5) {
        count++;
        for (int i = 0; i < n; i++) {
            printf("(%d,%d): %d ", path[i], path[i+1], adj[path[i]][path[i+1]]);
        }
        printf("\n");
    } else if (src != dest && adj[src][dest]) {
        int newPath[] = {src, dest};
        checkPath(dest, dest, newPath, n, count, pathLength + adj[src][dest]);
    }
}

// DFS遍历寻找通路
void dfs(int start, int visited[], int &count)
{
    int path[2 * V]; // 双向路径数组，考虑从起点到终点的所有可能路径
    path[0] = start;
    visited[start] = 1;

    for (int i = 0; i < V; i++) {
        if (visited[i] == 0 && adj[start][i]) {
            checkPath(start, i, path, V, count, 0);
            dfs(i, visited, count); // 继续搜索其他未访问节点
        }
    }
}

int main()
{
    int count = 0; // 计数器用于记录长度小于5的通路

    // 初始化访问标记数组
    int visited[V];
    for (int i = 0; i < V; i++) {
        visited[i] = 0;
    }

    // 开始深度优先搜索
    dfs(0, visited, count);

    printf("总共有%d条长度小于5的通路。\n", count);
    return 0;
}

这个代码首先定义了一个邻接矩阵`adj`，然后通过`dfs`函数和`checkPath`函数找到所有长度小于5的路径，并打印出来。注意，实际应用中可能需要根据具体的问题规模调整邻接矩阵的大小。