括扑排序.cpp

拓扑排序

#include<iostream.h>
#include<malloc.h>
#define max 100
typedef enum{DG,DN,UDG,UDN}graphkind;
typedef struct arcnode{
	int adjvex;
	struct arcnode*nextarc;
}arcnode;
typedef struct vnode{
	int data;
	int ind;
	arcnode* firstarc;
}vnode;
typedef struct{
	vnode adjlist[max];
	int vexnum,arcnum;
	graphkind kind;
}algraph;
void create(algraph *g)
{
	int i,k,j;
	arcnode*s;
	cout<<"输入顶点数:";cin>>g->vexnum;
    cout<<"输入边数:";cin>>g->arcnum;
	g->kind=DG;
	for(i=0;i<g->vexnum;i++)
	{
		g->adjlist[i].data=i;
		g->adjlist[i].firstarc=NULL;
	}
	for(k=0;k<g->arcnum;k++)
	{
		cout<<"输入第"<<k+1<<"条边(节点从0到"<<g->vexnum-1<<"):";
		cin>>i>>j;
		s=(arcnode*)malloc(sizeof(arcnode));
		s->adjvex=j;
		s->nextarc=g->adjlist[i].firstarc;
		g->adjlist[i].firstarc=s;
	}
}
void finddegree(algraph *g)
{
	arcnode*s;
	int count=0,i,j;
	for(j=0;j<g->vexnum;j++)
	{
		for(i=0;i<g->vexnum;i++)
		{
			s=g->adjlist[i].firstarc;
			while(s)
			{
				if(s->adjvex==j)
					count++;
				s=s->nextarc;
			}
			g->adjlist[j].ind=count;
		}
		count=0;
	}
	cout<<"输出各顶点的入度:";
	for(i=0;i<g->vexnum;i++)
		cout<<g->adjlist[i].ind<<" ";
	cout<<endl;
}
void topologicalsort(algraph g)
{
	int stack[max],top,i,count,k;
	arcnode*s;
	top=-1;
	for(i=0;i<g.vexnum;i++)
		if(g.adjlist[i].ind==0) 
			stack[++top]=i;
	count=0;
	if(top>-1)
	{
		cout<<"输出拓扑排序序列:";
	    while(top!=-1)
		{
			i=stack[top--];
		    cout<<g.adjlist[i].data<<" ";
		    count++;
		    s=g.adjlist[i].firstarc;
		    while(s)
			{
				k=s->adjvex;
		        if(!(--g.adjlist[k].ind)) stack[++top]=k;
			    s=s->nextarc;
			}
		}
	}
	cout<<endl;
	if(count<g.vexnum) cout<<"该有向图有回路!"<<endl;
}
void main()
{
	algraph g;
	create(&g);
	finddegree(&g);
	topologicalsort(g);
}