C++ 圖模板庫實戰 (二)：非遞迴 DFS/BFS 遍歷與訪問者模式泛型設計

編輯：關於C語言

系列回顧與本章目標

上一章實作了圖的基本操作（增刪頂點/邊）。本章攻克兩大核心課題：

非遞迴遍歷演算法：使用 std::stack 實作 DFS、std::deque 實作 BFS，消除遞迴呼叫堆疊溢位風險
泛型訪問者設計：支援函數指標、函數物件、Lambda、成員函數等多種可呼叫實體，實現演算法與業務邏輯完全解耦

訪問者模式的兩種泛型實現策略

策略一：非型別模板參數（編譯期綁定，零開銷）

template <typename V, typename W, void (*F)(V&, W&)>
class easy_visitor {
public:
    void operator()(V& v, W& w) { return F(v, w); }
};

// 使用方式
void my_visitor(string& data, string& weight) { /* ... */ }
easy_visitor<string, string, my_visitor> visitor;
visitor(node_data, edge_weight);

優點： 編譯期內聯、零間接呼叫開銷、型別安全。
缺點： 訪問邏輯變更需重新編譯遍歷函數模板實例（程式碼膨脹）。

策略二：多態 + 模板成員函數（執行期多態，極致彈性）

核心類別體系：

// 1. 純虛基類：定義訪問介面與複製語意
template <typename V, typename W>
class graph_visit_base {
public:
    virtual void operator()(V& v, W& w) = 0;
    virtual graph_visit_base<V,W>* clone() const = 0;  // 關鍵：虛擬複製建構子
    virtual ~graph_visit_base() {}
};

// 2. 具體適配器：包裝任意可呼叫物 F
template <typename F, typename V, typename W>
class graph_visit_f : public graph_visit_base<V,W> {
    F f;
public:
    graph_visit_f(F f0) : f(f0) {}
    graph_visit_f(const graph_visit_f& other) : f(other.f) {}
    void operator()(V& v, W& w) override { return f(v, w); }
    graph_visit_base<V,W>* clone() const override { 
        return new graph_visit_f<F,V,W>(*this); 
    }
};

// 3. 類型擦除外觀：隱藏 F，提供值語意
template <typename V, typename W>
class graph_visitor {
    graph_visit_base<V,W>* _p;
public:
    template <typename F> 
    graph_visitor(F f) : _p(new graph_visit_f<F,V,W>(f)) {}
    
    graph_visitor(const graph_visitor& other) : _p(other._p->clone()) {}
    graph_visitor& operator=(const graph_visitor& rhs) {
        if (&rhs != this) { delete _p; _p = rhs._p->clone(); }
        return *this;
    }
    void operator()(V& v, W& w) const { return (*_p)(v, w); }
    ~graph_visitor() { delete _p; }
};

關鍵設計解析：`clone()` 虛擬複製建構子

為什麼需要 clone()？

graph_visitor 持有基類指標 _p
拷貝/指派時需複製具體衍生類物件，而非基類指標（淺拷貝會導致雙重釋放）
基類宣告 virtual clone()，衍生類回傳 new Derived(*this)，實現型別擦除下的深拷貝
這是經典的 Prototype 模式 應用，也是 std::function 內部實現原理之一

使用示範：支援 Lambda、函數物件、成員函數

// Lambda
graph_visitor<string, string> v1([](auto& data, auto& w) { cout << data; });

// 函數物件
struct Printer { void operator()(string& d, string& w) { /* ... */ } };
graph_visitor<string, string> v2(Printer{});

// 成員函數 (需 std::bind 或 Lambda 捕獲 this)
class Analyzer { 
public: void process(string& d, string& w) { /* ... */ } 
};
Analyzer analyzer;
graph_visitor<string, string> v3([&](auto& d, auto& w) { analyzer.process(d, w); });

非遞迴 DFS 實作詳解

資料結構：

versta (stack<size_type>)：頂點索引堆疊，模擬遞迴呼叫堆疊
arcsta (stack<size_type>)：平行堆疊，記錄當前頂點「下一條待探索邊」的索引
vervec (vector<bool>)：訪問標記陣列

核心邏輯：

