问题描述 给定无向图的数据类型如下 #define MAXVEX 100 typedef char VertexType; typedef int EdgeType; typedef struct { VertexType vexs[MAXVEX]; //顶点表 EdgeType edge[MAXVEX][MAXVEX]; //邻接矩阵,即边表 int visited[MAXVEX];//遍历标记. 1:已遍历 0:未遍历 int vertexNum,edgeNum; }MGraph,*Graph; 请设计int distance(Graph g,VertexType v, VertexType u)函数。 该函数返回图中两个顶点v和w之间的距离(最短连通路上边的数目)。提示：连通返回距离，不连通返回0。 . 请注意，本题有预置代码，只需提交所要求的函数定义代码即可。 预置代码 #include<bits/stdc++.h> using namespace std; #define MAXVEX 100 typedef char VertexType; typedef int EdgeType; typedef struct { VertexType vexs[MAXVEX]; //顶点表 EdgeType edge[MAXVEX][MAXVEX]; //邻接矩阵,即边表 int visited[MAXVEX];//遍历标记. 1:已遍历 0:未遍历 int vertexNum,edgeNum; }MGraph,*Graph; int distance(Graph g,VertexType v, VertexType u); int main() { /*此处代码由测试程序自动添加，主要为了向顺序表中插入数据 并输出数据,你无需关心此处代码的具体实现细节。 如果有必要，请自己添加代码以测试你的函数是否正确。 */ return 0; } /*你的提交的代码将被添加在此处，请完成题目所要求的函数的定义*/

解题思路：

该题要求求出无向图中两个顶点之间的最短路径，可以使用 Dijkstra 算法或者 Floyd 算法来实现。这里我们选择 Floyd 算法。

Floyd 算法的基本思想是动态规划，用二维数组 dp 存储任意两个点之间的最短距离，dp[i][j] 表示顶点 i 到顶点 j 的最短路径长度。每次更新 dp[i][j] 时，我们考虑顶点 k 作为中间点的情况，即从 i 到 j 经过 k，那么更新后的 dp[i][j] 就是 dp[i][k] + dp[k][j] 和 dp[i][j] 中的较小值。

具体实现时，我们可以使用三重循环，枚举 i、j、k，其中 i 和 j 分别表示图中的两个顶点，k 表示中间点。每次更新 dp[i][j] 时，我们需要进行判断，如果 dp[i][j] 大于 dp[i][k] + dp[k][j]，则更新 dp[i][j] 的值。

最后，如果两个顶点不连通，则返回 0，否则返回 dp[v][u] 的值。

参考代码如下：

相关问题

问题描述 给定无向图带权图的数据类型如下 #define MAXVEX 100 typedef char VertexType; typedef int EdgeType; typedef struct { VertexType vexs[MAXVEX]; //顶点表 EdgeType edge[MAXVEX][MAXVEX]; //邻接矩阵,即边表 int vertexNum,edgeNum; }MGraph,*Graph; 请设计int Kruskal(Graph g)函数。 该函数用Kruskal算法求g的最小生成树的权,并返回最小生成树的权。 如果最小生成树不存在，则返回-1。 请注意，本题有预置代码，只需提交所要求的函数定义代码即可。

以下是题目所需的函数定义代码：

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

#define MAXVEX 100

typedef char VertexType;
typedef int EdgeType;

typedef struct {
    VertexType vexs[MAXVEX]; //顶点表
    EdgeType edge[MAXVEX][MAXVEX]; //邻接矩阵,即边表
    int vertexNum, edgeNum;
}MGraph, *Graph;

//边的结构体
typedef struct {
    int begin, end; //边的起点和终点
    int weight; //边的权重
}Edge;

//并查集的结构体
typedef struct {
    int father[MAXVEX]; //父节点数组
    int rank[MAXVEX]; //秩数组
}UnionFindSet;

//交换两个边的信息
void swapEdge(Edge *e1, Edge *e2) {
    Edge tmp = *e1;
    *e1 = *e2;
    *e2 = tmp;
}

