graph_trav.h

数据结构与算法设计学习得素材

//---------------------------------------------------------------------------
#ifndef GRAPH_TRAV_H_
#define GRAPH_TRAV_H_
//---------------------------------------------------------------------------
#include <queue>
#include <deque>
#include <stack>
#include <vector>
#include <list>
#include <algorithm>
#include "Graph_Bas.h" 

template <class T>
class graph_traver: public graph_bas<T>
{
    public:
       // 不带权值图构造器
       graph_traver(graphInfo<T> ginfo): graph_bas<T>(ginfo){ }
       // 先深遍历搜索
       list<T>& dfs(const T& beginVertex);
       // 先广遍历搜索
       list<T>& bfs(const T& beginVertex);
       // 计算无向图连通分量
       void component();
       // 计算有向图强连通分量
       void strong_component();
       // 判断图连通性
       bool isconnected();
       bool findVertex(list<T>& L,const T &vertex) {
       	  if(find(L.begin(),L.end(),vertex) != L.end())
	         return true;
	      else
	         return false;
       }
//    private:
    protected:
       bool pathconnect(T u,T w) {
          list<T> L = dfs(u);
          if(find(L.begin(),L.end(),w) != L.end())
             return 1;
          else
             return 0;
       }
};

template <class T>
list<T>& graph_traver<T>::dfs(const T& beginVertex)
{
   stack<T> S;
   list<T> *L,adjL;                   // L必须是一个指针，以便返回到引用
   list<T>::iterator itr;
   L = new list<T>;                   // 分配内存
   S.push(beginVertex);               // 顶点入栈
   while(!S.empty()) {
      T vertex = S.top();             // 取栈顶元素
      S.pop();                        // 顶点出栈
      if(! findVertex(*L, vertex)) {
         (*L).push_back(vertex);
         adjL = AdjLists[GetVertexPos(vertex)];
         for(itr=adjL.begin(); itr!=adjL.end(); ++itr)
            if(! findVertex(*L, *itr))
               S.push(*itr);
      }
   }
   return *L;                         // 返回到一个引用
}

template <class T>
list<T>& graph_traver<T>::bfs(const T& beginVertex)
{
   queue<T> Q;                        // 声明一个队列
   list<T> *L,adjL;
   list<T>::reverse_iterator itrev;
   T vertex;
   L = new list<T>;
   Q.push(beginVertex);               // 起始顶点入队
   while(!Q.empty()) {
      vertex = Q.front();
      Q.pop();                        // 出队
      if(!findVertex(*L,vertex)) {
         (*L).push_back(vertex);
	     adjL = AdjLists[GetVertexPos(vertex)];
         for(itrev=adjL.rbegin(); itrev!=adjL.rend(); itrev++)
	        if(!findVertex(*L,*itrev))
	           Q.push(*itrev);        // 新的邻接顶点入队
      }
   }
   return *L;
}

template <class T>
void graph_traver<T>::component()
{
   int count=0;
   vector<int> visited(GetnumVertices());
   list<T> L,vList=GetvertexList();
   list<T>::const_iterator it,itr;
   for(it=vList.begin(); it!=vList.end(); it++) {
      if (!visited[GetVertexPos(*it)]) {
         count++;
         L = bfs(*it);
         print_List("无向图连通分量：", L);
         for (itr=L.begin(); itr!=L.end(); itr++)
           visited[GetVertexPos(*itr)]=1;
      }
   }
   cout << "连通分量个数＝" << count << endl;
}

template <class T>
void graph_traver<T>::strong_component()
{
   int count=0;
   list<T> L,vList=GetvertexList(),markedList,scList;
   list<T>::const_iterator it,itr;
   for(it=vList.begin(); it!=vList.end(); it++) {
      if(find(markedList.begin(),markedList.end(),*it) == markedList.end()) {
         count++;
         scList.clear();
         L = bfs(*it);
         itr=L.begin();
         while(itr!=L.end()) {
           if(pathconnect(*itr,*it)) {
              scList.push_back(*itr);
              markedList.push_back(*itr);
           }
           itr++;
         }
         print_List("有向图强连通分量: ", scList);
      }
   }
   cout << "强连通分量个数＝" << count << endl;
}

// 判断图连通性
template <class T>
bool graph_traver<T>::isconnected()
{
   list<T> vList=GetvertexList(), L;
   list<T>::const_iterator it;
   for(it=vList.begin(); it!=vList.end(); it++) {
     L = bfs(*it);
     if(L.size()<vList.size())
        return false;
   }
   return true;
}
#endif