图的非递归深度优先遍历从邻接表的左边访问到右边的C语言代码
时间: 2023-06-20 16:09:12 浏览: 65
假设邻接表的每个节点的结构体定义如下:
```c
typedef struct node {
int val; // 节点的值
struct node* next; // 指向链表中下一个节点的指针
} Node;
// 邻接表中每个节点的结构体定义
typedef struct adj_list_node {
int vertex; // 节点的索引
Node* head; // 指向链表中第一个节点的指针
} AdjList;
```
非递归深度优先遍历的基本思路是使用栈来存储待访问的节点,从起始节点开始,将其入栈。然后依次取出栈顶的节点进行访问,并将其尚未访问的邻居节点入栈。直到栈为空。
以下是从邻接表的左边访问到右边的C语言代码实现:
```c
void dfs(int start_vertex, AdjList* adj_list, int num_vertices) {
int* visited = (int*)calloc(num_vertices, sizeof(int)); // 记录节点是否被访问过
Node** stack = (Node**)malloc(num_vertices * sizeof(Node*)); // 存储待访问的节点的栈
int top = -1; // 栈顶指针
// 将起始节点入栈
stack[++top] = adj_list[start_vertex].head;
while (top >= 0) {
// 取出栈顶节点并访问
Node* node = stack[top--];
visited[node->val] = 1;
printf("%d ", node->val);
// 将尚未访问的邻居节点入栈
Node* neighbor = adj_list[node->val].head;
while (neighbor) {
if (!visited[neighbor->val]) {
stack[++top] = neighbor;
}
neighbor = neighbor->next;
}
}
free(visited);
free(stack);
}
```