c++设计算法以邻接表作存储结构设计按深度优先遍历图的非递归算法

好的，以下是按深度优先遍历图的非递归算法的C++实现，使用邻接表作为图的存储结构：

#include<iostream>
#include<stack>
#include<vector>
using namespace std;

const int MAXN = 1005;

// 邻接表结构体
struct EdgeNode {
    int to;             // 边的终点
    int weight;         // 边的权值
    int next;           // 下一个邻接点的下标
}edges[MAXN];

int head[MAXN];         // 存储每个节点的第一个邻接点的下标
int edge_cnt = 0;       // 边的数量
int node_cnt = 0;       // 节点的数量

// 添加一条边
void add_edge(int u, int v, int w) {
    edges[++edge_cnt].to = v;
    edges[edge_cnt].weight = w;
    edges[edge_cnt].next = head[u];
    head[u] = edge_cnt;
}

// 深度优先遍历
void dfs(int start) {
    vector<bool> visited(node_cnt + 1, false);  // 记录每个节点是否被访问过
    stack<int> s;
    s.push(start);
    visited[start] = true;
    cout << start << " ";

    while(!s.empty()) {
        int u = s.top();
        bool flag = false;  // 判断是否有未访问过的邻接点
        for(int i = head[u]; i; i = edges[i].next) {
            int v = edges[i].to;
            if(!visited[v]) {
                s.push(v);
                visited[v] = true;
                cout << v << " ";
                flag = true;
                break;
            }
        }
        if(!flag) {
            s.pop();
        }
    }
}

int main() {
    int n, m;
    cin >> n >> m;  // 输入节点数量和边数量
    node_cnt = n;

    // 输入每条边的起点、终点、权值
    for(int i = 1; i <= m; i++) {
        int u, v, w;
        cin >> u >> v >> w;
        add_edge(u, v, w);
    }

    int start;
    cin >> start;   // 输入起点
    dfs(start);     // 按深度优先遍历图

    return 0;
}

在这个算法中，我们使用了一个栈来模拟递归的过程。首先将起点压入栈中，并标记为已访问。然后对于当前栈顶节点，遍历它的邻接点，如果有未访问过的邻接点，则将其压入栈中，并标记为已访问。如果当前节点没有未访问过的邻接点，则将其弹出栈。重复这个过程，直到栈为空。这样，就可以按深度优先遍历图，且不需要使用递归。