基于c语言的图的深度优先遍历非递归

在C语言中，深度优先搜索（Depth-First Search, DFS）通常可以采用栈数据结构来实现，避免了递归带来的栈溢出风险。非递归版本的DFS步骤如下：

创建一个辅助函数用于保存当前节点并压入栈中，同时设置它为已访问状态。
初始化一个空栈和一个集合（数组、链表等）用于存放已访问节点。
将起始节点压入栈中。
当栈不为空时，执行循环：
a. 弹出栈顶节点。
b. 如果该节点未访问过，则标记其为已访问，并将其邻接节点依次加入栈（添加前检查是否已访问）。
循环结束后，已访问的节点集合就包含了图的深度优先遍历路径。

以下是基于C语言的简单示例代码：
#include <stdio.h>
#include <stdbool.h>
#define MAX_VERTICES 100

// 图的邻接矩阵表示
bool adj[MAX_VERTICES][MAX_VERTICES];

// 非递归深度优先遍历
void dfs(int node, bool visited[]) {
visited[node] = true;
printf("%d ", node); // 打印节点

for (int i = 0; i < MAX_VERTICES; ++i) {
if (adj[node][i] &amp;&amp; !visited[i]) {
dfs(i, visited);
}
}
}

int main() {
int V, E;
// ... (输入图的顶点数V和边的信息)

// 假设这里已经初始化了邻接矩阵 adj[][]
bool* visited = malloc(V * sizeof(bool)); // 存储节点访问状态

// 起始节点
dfs(0, visited);

printf("\n");

free(visited); // 释放内存
return 0;
}
登录后复制