面试题：C++ 实现简单图的深度优先搜索

#include <iostream>
#include <vector>
#include <unordered_set>

struct GraphNode {
    int val;
    std::vector<GraphNode*> neighbors;
    GraphNode(int x) : val(x) {};
};

void dfs(GraphNode* node, std::unordered_set<GraphNode*>& visited, std::vector<int>& result) {
    visited.insert(node);
    result.push_back(node->val);
    for (GraphNode* neighbor : node->neighbors) {
        if (visited.find(neighbor) == visited.end()) {
            dfs(neighbor, visited, result);
        }
    }
}

std::vector<int> depthFirstSearch(GraphNode* start) {
    std::unordered_set<GraphNode*> visited;
    std::vector<int> result;
    dfs(start, visited, result);
    return result;
}

你可以这样调用函数：

int main() {
    // 构建图
    GraphNode* node1 = new GraphNode(1);
    GraphNode* node2 = new GraphNode(2);
    GraphNode* node3 = new GraphNode(3);
    node1->neighbors.push_back(node2);
    node2->neighbors.push_back(node1);
    node2->neighbors.push_back(node3);
    node3->neighbors.push_back(node2);

    std::vector<int> traversalOrder = depthFirstSearch(node1);
    for (int val : traversalOrder) {
        std::cout << val << " ";
    }
    return 0;
}

上述代码中，dfs 函数是实际进行深度优先搜索的递归函数，它接受当前节点、已访问节点集合和结果向量作为参数。depthFirstSearch 函数初始化相关参数并调用 dfs 函数开始搜索。在 main 函数中构建了一个简单的图并调用 depthFirstSearch 函数输出从起始节点开始的遍历顺序。

星途面试题库

面试题：C++ 实现简单图的深度优先搜索

知识考点

面试题答案