king.cpp

拓扑排序源码下载

#include <stdio.h>
#include <stdlib.h>
#define NULL 0
#define MAXVEX 100
#define STACK_INIT_SIZE 10
#define STACKINCREMENT 2
 
typedef int SElemType;
typedef struct SqStack
 {
   SElemType *base; 
   SElemType *top; 
   int stacksize; 
 }SqStack; 

typedef struct ArcNode{
	int adjvex;
	int info;
	struct ArcNode *nextarc;
}ArcNode;

typedef struct vexnode{
	int  data;
	struct ArcNode *firstarc;
}vexnode;

typedef struct vexnode AdjList [MAXVEX];

int n;

InitStack(SqStack &S)
 { 
   S.base=(SElemType *)malloc(STACK_INIT_SIZE*sizeof(SElemType));
   if(!S.base)
     return 0; 
   S.top=S.base;
   S.stacksize=STACK_INIT_SIZE;
   return 1;
 }

StackEmpty(SqStack &S)
{ 
   if(S.top==S.base)
     return 1;
   else
     return 0;
}

Push(SqStack &S,SElemType e)
 { 
   if(S.top-S.base>=S.stacksize)
   {
     S.base=(SElemType *)realloc(S.base,(S.stacksize+STACKINCREMENT)*sizeof(SElemType));
     if(!S.base)
       return 0; 
     S.top=S.base+S.stacksize;
     S.stacksize+=STACKINCREMENT;
   }
   *S.top++=e;
   return 1;
 }

 Pop(SqStack &S,SElemType &e)
 { 
   if(S.top==S.base)
     return 0;
   e=*--S.top;
   return 1;
 }
void creatbgraph(AdjList *g)
{
	int e,i,s,d;
	ArcNode *p;
	printf("请输入结点数(n)和边数(e):");
	scanf("%d,%d",&n,&e);
	for(i=0;i<n;i++)
	{
		g[i]->data=i;
		g[i]->firstarc=NULL;
	}
	for(i=0;i<e;i++)
	{	
		printf("\n输入第%d条边的起点序号,终点序号:",i+1);
		scanf("%d,%d",&s,&d);
		p=( ArcNode *)malloc(sizeof( ArcNode));
		p->adjvex=d;
		p->info=s;
		p->nextarc=g[s]->firstarc;
		g[s]->firstarc=p;
	}
}

void dispbgraph(AdjList *g)
{
	int i;
	ArcNode	*p;
	printf("图的连接表表示如下:\n");
	for(i=0;i<n;i++)
	{	
		printf("%d[V%d]->",i,g[i]->data+1);
		p=g[i]->firstarc;
		while(p!=NULL)
		{
			printf("(V%d,%d)->",p->info+1,p->adjvex);
			p=p->nextarc;
		}
		printf("^\n");
	}


}

void Findindegree(AdjList *g,int indegree[MAXVEX])
{
	int i;
	ArcNode	*p;
	for(i=0;i<n;i++)
     	indegree[i]=0; 
	for(i=0;i<n;i++)
	{
		p=g[i]->firstarc;
		while(p!=NULL)
		{
			indegree[p->adjvex]++;
		}
	}
}

TopologicalSort(AdjList *g)
 { 
   int i,k,count,indegree[MAXVEX];
   SqStack S;
   ArcNode *p;
   Findindegree(g,indegree); 
   InitStack(S); 
   for(i=0;i<n;++i) 
     if(!indegree[i])
       Push(S,i); 
   count=0; 
  printf("结果为:");
   while(!StackEmpty(S))
   { 
     Pop(S,i);
	 ++count;
	 if(count<n)
     printf("V%d->",g[i]->data+1); 
	 else printf("V%d",g[i]->data+1);
     for(p=g[i]->firstarc;p;p=p->nextarc)
     { 
       k=p->adjvex;
       if(!(--indegree[k])) 
         Push(S,k);
     }
   }
   if(count<n)
   {
     printf("\n此为有向图有回路");
     return 0;
   }
   else
   {
     printf("\n为一个拓扑序列。");
     return 1;
   }
}

void main()
{
	AdjList m[MAXVEX];
	creatbgraph(m);
	dispbgraph(m);
	TopologicalSort(m);
}