【算法设计题】判断无向图中任意给定的两个顶点之间是否存在一条长度为k的简单路径，第8题（C/C++）

第8题 判断无向图中任意给定的两个顶点之间是否存在一条长度为k的简单路径

编写算法，判断无向图中任意给定的两个顶点之间是否存在一条长度为k的简单路径（简单路径指的是其顶点序列中不含有重复出现的顶点）。

得分点（必背）

//判断是否存在长度为 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 函数的逐步详细解释：

函数定义

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 的简单路径。简单路径指的是路径中不重复顶点。

递归基准条件

if (i == j && k == 0) { return 1; }

• 条件：如果起始顶点 i 与目标顶点 j 相同，且路径长度 k 为0。
• 解释：如果当前顶点 i 就是目标顶点 j，并且路径长度 k 达到0，说明找到了长度为0的路径，即符合要求的路径。返回1表示找到了一条符合条件的路径。

递归条件

else if (k > 0) { visited[i] = 1;

• 条件：如果路径长度 k 大于0。
• 解释：首先，将当前顶点 i 标记为已访问 (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;
}

• 遍历邻接点：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。

恢复标记

visited[i] = 0;

• 解释：在所有邻接点的递归调用结束后，将当前顶点 i 的访问标记恢复为0。这样可以确保其他路径的探索不受影响。每次递归结束后，都需要将顶点标记恢复，以便其他路径的搜索可以重新访问该顶点。

函数返回

return 0;

• 解释：如果所有邻接点都没有找到符合条件的路径，则返回0，表示没有找到长度为 k 的简单路径。

总结

1. 递归基准条件：当当前顶点是目标顶点且路径长度为0时，返回1。
2. 递归条件：当路径长度大于0时，遍历所有邻接点，尝试找到从当前邻接点到目标顶点的路径，路径长度减1。
3. 恢复标记：确保每次递归结束后，恢复顶点访问标记，保证路径的简单性。
4. 返回值：如果找到符合条件的路径，则返回1；否则，返回0。

通过这种方式，函数递归地探索图中的路径，并确保路径是简单路径，最终判断是否存在一条符合长度要求的路径。