我想要在Boost Graph Library（BGL）的图中查找从起点到终点的所有路径，因此选用了DFS算法。但默认DFS会标记已访问的顶点，导致无法获取包含重复顶点的路径。

我的思路是：用栈记录访问节点，找到终点后保存路径，并取消该路径中除起点外所有节点的标记，重新开始搜索；若未找到终点且当前节点无出边，则丢弃该路径，重新搜索直至遍历完所有路径。我已在简单C++程序中实现该修改版DFS且可正常运行，但在BGL中遇到无法取消已使用节点标记的问题，现附上相关代码、当前输出及期望输出：

相关代码 #

#include <boost/graph/adjacency_list.hpp>
#include <boost/graph/depth_first_search.hpp>
#include <boost/graph/graphviz.hpp>
#include <boost/unordered_map.hpp>
#include <boost/graph/graph_utility.hpp>
#include <iostream>
using namespace std;
using namespace boost;
namespace graphProps {
struct VertexProps {
    unsigned int vertexID;
    std::string vertexName;
};
struct EdgeProps {
    unsigned int edgeID;
    std::string edgeName;
};
}
typedef boost::adjacency_list < boost::listS, boost::vecS, boost::directedS,
//vertex properties
boost::property < boost::vertex_name_t, std::string, boost::property<boost::vertex_index_t, int, graphProps::VertexProps> >,
//edge properties
boost::property< boost::edge_weight_t, int, boost::property<boost::edge_index_t, int, graphProps::EdgeProps > >,
boost::property<vertex_color_t, default_color_type> > mygraph;
typedef boost::unordered_map<std::string, std::size_t> _map;
typedef std::pair<mygraph::vertex_descriptor, mygraph::vertex_descriptor> edgePair;
using colormap = std::map<mygraph::vertex_descriptor, default_color_type>;
class PathDFSVisitor :public boost::default_dfs_visitor {
public:
    colormap vertex_coloring;
    mygraph *m_path;
    std::vector<edgePair> *m_edgePair;
    boost::unordered_map<std::string, std::size_t> *m_pathNumMap;
    std::vector<mygraph::vertex_descriptor> m_spath;
    int m_source;
    int m_destination;
    bool m_foundDest = false;
    bool m_pathFinished = false;
    bool *m_result;
    int path_index = 0;
    PathDFSVisitor(boost::unordered_map<std::string, std::size_t> *inMap, std::vector<edgePair> *edgePair) {
        m_edgePair = edgePair;
        m_pathNumMap = inMap;
    }
    PathDFSVisitor(std::vector<edgePair> *edgePair, int source, int destination, bool *result) {
        m_edgePair = edgePair;
        m_source = source;
        m_destination = destination;
        m_result = result;
    }
    template < typename Vertex, typename Graph >
    void discover_vertex(Vertex u, const Graph & g) {
        mygraph::vertex_descriptor vertex;
        vertex = boost::vertex(u, g);
        default_color_type color = vertex_coloring[u];
        std::cout << "Discover at: " << u << " with color " << color << std::endl;
        m_spath.push_back(vertex);
        path_index++;
    }
    template < typename Vertex, typename Graph >
    void finish_vertex(Vertex u, const Graph & g) {
        mygraph::vertex_descriptor vertex;
        default_color_type color = vertex_coloring[u];
        std::cout << "Finish vertex at: " << u << " with color " << color << std::endl;
        for (int i = path_index; i > 1; i--) {
            vertex = boost::vertex(m_spath[i-1], g);
            vertex_coloring[vertex] = white_color;
            std::cout << "Unmarking vertex: " << vertex << std::endl;
            m_spath.pop_back();
            path_index--;
        }
    }
};
void addVertex(unsigned int vertexID, std::string vertexName, mygraph &graph) {
    mygraph::vertex_descriptor vert;
    //add vertex and intialize
    vert = boost::add_vertex(graph);
    graph[vert].vertexID = vertexID;
    graph[vert].vertexName = vertexName;
}
void addEdge(unsigned int edgeID, unsigned int srcVertexID, unsigned int dstVertexID, std::string edgeName, mygraph &graph) {
    //(1) get vertex descriptor for source and destination vertex
    mygraph::vertex_descriptor src, dst;
    //add vertex and intialize
    src = boost::vertex(srcVertexID, graph);
    dst = boost::vertex(dstVertexID, graph);
    //set edge properties between source and destination vertex
    boost::add_edge(src, dst, graph);
    //(2)get edge descriptor
    auto e = boost::edge(boost::vertex(srcVertexID, graph), boost::vertex(dstVertexID, graph), graph).first;
    //initialize edge properties
    graph[e].edgeID = edgeID;
    graph[e].edgeName = edgeName;
}
int main() {
    mygraph g,l;
    std::vector<edgePair> path;
    addVertex(0, "A", g);
    addVertex(1, "B", g);
    addVertex(2, "C", g);
    addVertex(3, "D", g);
    addVertex(4, "E", g);
    addVertex(5, "F", g);
    addEdge(0, 1, 0, "BA", g);
    addEdge(1, 1, 4, "BD", g);
    addEdge(2, 1, 2, "BC", g);
    addEdge(2, 0, 3, "AD", g);
    addEdge(3, 4, 3, "ED", g);
    addEdge(4, 4, 2, "EC", g);
    addEdge(5, 3, 5, "DF", g);
    addEdge(6, 3, 1, "DB", g);
    addEdge(6, 4, 1, "EB", g);
    bool searchState = false;
    std::size_t start = 1;
    std::size_t stop = 5;
    PathDFSVisitor vis(&path,start,stop,&searchState);
    depth_first_search(g, visitor(vis).root_vertex(start));
    //build graph which contains (only) all paths between start and stop vertex
    std::vector<edgePair>::iterator it;
    for (it = path.begin(); it != path.end(); ++it) {
        boost::add_edge(it->first, it->second, l);
    }
    std::ofstream f("Graph.dot");
    write_graphviz(f, g);
    f.close();
    system("renderGraph.bat");
    std::cin.get();
}