//对边进行快速排序
void quickSortEdge(Edge *edges, int left, int right) {
    if (left < right) {
        int i = left, j = right;
        Edge pivot = edges[left];
        while (i < j) {
            while (i < j && edges[j].weight >= pivot.weight) {
                j--;
            }
            edges[i] = edges[j];
            while (i < j && edges[i].weight <= pivot.weight) {
                i++;
            }
            edges[j] = edges[i];
        }
        edges[i] = pivot;
        quickSortEdge(edges, left, i - 1);
        quickSortEdge(edges, i + 1, right);
    }
}

//初始化并查集
void initUnionFindSet(UnionFindSet *ufs, int n) {
    for (int i = 0; i < n; i++) {
        ufs->father[i] = i;
        ufs->rank[i] = 0;
    }
}

//查找节点所在的集合
int find(UnionFindSet *ufs, int x) {
    if (ufs->father[x] != x) {
        ufs->father[x] = find(ufs, ufs->father[x]);
    }
    return ufs->father[x];
}

//合并两个集合
void unionSet(UnionFindSet *ufs, int x, int y) {
    int rootX = find(ufs, x);
    int rootY = find(ufs, y);
    if (rootX != rootY) {
        if (ufs->rank[rootX] > ufs->rank[rootY]) {
            ufs->father[rootY] = rootX;
        } else if (ufs->rank[rootX] < ufs->rank[rootY]) {
            ufs->father[rootX] = rootY;
        } else {
            ufs->father[rootY] = rootX;
            ufs->rank[rootX]++;
        }
    }
}

//Kruskal算法求最小生成树
int Kruskal(Graph g) {
    Edge edges[MAXVEX * MAXVEX];
    int edgeNum = 0;
    for (int i = 0; i < g->vertexNum; i++) {
        for (int j = i + 1; j < g->vertexNum; j++) {
            if (g->edge[i][j] != 0) {
                edges[edgeNum].begin = i;
                edges[edgeNum].end = j;
                edges[edgeNum].weight = g->edge[i][j];
                edgeNum++;
            }
        }
    }
    quickSortEdge(edges, 0, edgeNum - 1);
    UnionFindSet ufs;
    initUnionFindSet(&ufs, g->vertexNum);
    int minWeight = 0;
    int count = 0;
    for (int i = 0; i < edgeNum; i++) {
        Edge e = edges[i];
        if (find(&ufs, e.begin) != find(&ufs, e.end)) {
            unionSet(&ufs, e.begin, e.end);
            minWeight += e.weight;
            count++;
            if (count == g->vertexNum - 1) {
                break;
            }
        }
    }
    if (count != g->vertexNum - 1) {
        return -1;
    }
    return minWeight;
}

其中，`swapEdge()`函数用于交换两个边的信息，`quickSortEdge()`函数用于对边进行快速排序，`initUnionFindSet()`函数用于初始化并查集，`find()`函数用于查找节点所在的集合，`unionSet()`函数用于合并两个集合，`Kruskal()`函数用于实现Kruskal算法求最小生成树的权。

