图的深度优先遍历非递归算法实现 - 邻接表存储结构

图的深度优先遍历非递归算法实现 - 邻接表存储结构

本文将详细介绍如何利用邻接表作为图的存储结构，设计一个非递归算法实现从指定顶点出发对图进行深度优先遍历。

算法步骤：

1. 创建一个栈，并将起始节点 v 入栈。
2. 创建一个数组 visited，用于记录每个节点是否被访问过，将 v 对应的 visited[v] 置为 true。
3. 当栈不为空时，执行以下步骤：
   1. 取出栈顶元素 top。
   2. 对于 top 的每个邻接点，如果该邻接点未被访问过，则将其入栈，并将 visited 数组对应位置置为 true。
4. 遍历结束。

实现代码：

void DFS_iterative(Graph g, int v) {
    int* visited = (int*)malloc(g.num_vertices * sizeof(int));
    for (int i = 0; i < g.num_vertices; i++) {
        visited[i] = 0;
    }
    Stack s = create_stack();
    push(s, v);
    visited[v] = 1;
    while (!is_empty(s)) {
        int top = pop(s);
        printf("%d ", top);
        for (int i = 0; i < g.adj_list[top].size(); i++) {
            int neighbor = g.adj_list[top][i];
            if (!visited[neighbor]) {
                push(s, neighbor);
                visited[neighbor] = 1;
            }
        }
    }
}

代码解释：

• DFS_iterative 函数接收图 g 和起始节点 v 作为参数，并返回遍历结果。
• visited 数组用于记录每个节点是否已经被访问过，初始值为 0，表示未访问过，当访问过该节点时，将对应的 visited 数组元素置为 1。
• 使用 Stack 数据结构来模拟递归过程，将当前节点的邻接点入栈，并按栈的先进后出的顺序进行访问。
• 当栈不为空时，从栈顶弹出元素，打印其值，并检查该节点的邻接点是否被访问过，若未被访问过，则将其入栈。

总结：

本文详细介绍了使用邻接表存储结构的图，如何实现从指定顶点出发进行深度优先遍历的非递归算法。通过栈和访问标记数组，该算法能够有效地遍历图的所有可达节点。