aov.cpp

c++下的AOV实现

#include<iostream.h>
template<class DistType> struct Edge{
	int dest;
	DistType cost;
	Edge<DistType> *link;
	Edge(){}
	Edge(int d,DistType c):dest(d),cost(c),link(NULL){}
};
template<class NameType,class DistType> struct Vertex{
	NameType data;
	Edge<DistType> *adj;
	Vertex():adj(NULL){}
};
class Graph{
private:
	Vertex<int,float> *NodeTable;
	int *count,*sort,n,e;
public:
	Graph(){
		int i,j,k;
		float weight;
		char c1,c2;
		cout<<"INPUT VERTEX:";
		cin>>n;
		NodeTable=new Vertex<int,float>[n];
		count=new int[n];
		for(i=0;i<n;i++)count[i]=0;
		sort=new int[n];
		cout<<"END WITH SIDES:";
		cin>>e;
		cout<<"INPUT SIDS ONE BY ONE:"<<endl;
		for(i=0;i<e;i++)
		{
			cin>>j>>c1>>k>>c2>>weight;
			Edge<float> *p=new Edge<float>(k,weight);
			p->link=NodeTable[j].adj;NodeTable[j].adj=p;
			count[k]++;
		}
	}
	void TopologicalSort(){
		int top=-1;
		cout<<"拓扑排序:";
		for(int i=0;i<n;i++)
			if(count[i]==0){count[i]=top;top=i;}
			for(i=0;i<n;i++)
				if(top==-1){cout<<"NetWork has a cycle"<<endl;return;}
				else{
					int j=top;top=count[top];
					cout<<j<<" ";
					sort[i]=j;
					Edge<float> *l=NodeTable[j].adj;
					while(l){
						int k=l->dest;
						if(--count[k]==0){count[k]=top;top=k;}
						l=l->link;
					}
				}
				cout<<endl;
	}
	void CriticalPath(){		
		cout<<"KEY ACTIVITY:";
		int i,k;float e,l;
		float* Ve=new float[n];float* Vl=new float[n];
		for(i=0;i<n;i++)Ve[sort[i]]=0;
		for(i=0;i<n;i++){
			Edge<float> *p=NodeTable[sort[i]].adj;
			while(p!=NULL){
				k=p->dest;
				if(Ve[sort[i]]+p->cost>Ve[k])Ve[k]=Ve[sort[i]]+p->cost;
				p=p->link;
			}
		}
		for(i=0;i<n;i++)Vl[sort[i]]=Ve[sort[n-1]];
		for(i=n-2;i;i--){
			Edge<float> *p=NodeTable[sort[i]].adj;
			while(p!=NULL){
				k=p->dest;
				if(Vl[k]-p->cost<Vl[sort[i]])Vl[sort[i]]=Vl[k]-p->cost;
				p=p->link;
			}
		}
		for(i=0;i<n;i++){
			Edge<float> *p=NodeTable[sort[i]].adj;
			while(p!=NULL){
				k=p->dest;
				e=Ve[sort[i]];l=Vl[k]-p->cost;
				if(l==e)
					cout<<"("<<sort[i]<<","<<k<<")";
				p=p->link;
			}
		}
		cout<<endl;
	}
};
	void main(){
	Graph a;
	a.TopologicalSort();
	a.CriticalPath();
}