sgraph.cpp

数据结构中的求强连通分量的源程序

# include <iostream.h>
# include <malloc.h>
# include <conio.h>
# include <stdio.h>

# define MAX_VERTEX_NUM 20
# define OK 1
typedef int VertexType;
typedef int InfoType;

typedef struct ArcBox	
{  int tailvex,headvex;
   struct ArcBox *hlink,*tlink;
   InfoType *info;
}ArcBox;

typedef struct VexNode
{  VertexType data;
   ArcBox *firstin,*firstout;
}VexNode;

typedef struct
{  VexNode xlist[MAX_VERTEX_NUM];
   int vexnum,arcnum;
}OLGraph;

int CreateDG(OLGraph &G)	
{  int IncInfo,i,j,k,v1,v2,w;
   cout<<endl<<"Please input the number of G.vexnum (eg,G.vexnum=4): ";
   cin>>G.vexnum;		
   cout<<"Please input the number of G.arcnum (eg,G.arcnum=4): ";
   cin>>G.arcnum;		
   cout<<"Please input IncInfo (0 for none)                  : ";
   cin>>IncInfo;		
   for(i=0;i<G.vexnum;++i)
       {  cout<<"Please input the value of the "<<i+1<<"th vex : ";
	  cin>>G.xlist[i].data;
	  G.xlist[i].firstin=NULL;
	  G.xlist[i].firstout=NULL;
       }
   cout<<"Plese input arc(V1-->V2), For example: (V1=1,V2=3),(V1=2,V2=4)..."<<endl;
   for(k=0;k<G.arcnum;++k)	
   {   cout<<endl<<"Please input the "<<k+1<<"th arc's v1 (0<v1<G.vexnum): ";
       cin>>v1;
       cout<<"Please input the "<<k+1<<"th arc's v2 (0<v2<G.vexnum): ";
       cin>>v2;
       i=v1;
       j=v2;
       while(i<1||i>G.vexnum||j<1||j>G.vexnum)	
       {  cout<<endl<<"Please input the "<<k+1<<"th arc's v1 (0<v1<G.vexnum): ";
	  cin>>v1;
	  cout<<"Please input the "<<k+1<<"th arc's v2 (0<v2<G.vexnum): ";
	  cin>>v2;
	  i=v1;
	  j=v2;
       } 
   ArcBox *p;
   p=(ArcBox *)malloc(sizeof(ArcBox));	
   if(!p)
   {  cout<<"Overflow!";	
      return (0);
   }
   p->tailvex=i;		
   p->headvex=j ;
   p->hlink=G.xlist[j].firstin;
   p->tlink=G.xlist[i].firstout;
   p->info=NULL;
   G.xlist[j].firstin=p;
   if(IncInfo)
      {  cout<<"Please input the info :";
	 cin>>*(p->info);	
      }
   } 
   return (OK);
} 

void Get_SGraph(OLGraph G,ArcBox *p);
void DFS1(OLGraph G,ArcBox *p,int v);
void DFS2(OLGraph G,ArcBox *p,int v);
void main()		
{   
	OLGraph G;
	ArcBox *p;
    cout<<endl<<endl<<"CreateDG.cpp";
    cout<<endl<<"============"<<endl;
    if(CreateDG(G))		
       cout<<endl<<"Create OLGraph success!"; 
    cout<<endl<<endl<<"...OK!...";
    getch();
    Get_SGraph(G,p);  
}

int visited[MAX_VERTEX_NUM];
int finished[MAX_VERTEX_NUM];
int count;              
void Get_SGraph(OLGraph G,ArcBox *p)         
{
	int v,i;
	count=0;
	for(v=0;v<G.vexnum;v++) visited[v]=0;
	for(v=0;v<G.vexnum;v++)              
		if(!visited[v]) DFS1(G,p,v);
		for(v=0;v<G.vexnum;v++) visited[v]=0;                
		for(i=G.vexnum-1;i>=0;i--)             
		{
			v=finished[i];
			if(!visited[v])
			{
				printf("\n");                      
				DFS2(G,p,v);
			}
		}
}
void DFS1(OLGraph G,ArcBox *p,int v)            
{
	int w;
	visited[v]=1;
	for(p=G.xlist[v].firstout;p;p=p->tlink)
	{
		w=p->headvex;
		if(!visited[w]) DFS1(G,p,w);
	}
	finished[++count]=v;                   
}
void DFS2(OLGraph G,ArcBox *p,int v)            
{
	int w;
	visited[v]=1;
	printf("%d",v);                        
	for(p=G.xlist[v].firstin;p;p=p->hlink)
	{
		w=p->tailvex;
		if(!visited[w]) DFS2(G,p,w);
	}                                        
}