DFS 非递归 邻接矩阵

DFS（深度优先搜索）非递归遍历邻接矩阵的代码如下：

int visited[MAX];
void NoReTraverseGraph(AdjMatrix g) {
    // 设置visited数组
    for (int vi = 0; vi < g.vexnum; vi++) {
        visited[vi = 0;
    }
    // 对全顶点遍历
    for (int vi = 0; vi < g.vexnum; vi++) {
        if (!visited[vi]) {
            NoReDepthFirstSearch(g, vi);
        }
    }
}

void NoReDepthFirstSearch(AdjMatrix g, int v) {
    printf("%c ", g.vertex[v]); // visit(v);
    visited[v = 1;
    stack<int> S;
    S.push(v);
    while (!S.empty()) {
        int top = S.top();
        int w = 0;
        for (w = 0; w < g.vexnum; w++) {
            // 如果没访问过并且还连着就访问入栈
            if (!visited[w && g.arcs[top][w].adj == 1) {
                printf("%c ", g.vertex[w]); // visit(w);
                visited[w = 1;
                S.push(w);
                // 立刻停止，对连着的这个元素进行遍历（深度优先）
                break;
            }
        }
        // 找了一圈都访问了或者都没连上，那就出栈
        if (w == g.vexnum) {
            S.pop();
        }
    }
}

以上是对邻接矩阵进行DFS非递归遍历的代码，其中`visited`数组用于标记顶点是否被访问过，`stack`用于存储待访问的顶点。在遍历过程中，首先输出当前访问的顶点，然后将其标记为已访问，并将其邻接且未被访问的顶点入栈。如果一个顶点的所有邻接顶点都被访问过或者没有邻接顶点，那么将该顶点出栈。重复这个过程直到栈为空，即完成了非递归的DFS遍历。

请注意，代码中的`visit(v)`和`visit(w)`表示访问顶点v和w的操作，具体的实现可以根据实际需求自行编写。<span class="em">1</span><span class="em">2</span><span class="em">3</span>
#### 引用[.reference_title]
- *1* *2* *3* [图的DFS算法在邻接矩阵/邻接表下的非递归实现【C/C++】](https://blog.csdn.net/qq_45400167/article/details/125822842)[target="_blank" data-report-click={"spm":"1018.2226.3001.9630","extra":{"utm_source":"vip_chatgpt_common_search_pc_result","utm_medium":"distribute.pc_search_result.none-task-cask-2~all~insert_cask~default-1-null.142^v92^chatsearchT3_1"}}] [.reference_item style="max-width: 100%"]
[ .reference_list ]