graph.h

数据结构算法

class Edge{
public:
	Edge(){next=NULL;}
	Edge(int V2,int W){v2=V2; weight=W; next=NULL;}
	~Edge(){}

	bool mark;
	int v2;
	int weight;
	Edge* next;    
};

struct ListNode{
	char Name;
	int degree;
	Edge* FirstE;
};

class Graph{
public:
    friend class AOE;

	Graph(){list=NULL;}
	Graph(int Vertrixs){ NumVert=Vertrixs;
	                     NumEdge=0;
	                     list=new ListNode[Vertrixs];
						 for(int i=0;i<Vertrixs;i++){
		                 list[i].degree=0;
						 list[i].FirstE=NULL;
                         }

	}

	dlink<int> topsort();
	bool isEdge(int v1,int v2);
    int NumV(){return NumVert;}
	int NumE(){return NumEdge;}
	int Weight(int v1,int v2){return 1;}

	bool InsertEdge(int v1,int v2,int w);
    
	void BFS(){}
    void DFS(){}

private:
	ListNode* list;
	int NumVert;
	int NumEdge;
};
	


bool Graph::InsertEdge(int v1,int v2,int w){               //can't insert the same balance;
	Edge* data=new Edge(v2,w);
	Edge* temp=list[v1].FirstE;
	
	if(temp!=NULL){
      if(v2<temp->v2){ 
		 list[v1].FirstE=data;
		 
	  }
	}
	else{
		list[v1].FirstE=data;
        data->next=temp;
        list[v1].degree+=1;
	    NumEdge+=1;
   	    return true;
	}

	while(temp!=NULL){
		if(temp->next==NULL){
			if(temp->v2<v2){
			   temp->next=data;
			   list[v1].degree+=1; 
			   NumEdge+=1;
			   return true;
			}
            else 		 
               return false;
		}
		else if(temp->v2<v2 && temp->next->v2>v2){
			   Edge* curr=temp->next;
			   temp->next=data;
			   data->next=curr;
			   list[v1].degree+=1;
			   NumEdge+=1;
			   return true;
		      }
		temp=temp->next;
	}
	return true;
}


dlink<int> Graph::topsort(){
	int i=0,j=0,n=0;
	int* DegArr=new int[NumVert];
	bool* ENed=new bool[NumVert];
    for(i=0;i<NumVert;i++){
		DegArr[i]=list[i].degree;
		ENed[i]=false;
	}

	dlink<int> Queue;
	
    while(j<NumVert){
	   i=0;
	  while(i<NumVert){
		 if(DegArr[i]==0 && ENed[i]==false){
			Queue.input(i);
			ENed[i]=true;
			j++;
			
            n=0;
			while(n<NumVert){
				if(isEdge(n,i)==true && ENed[n]==false)
					DegArr[n]--;
			   n++;
			}

		 }
		i++;
	  }
	}

   return Queue;
}




bool Graph::isEdge(int v1,int v2){
  Edge* temp=list[v1].FirstE;
  while(temp!=NULL){
	  if(temp->v2==v2) return true;
	  temp=temp->next;
  }
  return false;
}