采用邻接表存储结构,不是邻接矩阵的形式,编写一个判别无向图中任意给定的两个顶点之间是否存在一条长度为k的简单路径的算法,用C语言伪代码编写,注释用英文给出
时间: 2024-02-13 11:07:37 浏览: 77
采用连接表存储有向图,设计算法判断任意两个顶点间是否存在路径.doc
```c
// Check if there exists a simple path of length k between two given vertices in an undirected graph using adjacency list representation
/*
adj[]: adjacency list of the graph
visited[]: array to keep track of visited vertices
src: source vertex
dest: destination vertex
k: length of the required path
*/
bool isSimplePath(vector<int> adj[], bool visited[], int src, int dest, int k) {
// if the length of the required path is 0, return true if source and destination are same, else false
if (k == 0) {
return (src == dest);
}
// mark the current vertex as visited
visited[src] = true;
// traverse all the adjacent vertices of the current vertex
for (int i = 0; i < adj[src].size(); i++) {
// if the adjacent vertex is not visited
if (!visited[adj[src][i]]) {
// recursively check if there exists a simple path of length k-1 between the adjacent vertex and the destination vertex
if (isSimplePath(adj, visited, adj[src][i], dest, k-1)) {
return true;
}
}
}
// mark the current vertex as unvisited
visited[src] = false;
// if no simple path of length k is found, return false
return false;
}
```
阅读全文