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

在C++中，我们可以使用邻接表来表示图，并通过栈数据结构实现非递归的深度优先搜索（DFS）。以下是步骤和伪代码：

1. 定义一个节点类（Node），包含顶点值（value）以及指向邻居节点的列表（adjacent list）。

class Node {
public:
    int value;
    vector<Node*> adjacents; // 邻接表
};

2. 创建一个函数`dfsHelper()`作为辅助函数，用于执行实际的深度优先遍历。它接收当前顶点`current`, 栈`stack`和访问过的集合`visited`作为参数。

void dfsHelper(Node* current, stack<Node*>& stack, unordered_set<Node*>& visited) {
    // 将当前节点标记为已访问
    visited.insert(current);

    // 输出当前节点
    cout << "Visiting node: " << current->value << endl;

    // 遍历当前节点的所有邻居
    for (Node* neighbor : current->adjacents) {
        if (!visited.count(neighbor)) { // 如果邻居未访问
            // 将邻居压入栈
            stack.push(neighbor);
        }
    }
}

3. 主深度优先遍历函数`dfs()`, 起始于给定的起始顶点`start`。

void dfs(Node* start) {
    stack<Node*> stack;
    unordered_set<Node*> visited;

    // 将起点压入栈
    stack.push(start);
    visited.insert(start);

    while (!stack.empty()) {
        Node* current = stack.top();
        stack.pop();

        dfsHelper(current, stack, visited);
    }
}

4. 调用`dfs()`函数开始遍历：

int main() {
    // 初始化图和顶点v
    // ...

    // 调用dfs遍历
    dfs(&v);

    return 0;
}