当前输出 #

Discover at: 1 with color 0
Discover at: 0 with color 0
Discover at: 3 with color 0
Discover at: 5 with color 0
Finish vertex at: 5 with color 0
Unmarking vertex: 5
Unmarking vertex: 3
Unmarking vertex: 0
Finish vertex at: 3 with color 0
Finish vertex at: 0 with color 0
Discover at: 4 with color 0
Discover at: 2 with color 0
Finish vertex at: 2 with color 0
Unmarking vertex: 2
Unmarking vertex: 4
Finish vertex at: 4 with color 0
Finish vertex at: 1 with color 0

期望输出路径 #

期望能获取两条路径：{1,0,3,5} 和 {1,4,3,5}

问题分析与解决方案 #

我帮你梳理下核心问题：BGL的depth_first_search算法本身依赖于颜色映射来跟踪顶点的访问状态，但你自己维护的vertex_coloring和算法内部使用的颜色映射是完全独立的！也就是说，你修改自己的vertex_coloring对DFS的遍历逻辑没有任何影响——算法根本不会读取这个map，它用的是你在图定义中指定的vertex_color_t属性，或者默认的内部颜色存储。

要解决这个问题，有两种可行的思路：

思路1：完全自定义DFS遍历（推荐）

既然你已经在简单程序中实现了自己的DFS逻辑，不如直接在BGL的图上复现这个逻辑，完全控制访问标记和路径跟踪。这样你不需要依赖BGL自带的DFS算法，自由度更高，也能避免和BGL的内部机制冲突。

示例核心逻辑：

stack<pair<mygraph::vertex_descriptor, bool>> dfs_stack;
vector<mygraph::vertex_descriptor> current_path;
colormap visited;

// 初始化所有顶点为未访问
for (auto v : boost::make_iterator_range(boost::vertices(g))) {
    visited[v] = white_color;
}

dfs_stack.push({start, false});
visited[start] = gray_color;
current_path.push_back(start);

