圖模板（二）——遍歷

        圖模板一）已經更新）主要實現了圖的一些基本操作，如添加/刪除頂點，添加/刪除邊等。這篇文章主要實現基於棧和隊列消除遞歸）的圖的深度優先遍歷算法DFS和廣度優先遍歷算法BFS。         注：其中代碼只是片段，可以下載附件的源代碼        如果你看過圖模板一），就會知道，我們的最終目的是想實現一個類似下式的函數：
        template<typename V, typename K, typename W>
        void BFSTraverse(const graph<V,K,W>& g, const K& k, graph_visitor<V,W>& f)；
        其中，V，K，W分別表示頂點信息數據，頂點索引字，某條弧的權值。
        函數的意義是：從關鍵字k指定的頂點開始，遍歷圖g或者圖g的某個連通分量，對於到達的節點，訪問規則由f決定。
        算法之外，主要的問題是graph_visitor如何實現？這裡提供兩中實現方法：
        一、應用非類型的類模板參數。
        注意區別：
        template<typename T>...中的T是類的類型
        template<char>...中的char是一個內建類型，就是一個具體的類，它就是非類型的模板參數。基於此，我們可以這樣寫graph_visitor：
        template<typename V, typename W,  void (*F) (V&, W&)>
        class{...};
        表達式的含義：F是一個函數指針，這種函數沒有返回值，接受兩個輸入參數，分別是V和W類型的實參引用。F相關於V和W。
        行不行？在vs2005上測試通過。
        代碼很簡單，如下，它僅僅重載了operator()，調用方式類似於：graph_visitor<string, string, f0> visitor0; visitor0(s, i);
