数据结构之---C语言实现拓扑排序AOV图

//有向图的拓扑排序
//杨鑫
#include 
#include 
#include 
#define max_name 3
#define max_vertex_num 20
typedef int infotype;					//存放网的权值
typedef char vertextype[max_name];		//字符串类型
typedef enum{dg, dn, ag, an}graphkind;	//{有向图，有向网，无向图，无向网}
//图的邻接表存储
typedef struct arcnode
{
	int adjvex;							//该弧所指向的顶点的位置	
	struct arcnode *nextarc;			//指向吓一条的指针
	infotype *info;						//网的权值指针
}arcnode;

typedef struct vnode
{
	vertextype data;					//顶点信息
	arcnode *firstarc;					//第一个表结点的地址，指向第一条依附该顶点的弧的指针
}vnode, adjlist[max_vertex_num];		//头结点

typedef struct
{
		adjlist vertices;	
		int vexnum, arcnum;				//图的当前顶点数和弧数
		int kind;						//图的种类标志
}algraph;

//若g中存在顶点u，则返回该顶点在图中的位置，都则返回-1
int locatevex(algraph g, vertextype u)
{
	int i;
	for(i = 0; i < g.vexnum; ++i)
	{
		if(strcmp(u, g.vertices[i].data) == 0)
				return i;
		return -1;
	}
}

//采用邻接表存储结构，构造没有相关信息的图g(用一个函数构造4种图)
int creategraph(algraph *g)
{
	int i, j, k;
	int w;							//权值
	vertextype va, vb;
	arcnode *p;
	printf(请输入图的类型（有向图：0，有向网：1，无向图：2，无向网：3）:);
	scanf(%d, &(*g).kind);
	printf(请输入图的顶点数和边数:(以空格间隔)： 
);
	scanf(%d%d, &(*g).vexnum, &(*g).arcnum);
	printf(请输入%d个顶点的值(小于%d个字符):
, (*g).vexnum, max_name);
	for(i = 0; i < (*g).vexnum; ++i)                //构造顶点向量
	{
		scanf(%s, (*g).vertices[i].data);
		(*g).vertices[i].firstarc = null;
	}
	if((*g).kind == 1 || (*g).kind == 3)		//网
	{
		printf(请顺序输入每条弧（边）的权值,弧尾和弧头（以空格作为间隔）:
);
	}
	else											//图
	{
		printf(请顺序输入每条弧（边）的弧尾和弧头（以空格作为间隔）:
);
	}
	for(k = 0; k < (*g).arcnum; ++k)
	{
		if((*g).kind == 1 || (*g).kind == 3)
				scanf(%d%s%s, &w, va, vb);
		else
				scanf(%s%s, va, vb);
		i = locatevex(*g, va);					//弧尾
		j = locatevex(*g, vb);					//弧头
		p = (arcnode*)malloc(sizeof(arcnode));
		p->adjvex = j;
		if((*g).kind == 1 || (*g).kind == 3)
		{
			p->info = (int *)malloc(sizeof(int));
			*(p->info) = w;
		}
		else
		{
			p->info = null;
		}
		p->nextarc = (*g).vertices[i].firstarc;                 //插在表头
		(*g).vertices[i].firstarc = p;
		if((*g).kind >= 2)										//无向图或网，产生第二个表结点
		{
			p = (arcnode*)malloc(sizeof(arcnode));
			p->adjvex = i;
			if((*g).kind == 3)
			{
				p->info = (int*)malloc(sizeof(int));
				*(p->info) = w;
			}
			else
			{
				p->info = null;
			}
			p->nextarc = (*g).vertices[j].firstarc;               //插在表头
			(*g).vertices[j].firstarc = p;     
		}
	}
	return 1;
}

