邻接表的深度优先遍历非递归

邻接表的深度优先遍历非递归可以使用栈来实现。具体步骤如下：

1. 创建一个栈，将起始节点入栈，并将其标记为已访问。
2. 当栈不为空时，取出栈顶元素，输出该节点的值。
3. 遍历该节点的所有邻居节点，如果邻居节点未被访问，则将其入栈并标记为已访问。
4. 重复步骤2和3，直到栈为空。

下面是C++代码实现：

void DFS_non_recursive(Graph &g, VNode vNode) {
    stack<VNode> s;
    s.push(vNode);
    g.vNode[vNode.index].visited = true;
    while (!s.empty()) {
        VNode v = s.top();
        s.pop();
        cout << v.data << " ";
        ArcNode* p = v.firstArc;
        while (p != NULL) {
            if (!g.vNode[p->adjvex].visited) {
                s.push(g.vNode[p->adjvex]);
                g.vNode[p->adjvex].visited = true;
            }
            p = p->next;
        }
    }
}

相关问题

图的深度优先遍历非递归

图的深度优先遍历可以使用栈来实现非递归算法。

具体实现步骤如下：
1. 创建一个栈，并将起始节点入栈。
2. 创建一个 visited 集合，记录已经访问过的节点。
3. 当栈不为空时，取出栈顶节点，如果该节点没有被访问过，则将其标记为已访问，并将其所有未访问过的邻居节点入栈。
4. 重复步骤3，直到栈为空。

以下是示例 Python 代码实现：

def dfs_iterative(graph, start):
    stack = [start]
    visited = set()
    while stack:
        node = stack.pop()
        if node not in visited:
            visited.add(node)
            for neighbor in graph[node]:
                if neighbor not in visited:
                    stack.append(neighbor)
    return visited

其中，graph 表示图的邻接表表示方式，start 表示起始节点。函数返回已经访问过的节点集合。

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

在C语言中，基于非递归的方式实现深度优先遍历(DFS)通常需要借助栈数据结构，因为深度优先搜索的过程需要回溯。以下是使用栈实现图的深度优先遍历的一个示例：

#include <stdio.h>
#include <stdlib.h>
#define MAX 100 // 图的最大节点数

typedef struct {
    int vertex; // 节点值
    struct Node* next; // 指向下一个邻接节点的指针
} Node;

typedef struct {
    Node* top;
    int size;
} Stack;

// 初始化栈
void init(Stack *s) {
    s->top = NULL;
    s->size = 0;
}

// 判断栈是否为空
int isEmpty(Stack *s) {
    return (s->top == NULL);
}

// 入栈操作
void push(Stack *s, Node* node) {
    if (isEmpty(s)) {
        s->top = node;
    } else {
        node->next = s->top;
        s->top = node;
    }
    s->size++;
}

// 出栈操作
Node* pop(Stack *s) {
    if (isEmpty(s))
        return NULL;
    Node* temp = s->top;
    s->top = s->top->next;
    s->size--;
    return temp;
}

// 非递归深度优先遍历
void dfs(Node** graph, int v, Stack* stack) {
    printf("%d ", v); // 访问当前节点
    push(stack, (Node*)graph[v]); // 将未访问的相邻节点入栈

    while (!isEmpty(stack)) {
        v = pop(stack)->vertex; // 取出栈顶节点并访问其邻居
        for (Node* n = graph[v]; n != NULL; n = n->next) {
            if (n->vertex != v && !visited[n->vertex]) { // 如果邻居未访问过
                visited[n->vertex] = 1; // 标记已访问
                dfs(graph, n->vertex, stack); // 递归调用dfs
            }
        }
    }
}

int main() {
    int graph[MAX][MAX];
    int numVertices; // 图的节点数
    printf("Enter number of vertices: ");
    scanf("%d", &numVertices);

    // 填充图的邻接矩阵或其他表示法...
    for (int i = 0; i < numVertices; ++i) {
        for (int j = 0; j < numVertices; ++j) {
            scanf("%d", &graph[i][j]);
        }
    }

    Stack stack;
    Node* visited = (Node*)malloc(numVertices * sizeof(int)); // 创建标记数组
    memset(visited, 0, numVertices * sizeof(int));

    Node** graphPtr = (Node**)malloc(sizeof(Node*) * numVertices);
    for (int i = 0; i < numVertices; ++i) {
        graphPtr[i] = NULL; // 初始化邻接表
        for (int j = 0; j < numVertices; ++j) {
            if (graph[i][j] != 0) {
                graphPtr[i] = (Node*)malloc(sizeof(Node));
                graphPtr[i]->vertex = j;
                graphPtr[i]->next = NULL;
            }
        }
    }

    dfs(graphPtr, 0, &stack); // 从第一个节点开始遍历
    free(graphPtr);
    free(visited);
    return 0;
}