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>
bool ALGraph<T>::TopoSort(vector<T> & topo)
{ topo.clear();
	vector<int> indegree(m_N,0);
  // 统计入度表
  for(int i=0; i<m_N; i++)
    for(ArcNode *p=m_Data[i].firstarc; p; p=p->nextarc)
       indegree[p->adjvex]++;
  stack<int> S;
  for(i=0; i<m_N; i++)     // 入度为0者进栈
    if(indegree[i]==0) S.push(i); 
  while( !S.empty() )
  { int out=S.top(); S.pop();  // out为出栈元素
    topo.push_back( m_Data[out].data );
    for(ArcNode *p=m_Data[out].firstarc; p; p=p->nextarc)
    { int k=p->adjvex;  indegree[k]--; 
      if(indegree[k]==0) S.push(k);
    }  
  }
  if(topo.size()<m_N) return false;
       else           return true; 
}

#endif