C++怎么实现深度优先搜索(DFS)_C++图与树的遍历算法详解

class Graph { int V; // 节点数量 vector<vector<int>> adj; // 邻接表 void dfsUtil(int v, vector<bool>& visited);

public: Graph(int V); void addEdge(int v, int w); void dfs(int start); };

Graph::Graph(int V) { this->V = V; adj.resize(V); }

void Graph::addEdge(int v, int w) { adj[v].push_back(w); adj[w].push_back(v); // 无向图双向添加 }

void Graph::dfsUtil(int v, vector<bool>& visited) { visited[v] = true; cout << v << " ";

for (int neighbor : adj[v]) {
    if (!visited[neighbor]) {
        dfsUtil(neighbor, visited);
    }
}

}

立即学习“C++免费学习笔记（深入）”；

void Graph::dfs(int start) { vector<bool> visited(V, false); dfsUtil(start, visited); }

// 前序遍历：根 -> 左 -> 右 void preorder(TreeNode* root) { if (root == nullptr) return; cout << root->val << " "; preorder(root->left); preorder(root->right); }

// 中序遍历：左 -> 根 -> 右 void inorder(TreeNode* root) { if (root == nullptr) return; inorder(root->left); cout << root->val << " "; inorder(root->right); }

// 后序遍历：左 -> 右 -> 根 void postorder(TreeNode* root) { if (root == nullptr) return; postorder(root->left); postorder(root->right); cout << root->val << " "; }

void dfsIterative(Graph& g, int start) { int V = g.V; vector<bool> visited(V, false); stack<int> s;

s.push(start);

while (!s.empty()) {
    int v = s.top();
    s.pop();

    if (!visited[v]) {
        cout << v << " ";
        visited[v] = true;
    }

    // 将所有未访问的邻接点压入栈（注意顺序可影响输出）
    for (auto it = g.adj[v].rbegin(); it != g.adj[v].rend(); ++it) {
        if (!visited[*it]) {
            s.push(*it);
        }
    }
}

}