mgraph.h

拓扑排序问题

#include "stdio.h"
#include "stdlib.h"

#define MAX_VERTEX_NUM 30			//图的最大节点数
#define STACK_INIT_SIZE 100
#define STACKINCREMENT 10
#define OVERFLOW -1


typedef char VERTEXTYPE;	//定义图的节点类型
typedef int ELEMTYPE;		//定义栈的节点类型


typedef struct ArcCell	// 弧的定义
{ 
	int adj;			// 对无权图，用1或0表示相邻否；对带权图，则为权值类型。
    //InfoType *info;		// 该弧相关信息的指针
} ArcCell, AdjMatrix[MAX_VERTEX_NUM][MAX_VERTEX_NUM];

typedef struct // 图的定义
{  
	VERTEXTYPE  vexs[MAX_VERTEX_NUM];       // 顶点信息
    AdjMatrix  arcs;		// 弧的信息                     
    int  vexnum, arcnum;	// 顶点数，弧数             
} MGraph;

int LocateVex(MGraph G, VERTEXTYPE v)
{
	int locate=0;
	while( G.vexs[locate]!=v && locate<G.vexnum )locate++;
	if(locate==G.vexnum)
	{
		printf("该节点不存在！\n");
		return(locate);
	}
	else return(locate);
}

void CreateDG(MGraph &G)      //建有向图的邻接矩阵表示
{
	int i,j,k;
	VERTEXTYPE v1,v2;
	printf("请输入图中节点和弧的个数，中间以逗号间隔：\n");
	scanf("%d,%d",&G.vexnum,&G.arcnum);
	getchar();	//用来接收回车符
	printf("请输入节点向量，中间不需要间隔：\n");
	for( i=0; i<G.vexnum; i++ ) G.vexs[i]=getchar();	//构造顶点向量
	getchar();	//用来接收回车符
	for( i=0; i<G.vexnum; i++ )
       for( j=0; j<G.vexnum; j++ ) G.arcs[i][j].adj=0;	//初始化邻接矩阵
	printf("请输入每条边依附的顶点，两顶点之间用逗号间隔：\n");
	for( k=0; k<G.arcnum; k++ )
    { 
		scanf("%c,%c",&v1,&v2);		//输入一条边依附的顶点
		getchar();	//用来接收回车符
		i=LocateVex(G,v1);
		j=LocateVex(G,v2);
        G.arcs[i][j].adj=1;			//修改邻接矩阵
	}
}//   时间复杂度为O(n2)

bool visited[MAX_VERTEX_NUM];

void visit(VERTEXTYPE e)
{
	printf("%c",e);
}

////////////////////////////////////////////////////////下面是关于栈的定义
typedef struct
{
	ELEMTYPE *base,*top;
	int stacksize;
}stack;

void initstack(stack &s)
{
	s.base = (ELEMTYPE *)malloc(STACK_INIT_SIZE * sizeof(ELEMTYPE));
	if(!s.base)exit(OVERFLOW);
	s.top = s.base;
	s.stacksize = STACK_INIT_SIZE;
}//构造一个空栈

void push(stack &s,ELEMTYPE e)
{
	if(s.top-s.base>=s.stacksize)
	{
		s.base=(ELEMTYPE*)realloc(s.base,(s.stacksize +STACKINCREMENT)*sizeof(ELEMTYPE));
		if(!s.base)exit(OVERFLOW);
		s.top=s.base +s.stacksize;
		s.stacksize +=STACKINCREMENT;
	}
	*s.top ++=e;
}//插入元素e为新的栈顶元素

ELEMTYPE pop(stack &s)
{
	ELEMTYPE e;
	if(s.top==s.base)
		printf("栈已空!\n");
	e= * --s.top;
	return(e);
}//若栈不空，则删除s的栈顶元素，利用e返回其值

int stackempty(stack s)
{	
	if(s.top==s.base)
		return 1;
	else 
		return 0;
}//验证栈是否为空
//////////////////////////////////////////////////栈的定义结束

void TopologicalSort(MGraph G)
{
	stack s;
	initstack(s);
	int count=0;	//用于计数
	for( int i=0; i<G.vexnum; i++ )	
	{
		G.arcs[G.vexnum][i].adj=0;
		for( int j=0; j<G.vexnum; j++ )		
			G.arcs[G.vexnum][i].adj+=G.arcs[j][i].adj;
		if( G.arcs[G.vexnum][i].adj==0) push(s,i);
	}	
	while( !stackempty(s) )
	{
		i=pop(s);
		printf("%C",G.vexs[i]);
		count++;
		for( int j=0; j<G.vexnum; j++ )
			if( G.arcs[i][j].adj==1 )
			{
				G.arcs[G.vexnum][j].adj--;
				if( G.arcs[G.vexnum][j].adj==0 ) push(s,j);
			}
	} //while
	if( count<G.vexnum ) printf("原图中存在环！\n");
} //TopologicalSort