在邻接表类中编码实现一个函数,干函数输出从顶点source
时间: 2024-01-22 18:20:57 浏览: 20
到顶点target的所有路径。
```cpp
void printAllPaths(int source, int target) {
// 标记顶点是否被访问过
bool visited[V] = {false};
// 存储当前路径
vector<int> path;
// 从源顶点开始搜索
path.push_back(source);
printAllPathsUtil(source, target, visited, path);
}
void printAllPathsUtil(int u, int target, bool visited[],
vector<int> &path) {
// 标记当前顶点已被访问
visited[u] = true;
// 如果当前顶点是目标顶点,则输出路径
if (u == target) {
for (int i = 0; i < path.size(); ++i) {
cout << path[i] << " ";
}
cout << endl;
} else {
// 遍历 u 的所有邻接顶点
for (int v : adj[u]) {
if (!visited[v]) {
// 添加当前顶点到路径中
path.push_back(v);
// 递归搜索
printAllPathsUtil(v, target, visited, path);
// 回溯,将当前顶点从路径中删除
path.pop_back();
}
}
}
// 取消标记当前顶点已被访问
visited[u] = false;
}
```
其中,`adj` 表示邻接表,`V` 表示顶点数。函数 `printAllPaths` 是入口函数,它会调用 `printAllPathsUtil` 函数进行递归搜索。在搜索过程中,使用 `visited` 数组标记顶点是否被访问过,使用 `path` 向量存储当前路径。如果遍历到目标顶点,则输出路径;否则,遍历当前顶点的所有邻接顶点,并递归搜索。在递归返回后,需要回溯将当前顶点从路径中删除,并取消标记已访问。