c++实现深度优先遍历算法
时间: 2023-09-13 19:11:23 浏览: 62
深度优先遍历算法是一种图形遍历算法,它沿着图形的深度遍历图形,尽可能深的搜索图形的分支。
在 C 语言中,可以使用递归函数来实现深度优先遍历算法。
下面是一个简单的例子,展示了如何使用递归函数来实现深度优先遍历:
```
void dfs(int node) {
// 访问当前结点
printf("%d ", node);
// 遍历当前结点的所有邻居
for (int i = 0; i < num_neighbors(node); i++) {
int neighbor = get_neighbor(node, i);
// 递归遍历邻居
dfs(neighbor);
}
}
```
在这个例子中,`dfs` 函数接收一个结点编号作为参数,然后访问这个结点,并遍历它的所有邻居。对于每个邻居,它会递归调用自身,以便对这个邻居进行深度优先遍历。
希望这个例子能对你有帮助。
相关问题
使用C++实现图的深度优先遍历算法
在C++中,我们可以使用递归或栈来实现深度优先遍历。以下是使用栈实现深度优先遍历的基本步骤:
1. 创建一个visited数组来记录每个节点是否被访问过,初始值为false。
2. 创建一个栈,将起始节点入栈。
3. 当栈不为空时,弹出栈顶元素并访问它,将其标记为已访问。
4. 遍历该节点的所有未访问的相邻节点,将它们入栈。
5. 重复步骤3和步骤4,直到栈为空。
下面是一个使用栈实现深度优先遍历的C++代码示例:
```
void DFS(int start, vector<vector<int>>& graph, vector<bool>& visited) {
stack<int> s;
s.push(start);
while (!s.empty()) {
int node = s.top();
s.pop();
if (!visited[node]) {
visited[node] = true;
// 访问节点node
for (int i = 0; i < graph[node].size(); i++) {
int neighbor = graph[node][i];
if (!visited[neighbor]) {
s.push(neighbor);
}
}
}
}
}
```
其中,start表示起始节点,graph是邻接表表示的图,visited是记录节点是否被访问过的数组。
c++图的深度优先遍历算法
以下是C++图的深度优先遍历算法的示例代码:
```c++
#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;
const int MAXN = 1000; // 最大结点数
vector<int> node[MAXN]; // 存储结点关系
int vist[MAXN]; // 标记结点是否被遍历过
void dfs(int nd) {
if(vist[nd]==0) {
cout<<nd<<" "; // 输出遍历到的结点
vist[nd]=1; // 标记结点已被遍历
}
for(int i=0;i<node[nd].size();i++) {
if(vist[node[nd][i]]==0) dfs(node[nd][i]); // 遍历与该结点有关系的结点
}
}
void dfs_all(int wi) {
for(int i=0;i<wi;i++) {
if(vist[i]==0) dfs(i); // 遍历所有未被遍历的结点
}
}
int main() {
int wi,ma;
cin>>wi>>ma; // wi为结点数,ma为边数
for(int i=0;i<ma;i++) {
int a,b;
cin>>a>>b; // 读入结点关系
node[a].push_back(b); // 存储结点关系
}
for(int i=0;i<wi;i++) {
if(!node[i].empty()) sort(node[i].begin(),node[i].end()); // 对每个结点的关系结点进行排序
}
dfs_all(wi); // 遍历所有结点
return 0;
}
```