问题描述 给定无向图的数据类型如下 #define MAXVEX 100 typedef char VertexType; typedef int EdgeType; typedef struct { VertexType vexs[MAXVEX]; //顶点表 EdgeType edge[MAXVEX][MAXVEX]; //邻接矩阵,即边表 int visited[MAXVEX];//遍历标记. 1:已遍历 0:未遍历 int vertexNum,edgeNum; }MGraph,*Graph; 请设计int distance(Graph g,VertexType v, VertexType u)函数。 该函数返回图中两个顶点v和w之间的距离(最短连通路上边的数目)。提示：连通返回距离，不连通返回0。 . 请注意，本题有预置代码，只需提交所要求的函数定义代码即可。 预置代码 #include<bits/stdc++.h> using namespace std; #define MAXVEX 100 typedef char VertexType; typedef int EdgeType; typedef struct { VertexType vexs[MAXVEX]; //顶点表 EdgeType edge[MAXVEX][MAXVEX]; //邻接矩阵,即边表 int visited[MAXVEX];//遍历标记. 1:已遍历 0:未遍历 int vertexNum,edgeNum; }MGraph,*Graph; int distance(Graph g,VertexType v, VertexType u); int main() { /*此处代码由测试程序自动添加，主要为了向顺序表中插入数据 并输出数据,你无需关心此处代码的具体实现细节。 如果有必要，请自己添加代码以测试你的函数是否正确。 */ return 0; } /*你的提交的代码将被添加在此处，请完成题目所要求的函数的定义*/c语言代码

) {
dir = parent->u.subdir;
break;
} else if (parent->type == 1 && strcmp(parent以下是实现题目要求的 C 语言代码：

int distance(Graph g, VertexType v, VertexType->name, token) == 0) {
                inode* node = parent->u.file;
                for (i = 0; i < 256; i++) {
                    if (node->index[i] != -1) {
                        free_block(node->index[i]);
                    u) {
    // 先判断两个顶点是否连通
    int vIndex = -1, uIndex = -1;
    for (int i = 0; i < g->vertexNum; i++) {
        if (g->vexs[i] }
                }
                free_inode(node);
                if (parent == root->u.subdir) {
                    root->u.subdir = parent == v) {
            vIndex = i;
        } else if (g->vexs[i] == u) {
            uIndex->next;
                } else {
                    parent->parent->next = parent->next;
                }
                free(parent);
                pthread_mutex_unlock(&mutex);
                return 0;
            }
            parent = parent->next;
        }
        if (dir == NULL) {
            = i;
        }
    }
    if (vIndex == -1 || uIndex == -1) {
        return 0; // pthread_mutex_unlock(&mutex);
            return -1;
        }
        token = strtok(NULL, "/");
    }
    pthread_mutex_unlock(&mutex 两个顶点中至少有一个不在图中
    }

    // 初始化 dp 数组
    int dp[MAXVEX][MAXVEX];
    for (int i = 0; i < g->vertexNum; i++) {
        for (int);
    return -1;
}

// 文件读操作
int read(char* path, char* data, int size, int offset) {
 j = 0; j < g->vertexNum; j++) {
            dp[i][j] = g->edge[i][j];
    pthread_mutex_lock(&mutex);
    int i, j, k;
    directory* dir = root;
    char* token = strtok(path, "/");
    while (token != NULL) {
        directory* sub = NULL;
        while (dir != NULL) {
            if (        }
    }

    // Floyd 算法求最短路径
    for (int k = 0; k < g->vertexNumdir->type == 0 && strcmp(dir->name, token) == 0) {
                sub = dir->u.subdir;
               ; k++) {
        for (int i = 0; i < g->vertexNum; i++) {
            for (int j = break;
            } else if (dir->type == 1 && strcmp(dir->name, token) == 0) {
                inode* 0; j < g->vertexNum; j++) {
                if (dp[i][j] > dp[i][k] + dp[k][j]) {
                    dp[i][j] = dp[i][k] + dp[k][j];
                }
            }
        }
 node = dir->u.file;
                if (offset >= node->size) {
                    pthread_mutex_unlock(&mutex);
                    return 0    }

    return dp[vIndex][uIndex] == INT_MAX ? 0 : dp[vIndex][uIndex];
}

在;
}
int block_num = (size - 1) / BLOCK_SIZE + 1;
int block_offset = offset /该代码中，我们首先根据顶点 v 和顶点 u 的值找到它们在顶点表中的下 BLOCK_SIZE;
int block_remain = size;
int data_offset = 0;
for (i = block_offset; i <标，判断它们是否都在图中。

然后我们使用 Floyd 算法求出任意两个顶点之间的 256 && node->index[i] != -1 && block_remain > 0; i++) {
int block_size = block_remain >最短路径，即计算出 dp 数组。最后，如果 v 和 u 不连通，即它们之间没有 BLOCK_SIZE ? BLOCK_SIZE : block_remain;
memcpy(data + data_offset, disk[node->index[i]].data + offset % BLOCK_SIZE路径，则返回 0，否则返回 dp[vIndex][uIndex]，即顶点 v 到顶点 u 的最短路径长度。