template<typename V, typename W, void (*F)(V&, W&)>  
    class easy_visitor  
    {  
    public:  
  void operator()(V& v, W& w){  
      return F(v,w);  
  }  
    protected:  
    private:  
    };
        
        問：既然如此，為什麼不把遍歷函數聲明成這樣？
        template<typename V, typename K, typename W, void(*F)(V&,W&)>
        void BFSTraverse(const graph<V,K,W>& g, const K& k)；
        這樣看起來可以，也的確可以，但訪問節點的規則是多種多樣的，F種類太多，而且F有可能是多種函數的組合，我們不希望因為更改了F的種類就要重新編寫BFS。對於不同的種類F，我們只需要修改seay_visitor，簡單得多。         二、利用C++的多態性和模板成員函數。代碼如下： template <typename V, typename W>  
    class graph_visit_base  
    {  
    public:  
  
    virtual void operator() (V& x, W& w)=0;  
  
    virtual graph_visit_base<V,W>*  clone() const=0;  
  
    virtual ~graph_visit_base(){}  
  
    protected:  
    private:  
    };//純虛基類  
  
    template <typename F, typename V, typename W>  
    class graph_visit_f : public graph_visit_base<V,W>  
    {  
    public:  
  
  graph_visit_f(F f0):f(f0){}  
  
  graph_visit_f(const graph_visit_f<F,V,W>& other):f(other.f){}  
  
  virtual void operator() (V& v, W& w){  
      return f(v,w);  
  }  
  
  virtual graph_visit_base<V,W>* clone() const{  
      return new graph_visit_f<F,V,W>(*this);  
  }  
  
    protected:  
    private:  
  F f;  
    };  
  
    template <typename V, typename W>  
    class graph_visitor  
    {  
    public:  
  template<typename F> graph_visitor(F f)  
    :_p(new graph_visit_f<F,V,W>(f)){}  
  
  //拷貝構造  
      graph_visitor(const graph_visitor<V,W>& other):_p(other._p->clone()){}  
  
  //重載=  
  virtual graph_visitor& operator= (const graph_visitor& rhs){  
      if(&rhs!=this)  
      {  
    delete _p;  
    _p=rhs._p->clone();  
      }  
      return *this;  
  }  
  
  //重載()  
  virtual void operator() (V& v, W& w) const{  
      return _p->operator ()(v, w);  
  }  
  
  //析構  
  virtual ~graph_visitor(){  
      delete _p;  
  }  
  
    protected:  
    private:  
  graph_visit_base<V,W>* _p;  
    };
                
        純虛基類graph_visit_base包裝了數據信息。
        基於graph_visit_base的繼承類graph_visit_f引入了函數對象或者函數指針）F，從而為數據信息提供了訪問規則。
        模板類graph_visitor則在此隱藏了訪問規則F，F不在是該模板一個模板參數，而是一個作為構造函數的一個模板參數。這裡模板函數是一個模板成員，而且是一個構造函數據說有些低級的編譯器沒有提供這種編譯特性，但我想10多年過去了，不支持的應該很少很少吧。）
        另外，virtual graph_visit_base<V,W>* clone() const{return new graph_visit_f<F,V,W>(*this);至關重要，他把子類指針轉化成為基類指針，從而避免了graph_visitor模板不必要F參數。試想：如果graph_visit_base<V,W>* _p;改成graph_visit_f<F,V,W>* _p;，不可避免的要修改graph_visitor的模板參數。
       調用法： graph_visitor<string, string> visitor0(f0); visitor0(s, i);
       問：有必要把上面的簡單構造改得這麼復雜嗎？我想，最簡單的一條就是調用習慣，這種方式更像是C吧。比較一下：
        graph_visitor<string, string, f0,f1,f2,f3,f4> visitor0; visitor0(s, i);
        graph_visitor<string, string> visitor0(f0,f1,f2,f3,f4); visitor0(s, i);
其次，我們這裡的需求是如此的簡單，如果考慮更多的細節和更加泛型化的需求，這個方式必然是優於前者的，比如增加policy和trait等其他性質時。這些就復雜了，暫時還談不了。stl等泛型設計中都是後者。           關於算法原理，這裡也不多說了，我也是參考數據結構寫的。這裡主要是針對本數據結構，對於遍歷某個頂點節點的弧時，采用了棧或者隊列的方式。大家仔細琢磨琢磨，也許還有更優的選擇。
        代碼如下：   由外部函數轉成類成員函數通常使用如下手段： //DSF graph成員
  inline void DSF(const K& key, graph_visitor<V,W>& visitor){
   DFSTraverse<V,K,W>(*this, key, visitor);
  }
  //BSF graph成員
  inline void BSF(const K& key, graph_visitor<V,W>& visitor){
   BFSTraverse<V,K,W>(*this, key, visitor);
  }
inline bool visited_vertex(unsigned int index, std::vector<bool>& vec)  
    {  
  unsigned int i=0;  
  for(; i<(unsigned int)vec.size(); i++)  
      if(i==index) break;  
  return vec[i];  
    }  
  
    //從k指定的頂點節點開始，用f函數遍歷圖g(或它的一個連通分量),棧實現  
    template<typename V, typename K, typename W>  
    void DFSTraverse(const graph<V,K,W>& g, const K& k, graph_visitor<V,W>& f)  
    {  
  typedef redwolf::graph<V,K,W>::size_type size_type;  
  typedef redwolf::vertex<V,K> VERTEX;  
  typedef typename redwolf::graph<V,K,W>::const_iterator const_iterator;  
  
  std::stack<size_type> versta;//棧，用於回溯，消除遞歸,  
  std::stack<size_type> arcsta;//存放vsta中頂點對應的出邊終點節點序號  
  std::vector<bool> vervec;//用於標示索引位置的vertex是否被訪問過  
  const_iterator git;  
  VERTEX vert;  
  W weight=W();  
  size_type verindex=0;//頂點節點序號  
     size_type arcindex=0;//將要被訪問的弧頭序號  
  
  //初始化vvec  
  for(int i=0; i<(int)g.vertex_size(); i++)  
      vervec.push_back(false);  
  
  bool b=g.vertex_existed(k, verindex);  
  if(!b) return;  
  git=g.get_vertex_node(verindex);  
  vert=git->get_head();  
  versta.push(verindex);  
  arcsta.push(arcindex);  
  vervec[verindex]=true;  
  f(vert.get_data(), weight);  
  
  while(!versta.empty())  
  {  
      //由於i_visiting是按順序訪問的，  
      //一旦找不到，說明該節點的所有弧頭都被訪問過了  
      verindex=versta.top();  
      arcindex=arcsta.top();  
      arcsta.pop();  
      arcsta.push((unsigned int)arcindex+1);  
      git=g.get_vertex_node(verindex);  
      bool b=git->get_tail(arcindex, vert, weight);  
      if(!b)  
      {  
    versta.pop();  
    arcsta.pop();  
      }  
      else  
      {  
    g.vertex_existed(vert.get_key(), verindex);  
    git=g.get_vertex_node(verindex);  
    if(!visited_vertex((unsigned int)verindex, vervec))  
    {  
        vert=git->get_head();  
        versta.push(verindex);  
        arcsta.push(0);  
        vervec[verindex]=true;  
        f(vert.get_data(), weight);  
    }  
      }  
  }  
    }  
  
    //從k指定的頂點節點開始，用f函數遍歷圖g(或它的一個連通分量),隊列實現  
    template<typename V, typename K, typename W>  
    void BFSTraverse(const graph<V,K,W>& g, const K& k, graph_visitor<V,W>& f)  
    {  
  typedef redwolf::graph<V,K,W>::size_type size_type;  
  typedef redwolf::vertex<V,K> VERTEX;  
  typedef typename redwolf::graph<V,K,W>::const_iterator const_iterator;  
  
  std::deque<size_type> verqueue;//消除遞歸,  
  std::deque<size_type> arcqueue;//存放verqueue中頂點對應的出邊終點節點序號  
  std::vector<bool> vervec;//用於標示索引位置的vertex是否被訪問過  
  const_iterator git;  
  VERTEX vert;  
  W weight=W();  
  size_type verindex=0;//頂點節點序號  
     size_type arcindex=0;//將要被訪問的弧頭序號  
  
  //初始化vvec  
  for(int i=0; i<(int)g.vertex_size(); i++)  
      vervec.push_back(false);  
  
  bool b=g.vertex_existed(k, verindex);  
  if(!b) return;  
  git=g.get_vertex_node(verindex);  
  vert=git->get_head();  
  verqueue.push_back(verindex);  
  arcqueue.push_back(arcindex);  
  vervec[verindex]=true;  
  f(vert.get_data(), weight);  
  
  while(!verqueue.empty())  
  {  
      //由於i_visiting是按順序訪問的，  
      //一旦找不到，說明該節點的所有弧頭都被訪問過了  
      verindex=verqueue.at(0);//隊頭  
      arcindex=arcqueue.at(0);  
      arcqueue.pop_front();  
      arcqueue.push_front((unsigned int)arcindex+1);  
      git=g.get_vertex_node(verindex);  
      bool b=git->get_tail(arcindex, vert, weight);  
      if(!b)  
      {  
    verqueue.pop_front();  
    arcqueue.pop_front();  
      }  
      else  
      {  
    g.vertex_existed(vert.get_key(), verindex);  
    git=g.get_vertex_node(verindex);  
    if(!visited_vertex((unsigned int)verindex, vervec))  
    {  
        vert=git->get_head();  
        verqueue.push_back(verindex);  
        arcqueue.push_back(0);  
        vervec[verindex]=true;  
        f(vert.get_data(), weight);  
    }  
      }  
  }  
    }

本文出自 “狼窩” 博客，請務必保留此出處http://redwolf.blog.51cto.com/427621/88854