algraph.cpp

树的操作中的邻接表。。解压即可。。直接上交

#ifndef ALGraph_CPP
#define ALGraph_CPP
#include  "ALGraph.h"

template<class T>
ALGraph<T>::ALGraph(vector<T> vs)
{ m_N = vs.size();
  m_Data.resize(m_N);
  for(int i=0; i<m_N; i++) 
  { m_Data[i].data=vs[i];
    m_Data[i].firstarc=NULL;
  }
}

template<class T>
ALGraph<T>::~ALGraph()
{ for(int i=0; i<m_N; i++) 
    Clear(m_Data[i].firstarc);
}  

template<class T>
void ALGraph<T>::Clear(ArcNode *head)
{ while(head)
  { ArcNode *p=head->nextarc;
    delete head; head=p;
  }
}

template<class T>
void ALGraph<T>::Append(vector<Edge> &es)
{ for(int i=0; i<es.size(); i++) 
  { int v1=es[i].v1, v2=es[i].v2;
    ArcNode *p=new ArcNode;
    p->adjvex=v2;  p->weight=es[i].weight;
    p->nextarc=m_Data[v1].firstarc;
    m_Data[v1].firstarc = p;
  }
}

template<class T>
void ALGraph<T>::Output()
{ for(int i=0; i<m_N; i++)
  { cout<<m_Data[i].data<<": ";
    for(ArcNode *p=m_Data[i].firstarc; p; p=p->nextarc)
      cout<<i<<","<<p->adjvex<<":"<<p->weight<<"\t"; 
    cout<<endl;
  }
  cout<<endl;
} 


template<class T>
int ALGraph<T>::OutDegree(int k)
{ int n=0;
  for(ArcNode *p=m_Data[k].firstarc; p; p=p->nextarc)
    n++;
  return n;
}

template<class T>
int ALGraph<T>::InDegree(int k)
{ int n=0;
  for(int i=0; i<m_N; i++)
    for(ArcNode *p=m_Data[i].firstarc; p; p=p->nextarc)
      if(p->adjvex==k) n++;
  return n;
}

template<class T>
vector<T> ALGraph<T>::DFSTraverse()
{ vector<T> vs,vs1;  
  // 实现步骤①
  vector<bool> visited(m_N,false); 
  // 实现步骤④
  for(int v=0; v<m_N; v++)                   
    if(visited[v]==false)       
    { vs1.clear();
      DoDFSTraverse(v,visited,vs1);
      vs.insert(vs.end(),vs1.begin(),vs1.end());
    }
  return vs;
}



template<class T>
void ALGraph<T>::DoDFSTraverse(int v,vector<bool>& visited,vector<T>& vs)
{ // 实现步骤②
  vs.push_back(m_Data[v].data);  visited[v]=true; 
  // 实现步骤③
  for(ArcNode *p=m_Data[v].firstarc; p; p=p->nextarc)
   { int w=p->adjvex;
     if(visited[w]==false)
       DoDFSTraverse(w,visited,vs);
   }
}

template<class T>
vector<T> ALGraph<T>::BFSTraverse()
{ vector<T> vs,vs1;  
  // 实现步骤①
  vector<bool> visited(m_N,false); 
  // 实现步骤④
  for(int v=0; v<m_N; v++)                   
    if(visited[v]==false)       
    { vs1.clear();
      DoBFSTraverse(v,visited,vs1);
      vs.insert(vs.end(),vs1.begin(),vs1.end());
    }
  return vs;
}


template<class T>
void ALGraph<T>::DoBFSTraverse(int v,vector<bool>& visited,vector<T>& vs)
{ queue<int> Q; ArcNode *p;
  Q.push(v);  visited[v]=true;    // 步骤②
  while(!Q.empty())               // 步骤⑤
  { v=Q.front(); Q.pop();  
    vs.push_back(m_Data[v].data); // 步骤③ 
    for(ArcNode *p=m_Data[v].firstarc; p; p=p->nextarc)  
    { int w=p->adjvex;
      if(visited[w]==false) 
      { Q.push(w);
        visited[w]=true;
      }
    }
  }
}

#endif