graph_bas.h

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

//---------------------------------------------------------------------------
#ifndef GRAPH_BAS_H_
#define GRAPH_BAS_H_
//---------------------------------------------------------------------------
#include <iostream>
#include <list>
#include <vector>
#include "Graph_Input.h"
using namespace std;

template <class T>
class graph_bas
{
    private:
       typedef vector<list<T> > AdjacencyLists;
       // 顶点数
       int vertexNum;
       // 边数
       int edgeNum;
    protected:
       // 保存顶点数据的链表
       list<T> vertexList;
       // 邻接链表
       AdjacencyLists AdjLists;
    public:
       // 图类型信息
       bool gType;
       // 返回顶点位置
       int GetVertexPos(const T& vertext);
       // 重载下标运算符
       list<size_t>& operator[](size_t i) { return AdjLists[i]; }
       // 图构造器: 创建空图对象
       graph_bas() { }
       // 图构造器: 创建基于邻接链表的图对象（不带权值）
       graph_bas(graphInfo<T> ginfor);
       // 返回保存顶点数据的链表
       list<T> GetvertexList() { return vertexList; }
       // 返回图顶点数
       int GetnumVertices(void) const { return vertexNum; }
       // 返回图边数
       int GetnumEdges(void) const { return edgeNum; }
       // 输出链表
       void print_List(char *c,list<T> L);
       // 输出邻接链表
       void print_AdjLists(char *c);
};

// 不带权值的无向图/有向图构造器
template <class T>
graph_bas<T>::graph_bas(graphInfo<T> ginfor):
  vertexNum(ginfor.numV),edgeNum(ginfor.numE),
  AdjLists(ginfor.numV),gType(ginfor.directedGraph)
{
   T vertex;
   T vertex1,vertex2;
   for(int i=0; i<vertexNum; i++) {     // 建立供查找的顶点链表
      vertex=ginfor.vexs[i];
      vertexList.push_back(vertex);     // 插入顶点到一个顶点链表尾部
   }
   for(i=0; i<edgeNum; i++) {
     vertex1 = ginfor.edges[i].v1;
     vertex2 = ginfor.edges[i].v2;
     // 无向图建邻接链表时，顶点1和2是互相邻接的，插入到邻接链表首部
     AdjLists[GetVertexPos(vertex1)].push_front(vertex2);
     // 对于有向图，顶点1和2邻接是单向的，不执行下面插入语句
     if(!gType)
        AdjLists[GetVertexPos(vertex2)].push_front(vertex1);
   }
   for(i=0; i<vertexNum; i++)
      AdjLists[i].push_front(ginfor.vexs[i]); // 插入顶点到顶点链表首部
}

template <class T>
int graph_bas<T>::GetVertexPos(const T& vertex)
{
   list<T>::iterator itr;         // 声明链表迭代器
   itr = vertexList.begin();      // 迭代器指向顶点链表首元素
   int pos = 0;
   // 查找指定顶点的位置
   while(itr!=vertexList.end() && (*itr) != vertex) {
      ++pos;
      ++itr;
   }
   return pos;
}
// 链表存储数据的公用显示函数
template <class T>
void graph_bas<T>::print_List(char *c,list<T> L)
{
   list<T>::iterator it;
   cout << c;
   for (it=L.begin(); it!=L.end(); it++)
      cout << *it << "   ";
   cout << endl;
  
}

template <class T>
void graph_bas<T>::print_AdjLists(char *c)
{ 
   cout << c << endl;
   list<VertexNode<T,T1> >::const_iterator it;
   for (int k=0; k<GetnumVertices(); k++) {
      for (it=AdjLists[k].begin(); it!=AdjLists[k].end(); it++)
         if (it==AdjLists[k].begin())
            cout << "《" << it->flag << "，id: " << it->id << "》";
         else
            cout << "→《" << it->flag << "，dut: " << it->dut << "》";
      cout << endl;
   }
}

#endif