程式師世界 >> 編程語言 >> C語言 >> 關於C語言 >> 圖模板（二）——遍歷

圖模板（二）——遍歷

編輯：關於C語言

        圖模板一）已經更新）主要實現了圖的一些基本操作，如添加/刪除頂點，添加/刪除邊等。這篇文章主要實現基於棧和隊列消除遞歸）的圖的深度優先遍歷算法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);
    }
      }
  }
    }