第8题 判断无向图中任意给定的两个顶点之间是否存在一条长度为k的简单路径
编写算法，判断无向图中任意给定的两个顶点之间是否存在一条长度为k的简单路径（简单路径指的是其顶点序列中不含有重复出现的顶点）。
得分点（必背）
代码语言：javascript复制//判断是否存在长度为 k 的简单路径
int visited[MAXSIZE];
int exist_path_len(ALGraph G ,int i, int j,int k){
if(i==j&&k==0){
return 1;
}
else if(k>0){
visited[i]=1;
for(ArcNode* p=G.vertices[i].firstarc;p;p=p->nextarc){
int temp=p->adjvex;
if(!visited[temp]&&exist_path_len(G,temp,j,k-1)){
return 1;
}
visited[i]=0;
}
return 0;
}
}下面是对 exist_path_len 函数的逐步详细解释：
函数定义
代码语言：javascript复制int visited[MAXSIZE]; int exist_path_len(ALGraph G, int i, int j, int k) {visited[MAXSIZE]: 一个全局数组，用于标记图中顶点是否已经被访问过。exist_path_len(ALGraph G, int i, int j, int k): 判断在无向图G中，是否存在一条从顶点i到顶点j长度为k的简单路径。简单路径指的是路径中不重复顶点。
递归基准条件
代码语言：javascript复制if (i == j && k == 0) { return 1; }- 条件：如果起始顶点
i与目标顶点j相同，且路径长度k为0。 - 解释：如果当前顶点
i就是目标顶点j，并且路径长度k达到0，说明找到了长度为0的路径，即符合要求的路径。返回1表示找到了一条符合条件的路径。
递归条件
代码语言：javascript复制else if (k > 0) { visited[i] = 1;- 条件：如果路径长度
k大于0。 - 解释：首先，将当前顶点
i标记为已访问 (visited[i] = 1)，防止在路径中重复访问此顶点。
遍历邻接点
代码语言：javascript复制for (ArcNode* p = G.vertices[i].firstarc; p; p = p->nextarc) {
int temp = p->adjvex;
if (!visited[temp] && exist_path_len(G, temp, j, k - 1)) {
return 1;
}
visited[i] = 0;
}- 遍历邻接点：
for (ArcNode* p = G.vertices[i].firstarc; p; p = p->nextarc)遍历顶点i的所有邻接点。p是当前弧的指针，p->adjvex是邻接点的编号。- 检查邻接点：
int temp = p->adjvex取得当前邻接点的编号。 - 递归调用：
if (!visited[temp] && exist_path_len(G, temp, j, k - 1))检查邻接点temp是否未被访问且从temp到j是否存在一条长度为k-1的路径。如果存在这样的路径，则返回1。
恢复标记
代码语言：javascript复制visited[i] = 0;- 解释：在所有邻接点的递归调用结束后，将当前顶点
i的访问标记恢复为0。这样可以确保其他路径的探索不受影响。每次递归结束后，都需要将顶点标记恢复，以便其他路径的搜索可以重新访问该顶点。
函数返回
代码语言：javascript复制return 0;- 解释：如果所有邻接点都没有找到符合条件的路径，则返回0，表示没有找到长度为
k的简单路径。
总结
- 递归基准条件：当当前顶点是目标顶点且路径长度为0时，返回1。
- 递归条件：当路径长度大于0时，遍历所有邻接点，尝试找到从当前邻接点到目标顶点的路径，路径长度减1。
- 恢复标记：确保每次递归结束后，恢复顶点访问标记，保证路径的简单性。
- 返回值：如果找到符合条件的路径，则返回1；否则，返回0。
通过这种方式，函数递归地探索图中的路径，并确保路径是简单路径，最终判断是否存在一条符合长度要求的路径。