while (!dfs_stack.empty()) {
    auto [u, processed] = dfs_stack.top();
    dfs_stack.pop();

    if (processed) {
        // 回溯：取消标记（除起点）并弹出路径
        if (u != start) {
            visited[u] = white_color;
            current_path.pop_back();
        }
        continue;
    }

    // 标记为已处理，再压回去
    dfs_stack.push({u, true});

    // 检查是否到达终点，保存路径
    if (u == stop) {
        for (size_t i = 0; i < current_path.size()-1; ++i) {
            path.emplace_back(current_path[i], current_path[i+1]);
        }
        std::cout << "Found path: ";
        for (auto v : current_path) std::cout << v << " ";
        std::cout << std::endl;
        continue;
    }

    // 反向压栈，保证遍历顺序和DFS一致
    auto adj = boost::adjacent_vertices(u, g);
    for (auto it = adj.second; it != adj.first; ) {
        --it;
        mygraph::vertex_descriptor v = *it;
        if (visited[v] == white_color) {
            visited[v] = gray_color;
            current_path.push_back(v);
            dfs_stack.push({v, false});
        }
    }
}

思路2：让BGL的DFS使用你自定义的颜色映射

如果你一定要用BGL的DFS Visitor机制，那么必须让算法使用你维护的vertex_coloring，而不是默认的颜色存储。具体步骤如下：

1. 修改Visitor的构造函数，传入颜色映射的引用（避免拷贝）
2. 在discover_vertex中使用该颜色映射标记顶点状态
3. 在调用depth_first_search时，通过color_map参数传入你的颜色映射

修改后的关键代码：

修改Visitor类

class PathDFSVisitor :public boost::default_dfs_visitor {
public:
    colormap& vertex_coloring; // 改为引用，共享外部的颜色映射
    std::vector<edgePair> *m_edgePair;
    std::vector<mygraph::vertex_descriptor> m_spath;
    int m_source;
    int m_destination;
    bool *m_result;

    // 构造函数新增颜色映射参数
    PathDFSVisitor(std::vector<edgePair> *edgePair, int source, int destination, bool *result, colormap& coloring) 
        : vertex_coloring(coloring), m_edgePair(edgePair), m_source(source), m_destination(destination), m_result(result) {}

    template < typename Vertex, typename Graph >
    void discover_vertex(Vertex u, const Graph & g) {
        vertex_coloring[u] = gray_color; // 标记为正在访问
        m_spath.push_back(u);
        std::cout << "Discover at: " << u << " with color " << vertex_coloring[u] << std::endl;

        // 检查是否到达终点，保存路径
        if (u == m_destination) {
            for (size_t i = 0; i < m_spath.size()-1; ++i) {
                m_edgePair->emplace_back(m_spath[i], m_spath[i+1]);
            }
            std::cout << "Found path: ";
            for (auto v : m_spath) std::cout << v << " ";
            std::cout << std::endl;
        }
    }

    template < typename Vertex, typename Graph >
    void finish_vertex(Vertex u, const Graph & g) {
        std::cout << "Finish vertex at: " << u << std::endl;
        // 回溯时取消标记（除起点）
        if (u != m_source) {
            vertex_coloring[u] = white_color;
            std::cout << "Unmarking vertex: " << u << std::endl;
        }
        m_spath.pop_back();
    }
};

修改main函数中的DFS调用

int main() {
    // ... 之前的图构建代码不变

    colormap vertex_coloring;
    // 初始化所有顶点为白色（未访问）
    for (auto v : boost::make_iterator_range(boost::vertices(g))) {
        vertex_coloring[v] = white_color;
    }

    bool searchState = false;
    std::size_t start = 1;
    std::size_t stop = 5;
    PathDFSVisitor vis(&path, start, stop, &searchState, vertex_coloring);

    // 调用DFS时传入自定义的颜色映射
    depth_first_search(g, 
        visitor(vis)
        .root_vertex(start)
        .color_map(boost::make_assoc_property_map(vertex_coloring))); // 关键：传入自定义颜色映射

    // ... 后续代码不变
}

这样修改后，BGL的DFS算法会使用你维护的vertex_coloring来跟踪访问状态，你的取消标记操作就能生效，从而遍历到所有包含重复节点的路径，得到你期望的{1,0,3,5}和{1,4,3,5}两条路径。

内容的提问来源于stack exchange，提问作者Freacky2002