graph.h

求图的强连通分支

#ifndef GRAPH_H
#define GRAPH_H
#include"SqStack.h"
#include"sort.h"
#include<iostream.h>
#include<stdlib.h>
#include<fstream.h>
template<class VertexType,class EdgeType>class Graph;
template<class VertexType,class EdgeType>class Vertex;
template<class VertexType,class EdgeType>class Edge{
friend class Graph<VertexType,EdgeType>;
public:
	Edge(Vertex<VertexType,EdgeType>*d,EdgeType c,Edge<VertexType,EdgeType> *q):
	dest(d),cost(c),link(q){};
private:
	Vertex<VertexType,EdgeType> * dest;
	EdgeType cost;
	Edge<VertexType,EdgeType> *link;
};

template<class VertexType,class EdgeType>class Vertex{
friend class Edge<VertexType,EdgeType>;
friend class Graph<VertexType,EdgeType>;
public:
	Vertex(VertexType d,Vertex<VertexType,EdgeType>*p, Edge<VertexType,EdgeType>*q):
	  data(d),next(p),adj(q),ve(0),vl(0){}
private:
	int tag;
	VertexType data;
	EdgeType ve;
	EdgeType vl;
	Vertex<VertexType,EdgeType> *next;
	Edge<VertexType,EdgeType>* adj;
	int DFS_Number;
	int Component;
   int High;
};

template<class VertexType,class EdgeType>
class Graph{
private:
	Vertex<VertexType,EdgeType> *head;
	int NumVertex;
	int NumStrong;
	int NumEdge;
	const VertexType Vertex_finish_flag;
	const EdgeType Edge_finish_flag;
public:
	Graph(VertexType flag,EdgeType tag);
	~Graph();
	int GraphEmpty()const {return NumVertex==0;}
	void DFS_Traveling(const VertexType & start);
	int NumofVertex()const{return NumVertex;}
	VertexType Getvalue(Vertex<VertexType,EdgeType>*p)
	{return p?p->data:0;}
	void InsertVertex(const VertexType &vertex);
	void InsertEdge(Vertex<VertexType,EdgeType> *v1,Vertex<VertexType,EdgeType> *v2,EdgeType weight);
	void RemoveVertex(const VertexType & vertex);
	void RemoveEdge(Vertex<VertexType,EdgeType> *v1,Vertex<VertexType,EdgeType> *v2);
	EdgeType GetWeight(Vertex<VertexType,EdgeType> *v1,Vertex<VertexType,EdgeType>*v2);
	Vertex<VertexType,EdgeType> *GetFirstNeighbor(const Vertex<VertexType,EdgeType> *v);
	Vertex<VertexType,EdgeType> *GetNextNeighbor(Vertex<VertexType,EdgeType>*v1,Vertex<VertexType,EdgeType>*v2);
	Vertex<VertexType,EdgeType>* GetVertexPos(const VertexType & vertex);
	void CreateGraph(VertexType a[],int n);
	void InsertEdge(VertexType u,VertexType v);
	void StronglyConnectedComponents();
	//v为图的一个节点，作为DFS树的根，n为图G 的节点数
	void SCC(Vertex<VertexType,EdgeType>* p,int *DFS_N,int *Current_Component,Stack<Vertex<VertexType,EdgeType>*> *s);
	void OutputComponent();
};

template<class VertexType,class EdgeType>
void Graph<VertexType,EdgeType>::OutputComponent(){
	char outFileName[]="result4.txt";
	ofstream outFile;
	outFile.open(outFileName);
	if(!outFile.is_open()){
	cout<<"File open error!"<<endl;
	cout<<"opration is ter!"<<endl;
	exit(EXIT_FAILURE);
	}
	 Vertex<VertexType,EdgeType> *p;
	 for(p=head;p!=NULL;p=p->next)
		cout<<p->data<<" :   "<<p->Component<<endl;
     int * Array=new int[NumStrong+1];
	 int *Array1=new int[NumStrong+1];
	 for(int i=1;i<NumStrong+1;i++){
	 Array[i]=0;
	 }
	 bool m_bPrint=false;
	 for(p=head;p!=NULL;p=p->next)
	 Array[p->Component]++;
for(i=1;i<NumStrong+1;i++)
Array1[i]=Array[i];
int temp;
	 MergeSort(Array1,NumStrong);
	 outFile<<NumStrong<<endl;
	 for(i=1;i<=NumStrong ;i++){
		 if(Array1[i]==Array1[i-1])continue;
		 for(int j=1;j<NumStrong+1;j++){
			 if(Array[j]==Array1[i]){
		 for(p=head;p!=NULL;p=p->next){
			 if(p->Component==j){
				 outFile<<p->data<<"   ";
		 m_bPrint=true;}}	
		 if(m_bPrint)outFile<<endl;
		 m_bPrint=false;}}
	}
	
}

