写一段C++代码,,实现基于邻接表存储的DFS非递归算法
时间: 2023-06-08 16:03:42 浏览: 88
编写DFS算法的非递归函数
5星 · 资源好评率100%
以下是基于邻接表存储的DFS非递归算法的 C 代码实现:
#include <stdio.h>
#include <stdlib.h>
#define MAX_N 100 // 顶点数最大值
typedef struct Node {
int val;
struct Node* next;
} Node;
Node* graph[MAX_N]; // 邻接表
int visited[MAX_N]; // 记录每个节点的访问状态
int top = -1; // 栈顶指针
int stack[MAX_N]; // 栈
// 非递归DFS
void dfs(int start) {
visited[start] = 1; // 标记起点已经被访问
stack[++top] = start; // 起点入栈
while (top >= 0) { // 栈非空
int cur = stack[top--]; // 出栈
printf("%d ", cur); // 访问节点
Node* p = graph[cur]; // 找到该节点的邻居
while (p) { // 遍历所有的邻居节点
int val = p->val;
if (!visited[val]) { // 如果邻居节点未被访问
visited[val] = 1; // 标记已访问
stack[++top] = val; // 入栈
}
p = p->next;
}
}
}
int main() {
// 建立一个简单的无向图
int n = 6; // 节点数
int edges[][2] = {{0, 1}, {0, 2}, {1, 3}, {2, 3}, {2, 4}, {3, 4}}; // 边列表
for (int i = 0; i < n; i++) {
graph[i] = NULL; // 初始化邻接表
visited[i] = 0; // 初始化访问状态
}
for (int i = 0; i < sizeof(edges) / sizeof(edges[0]); i++) { // 建图
int u = edges[i][0], v = edges[i][1];
Node* p = (Node*)malloc(sizeof(Node)); // 新建节点
p->val = v;
p->next = graph[u];
graph[u] = p;
p = (Node*)malloc(sizeof(Node)); // 新建节点
p->val = u;
p->next = graph[v];
graph[v] = p;
}
int start = 0; // 起点
printf("DFS: ");
dfs(start);
printf("\n");
return 0;
}
阅读全文