一个连通图采用邻接表作为储存结构，设计一个算法～实现从顶点v出发的深度优先遍历的非递归过程

如题所述

递归转非递归的常用方法是自己用栈来模拟，比较容易得到的方法是：

#include <iostream>
#include <vector>
#include <stack>
#include <cstring>
using namespace std;
const int maxn = 1000000;

vector<int> G[maxn];
int e[maxn];
bool visit[maxn];
void dfs(int u)
{
    visit[u] = true;
    cout << u << endl;
    for(int i = 0; i < (int)G[u].size(); ++i) {
        if(!visit[G[u][i]]) dfs(G[u][i]);
    }
}
int n, s; // 结点数, 起点编号
int main()
{
    cin >> n;
    for(int i = 1; i <= n; ++i) {
        int sz;
        cin >> sz;
        for(int j = 0; j < sz; ++j) {
            int v;
            cin >> v;
            G[i].push_back(v);
        }
    }
    cin >> s;
    dfs(s);
    cout << endl;
    memset(visit, 0, sizeof(visit));
    stack<int> stk;
    stk.push(s);
    while(!stk.empty()) {
        int u = stk.top(); stk.pop();
        if(!visit[u]) {
            cout << u << endl;
            visit[u] = true;
        }
        for(; e[u] < (int)G[u].size(); ++e[u]) {
            int v = G[u][e[u]];
            if(visit[v]) continue;
            stk.push(u); stk.push(v);
            break;
        }
    }
    return 0;
}

以上程序进行了一次递归遍历和依次非递归遍历，输入格式是：

10
1 8
1 4
1 9
2 2 5
2 4 8
3 10 7 8
1 6
3 1 5 6
2 3 10
2 6 9
8

第一行表示结点数，第[2..n+1]行每行表示编号为[1..n]的结点的邻接表（邻接点数量 结点编号...）

最后一行表示dfs的起点编号。

追问

谢谢*^_^*

追答

不客气，问题解决的话就采纳呗。。

温馨提示：内容为网友见解，仅供参考

当前网址：https://11.t2y.org/zz/fmp2778848v828mfqv4.html