欢迎您访问程序员文章站本站旨在为大家提供分享程序员计算机编程知识!
您现在的位置是: 首页  >  IT编程

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

程序员文章站 2023-10-11 19:20:33
//有向图的拓扑排序 //杨鑫 #include #include #include #define max_name 3 #define max_vertex_num 20...
//有向图的拓扑排序
//杨鑫
#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;
}













结果:

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