template <typename V, typename K, typename W>
void DFSTraverse(const graph<V,K,W>& g, const K& k, graph_visitor<V,W>& f) {
    using size_type = typename graph<V,K,W>::size_type;
    using VERTEX = vertex<V,K>;
    
    stack<size_type> versta, arcsta;
    vector<bool> vervec(g.vertex_size(), false);
    
    size_type verindex, arcindex = 0;
    if (!g.vertex_existed(k, verindex)) return;
    
    // 初始化：起始頂點入堆疊
    versta.push(verindex);
    arcsta.push(0);
    vervec[verindex] = true;
    f(g.get_vertex_node(verindex)->get_head().get_data(), W());
    
    while (!versta.empty()) {
        verindex = versta.top();
        arcindex = arcsta.top();
        arcsta.pop();
        arcsta.push(arcindex + 1);  // 下一次探索下一條邊
        
        VERTEX vert;
        W weight;
        auto git = g.get_vertex_node(verindex);
        bool has_edge = git->get_tail(arcindex, vert, weight);
        
        if (!has_edge) {  // 當前頂點所有邊探索完畢
            versta.pop();
            arcsta.pop();
            continue;
        }
        
        // 發現鄰接頂點
        size_type next_verindex;
        g.vertex_existed(vert.get_key(), next_verindex);
        if (!vervec[next_verindex]) {
            vervec[next_verindex] = true;
            versta.push(next_verindex);
            arcsta.push(0);  // 新頂點從第 0 條邊開始探索
            f(vert.get_data(), weight);
        }
    }
}

非遞迴 BFS 實作詳解

資料結構差異： 將堆疊改為雙端佇列 std::deque（或 std::queue），實現先進先出。

template <typename V, typename K, typename W>
void BFSTraverse(const graph<V,K,W>& g, const K& k, graph_visitor<V,W>& f) {
    using size_type = typename graph<V,K,W>::size_type;
    using VERTEX = vertex<V,K>;
    
    deque<size_type> verqueue, arcqueue;
    vector<bool> vervec(g.vertex_size(), false);
    
    size_type verindex, arcindex = 0;
    if (!g.vertex_existed(k, verindex)) return;
    
    verqueue.push_back(verindex);
    arcqueue.push_back(0);
    vervec[verindex] = true;
    f(g.get_vertex_node(verindex)->get_head().get_data(), W());
    
    while (!verqueue.empty()) {
        verindex = verqueue.front();   // 隊頭
        arcindex = arcqueue.front();
        arcqueue.pop_front();
        arcqueue.push_front(arcindex + 1);
        
        VERTEX vert;
        W weight;
        auto git = g.get_vertex_node(verindex);
        bool has_edge = git->get_tail(arcindex, vert, weight);
        
        if (!has_edge) {
            verqueue.pop_front();
            arcqueue.pop_front();
            continue;
        }
        
        size_type next_verindex;
        g.vertex_existed(vert.get_key(), next_verindex);
        if (!vervec[next_verindex]) {
            vervec[next_verindex] = true;
            verqueue.push_back(next_verindex);  // 入隊尾
            arcqueue.push_back(0);
            f(vert.get_data(), weight);
        }
    }
}

圖類別整合：成員函數封裝


template <typename V, typename K, typename W>
class graph {
    // ... 
public:
    inline void DFS(const K& key, graph_visitor<V,W>& visitor) {
        DFSTraverse<V,K,W>(*this, key, visitor);
    }
    inline void BFS(const K& key, graph_visitor<V,W>& visitor) {
        BFSTraverse<V,K,W>(*this, key, visitor);
    }
};

效能與設計權衡總結

維度	策略一：非型別模板參數	策略二：型別擦除 + 多態
執行效能	極致（內聯、無虛函數）	極微小虛函數開銷（可忽略）
程式碼膨脹	每個訪問函數產生獨立模板實例	單一 `graph_visitor` 實例，無膨脹
彈性	僅限函數指標	支援 Lambda、bind、函數物件、成員函數
編譯相依	訪問函數變更需重編遍歷模板	訪問邏輯變更不影響遍歷編譯單元
適用場景	高效能、固定訪問邏輯、嵌入式	通用庫、插件架構、動態載入訪問邏輯