template<class VertexType,class EdgeType>
void Graph<VertexType,EdgeType>::SCC(Vertex<VertexType,EdgeType>* p,int* DFS_N,
									 int *Current_Component,Stack<Vertex<VertexType,EdgeType>*> *s){
p->DFS_Number=(*DFS_N);
(*DFS_N)--;
s->Push(p);
p->High=p->DFS_Number;
Vertex<VertexType,EdgeType> *w;
Edge<VertexType,EdgeType> *q1;
for(q1=p->adj;;q1=q1->link){
	if(q1->dest->DFS_Number==0){
		SCC(q1->dest,DFS_N,Current_Component,s);
		p->High=p->High>=q1->dest->High?p->High:q1->dest->High;
	}
	else{
	if(q1->dest->DFS_Number>p->DFS_Number && q1->dest->Component==0)
		p->High=p->High>q1->dest->DFS_Number?p->High:q1->dest->DFS_Number;}
		if(q1->link==NULL)break;}
	if(p->High==p->DFS_Number)
	{(*Current_Component)++;
	  NumStrong++;
	do{w=s->Top();
	s->Pop();
	w->Component=(*Current_Component);}while(w!=p);}


}

template<class VertexType,class EdgeType>
void Graph<VertexType,EdgeType>::StronglyConnectedComponents(){
     Vertex<VertexType ,EdgeType> *p;
Stack<Vertex<VertexType,EdgeType>*> s(NumVertex);
	 for(p=head;;p=p->next){
	 p->DFS_Number=0;
	 p->Component=0;
	 if(p->next==NULL)break;
	 }
	 int Current_Component=0;
int	 DFS_N=NumVertex;
	 for(p=head;p->next!=NULL;p=p->next){
	 if(p->DFS_Number==0)
		 SCC(p,&DFS_N,&Current_Component,&s);
	 }

}

template<class VertexType,class EdgeType>
void Graph<VertexType,EdgeType>::InsertEdge(VertexType v ,VertexType u){
Vertex<VertexType,EdgeType> *p,*q;
Exception(!(p=GetVertexPos(v)),"It is NULL!");
Exception(!(q=GetVertexPos(u)),"It is NULL!");
p->adj=new Edge<VertexType,EdgeType>(q,1,p->adj);
Exception(!p->adj,"Fail on memory!");
NumEdge++;
}

template<class VertexType ,class EdgeType>//创建顶点
void Graph<VertexType,EdgeType>::CreateGraph(VertexType a[],int n){
head=NULL;
for(int i=0;i<n;i++){
	head=new Vertex<VertexType,EdgeType> (a[i],head,NULL);
Exception(!head,"Head is NULL");
NumVertex++;
}
}


template<class VertexType,class EdgeType>
Graph<VertexType,EdgeType>::Graph(VertexType flag,EdgeType tag):Vertex_finish_flag(flag),Edge_finish_flag(tag){
	NumVertex=0;
	NumEdge=0;
	NumStrong=0;
}

template<class VertexType,class EdgeType>
Graph<VertexType,EdgeType>::~Graph(){
Vertex<VertexType,EdgeType> *p,*m;
Edge<VertexType,EdgeType> *q;
p=head;
while(p){
	while(q=p->adj){p->adj=q->link;delete q;}
	m=p;p=p->next;delete m;
}
}

template<class VertexType,class EdgeType>
Vertex<VertexType,EdgeType> *Graph<VertexType,EdgeType>::GetVertexPos(const VertexType & vertex){
Vertex<VertexType,EdgeType>* p;
p=head;
while(p){if(p->data==vertex)return p;p=p->next;}
return NULL;
}

template<class VertexType,class EdgeType>
Vertex<VertexType,EdgeType>* Graph<VertexType,EdgeType>::GetFirstNeighbor(const Vertex<VertexType,EdgeType>*v){
Edge<VertexType,EdgeType> *p;
if(v1 && v2){p=v1->adj;if(!p)return NULL;}else return NULL;
while(p){if(p->dest==v2 && p->link!= NULL)return p->link->dest;p=p->link;}
return NULL;
}

template<class VertexType,class EdgeType>
EdgeType Graph<VertexType,EdgeType>::GetWeight(Vertex<VertexType,EdgeType>*v1,Vertex<VertexType,EdgeType> *v2){
Edge<VertexType,EdgeType> *p;
if(v1 && v2){p=v1->adj;if(!p)return 0;}else return 0;
while(p){if(p->data==v2)return p->cost;p=p->link;}
return 0;
}


template<class VertexType,class EdgeType>
void Graph<VertexType,EdgeType>::DFS_Traveling(const VertexType& start){
Stack<Edge<VertexType,EdgeType>*>s (NumEdge);
Vertex<VertexType,EdgeType> *p,*m;
Edge<VertexType,EdgeType>* q;
p=head;
while(p){p->tag=0;p=p->next;}
p=GetVertexPos(start);
if(!p){cout<<"Start vertex is error"<<endl;return;}
int finished=0;
while(p){
	if(p->tag==0){
	p->tag=1;
	cout<<"visit vertex data"<<p->data<<endl;
	if(p->adj)s.Push(p->adj);
	while(!s.IsEmpty()){
	q=s.Top();s.Pop();
	if(q->link) s.Push(q->link);
	m=q->dest;
	if(m->tag==0){m->tag=1;
	cout<<"visited vertex data:"<<m->data<<endl;
	if(m->adj)s.Push(m->adj);}
	}
	}
	p=p->next;if(!p&& !finished){p=head;finished=1;}
}return;
}
#endif