#ifndef _GRAPH_H
#define _GRAPH_H

#include 
  
   
#include 
   
     using namespace::std; /////////////////////////////////////////////////////////////////////////////////////////// //通用图结构 template 
    
      class graph{ public: bool is_empty()const; bool is_full()const; int get_numvertices()const; //当前顶点数 int get_numedges()const; //当前边数 public: virtual bool insert_vertex(const T&) = 0; //插入顶点 virtual bool insert_edge(const T&, const T&) = 0; //插入边 virtual bool remove_vertex(const T&) = 0; //删除定点 virtual bool remove_edge(const T&, const T&) = 0; //删除边 virtual int get_firstneighbor(const T&)const = 0; //得到第一个邻接顶点 virtual int get_nextneighbor(const T&, const T&)const = 0; //某邻接顶点的下一个邻接顶点 virtual void print_graph()const = 0; virtual int get_vertex_index(const T&)const = 0; //得到顶点序号 protected: static const int VERTICES_DEFAULT_SIZE = 10; //默认图顶点数 int max_vertices; int num_vertices; int num_edges; }; template 
     
       bool graph
      
       ::is_empty()const { return num_edges == 0; } template 
       
         bool graph
        
         ::is_full()const { return num_vertices >= max_vertices || num_edges >= max_vertices*(max_vertices-1)/2; //判满，分为顶点满和边满 } template 
         
           int graph
          
           ::get_numvertices()const { return num_vertices; } template 
           
             int graph
            
             ::get_numedges()const { return num_edges; } /////////////////////////////////////////////////////////////////////////////////////////// #define VERTICES_DEFAULT_SIZE graph
             
              ::VERTICES_DEFAULT_SIZE //派生类继承父类，若父类为模板，派生类不可直接调用父类保护成员 #define num_vertices graph
              
               ::num_vertices //以宏来代替每个位置写作用域的做法 #define num_edges graph
               
                ::num_edges #define max_vertices graph
                
                 ::max_vertices //另一种方法派生类内定义自己成员函数，可用using graph
                 
                  ::num_edges，在类外则不可 /////////////////////////////////////////////////////////////////////////////////////////// //图的邻接矩阵表示法 template 
                  
                    class graph_mtx : public graph
                   
                    { public: graph_mtx(int); graph_mtx(int (*)[4], const int); //矩阵构造 ~graph_mtx(); public: bool insert_vertex(const T&); bool insert_edge(const T&, const T&); bool remove_vertex(const T&); bool remove_edge(const T&, const T&); int get_firstneighbor(const T&)const; int get_nextneighbor(const T&, const T&)const; int get_vertex_index(const T&)const; void print_graph()const; private: T* vertices_list; //顶点线性表 int **edge; //内部矩阵 }; template 
                    
                      graph_mtx
                     
                      ::graph_mtx(int sz = VERTICES_DEFAULT_SIZE) { max_vertices = sz > VERTICES_DEFAULT_SIZE  sz : VERTICES_DEFAULT_SIZE; vertices_list = new T[max_vertices]; edge = new int*[max_vertices]; //动态申请二维数组 for(int i=0; i
                      
                        graph_mtx
                       
                        ::graph_mtx(int (*mt)[4], const int arr_size) { int edge_count = 0; max_vertices = arr_size > VERTICES_DEFAULT_SIZE  arr_size : VERTICES_DEFAULT_SIZE; vertices_list = new T[max_vertices]; edge = new int*[max_vertices]; for(int i=0; i
                        
                          graph_mtx
                         
                          ::~graph_mtx() { for(int i=0; i
                          
                            bool graph_mtx
                           
                            ::insert_vertex(const T& vert) { if(this->is_full()) //派生类函数调用父类函数，用this或加作用域 return false; vertices_list[num_vertices++] = vert; return true; } template 
                            
                              bool graph_mtx
                             
                              ::insert_edge(const T& vert1, const T& vert2) { if(this->is_full()) //判满 return false; int index_v1 = get_vertex_index(vert1); //得到顶点序号 int index_v2 = get_vertex_index(vert2); if(index_v1 == -1 || index_v2 == -1 ) return false; edge[index_v1][index_v2] = edge[index_v2][index_v1] = 1; //无向图 ++num_edges; return true; } template 
                              
                                bool graph_mtx
                               
                                ::remove_vertex(const T& vert) //用最后一个节点直接覆盖删除的节点，转化为删