//输出图的邻接表g
void display(algraph g)
{
	int i;
	arcnode *p;
	switch(g.kind)
	{
		case dg:
				printf(有向图
);
				break;
		case dn:
				printf(有向网
);
				break;
		case ag:
				printf(无向图
);
				break;
		case an:
				printf(无向网
);
	}
	printf(%d 个顶点: 
, g.vexnum);
	for(i = 0; i < g.vexnum; ++i)
	{
		printf(%s , g.vertices[i].data);
	}
	printf(
%d条弧（边）:
, g.arcnum);
	for(i = 0; i < g.vexnum; i++)
	{
		p = g.vertices[i].firstarc;
		while(p)
		{
			if(g.kind <= 1)
			{
				printf(%s->%s, g.vertices[i].data, g.vertices[p->adjvex].data);
				if(g.kind == dn)
						printf(:%d , *(p->info));
			}
			else
			{
				if(i < p->adjvex)
				{
					printf(%s--%s, g.vertices[i].data, g.vertices[p->adjvex].data);
					if(g.kind == an)
						printf(:%d , *(p->info));
				}
			}
			p = p->nextarc;

		}
		printf(
);
	}
}


//求顶点的入度
void findindegree(algraph g, int indegree[])
{
	int i;
	arcnode *p;
	//赋初值
	for(i = 0; i < g.vexnum; i++)
	{
		indegree[i] = 0;
	}
	for(i = 0; i < g.vexnum; i++)
	{
		p = g.vertices[i].firstarc;
		while(p)
		{
			indegree[p->adjvex]++;
			p = p->nextarc;
		}
	
	}

}

//栈类型
typedef int selemtype;
#define stack_init_size 10										//存储空间初始分配量
#define stackincrement 2										//存储空间分配增量

//栈的顺序存储结构表示
typedef struct sqstack
{
	selemtype *base;						//基地址
	selemtype *top;							//栈顶指针
	int stacksize;							//当前已经分配的存储空间
}sqstack;                                              

//构造一个空栈
int initstack(sqstack *s)
{
	//为栈底分分配一个指定大小的存储空间
	(*s).base = (selemtype *)malloc(stack_init_size*sizeof(selemtype));
	if(!(*s).base)
			exit(0);						
	(*s).top = (*s).base;					//栈底与栈顶指针相同
	(*s).stacksize = stack_init_size;	
	return 1;
}



//若栈s为空栈（栈底指针和栈顶指针相同）, 则返回1，否则返回0
int stackempty(sqstack s)
{
	if(s.top == s.base)
			return 1;
	else
			return 0;
}


//插入元素e为新的栈顶元素
int 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)
				exit(0);
		(*s).top = (*s).base + (*s).stacksize;
	   	(*s).stacksize += stackincrement;	
	}
	*((*s).top)++= e;
	return 1;
}




//若栈不为空，则删除s栈顶元素用e返回其值，并返回1，否则返回0
int pop(sqstack *s, selemtype *e)
{
	if((*s).top == (*s).base)
	{
		return 0;
	}
	*e = *--(*s).top;
	return 1;
}


//有向图的g采用邻接表存储结构，若g无回路，则输出g的顶点的一个拓扑结构
int topologicalsort(algraph g)
{
	int i, k, count, indegree[max_vertex_num];
	sqstack s;
	arcnode *p;
	findindegree(g, indegree);
	initstack(&s);
	for(i = 0; i < g.vexnum; ++i)
	{
		if(!indegree[i])
				push(&s, i);
		count = 0;
		//栈不空
		while(!stackempty(s))
		{
			pop(&s, &i);
			printf(%s, g.vertices[i].data);			//输出i号顶点并计数
			++count;
			//对i号顶点的每个邻接点的入度减1
			for(p == g.vertices[i].firstarc; p; p = p->nextarc)
			{
				k = p->adjvex;
				if(!(--indegree[k]))			//若入度减为0，则入栈
						push(&s, k);
			}
		}
		if(count < g.vexnum)
		{
				printf(此有向图有回路
);
				return 0;
		}
		else
		{
			printf(为一个拓扑序列!!
);
		}
	}
}

int main()
{
	algraph f;
	printf(请选择有向图
);
	creategraph(&f);
	display(f);
	topologicalsort(f);
	return 0;
}

结果：