手机版 欢迎访问it开发者社区(www.mfbz.cn)网站

当前位置: > 开发

AOV网是否存在回路-拓扑排序-C++

时间:2021/11/30 3:33:21|来源:|点击: 次

拓扑排序是对测试AOV网是否存在回路的方法!

 

 

拓扑排序的过程中,由于需要查找所有以某顶点为尾的弧,即找到该顶点的所有出边,故图要采用邻接表的存储方式。但拓扑排序较邻接表的存储方式有一点不同,由于要查找入度为0的点、要将某顶点入度减1等,所以要在顶点表中添加一个入度域;

顶点表域:

struct vertexnode
{
	int in;//用于判断该顶点之前是否输出完毕,入度域
	char vertex;
	edgenode *firstedge; 
};

定义边表节点:

struct edgenode {//定义边表节点 
	int adjvex;//邻接点域 
	edgenode *next;
};

邻接表类algraph:

class algraph{
	public:
		algraph(char a[],int n,int e);//构造函数建立n个结点,e条边的图
		~algraph();
		void topsort();
	private:
	vertexnode adjlist[maxsize];//存放顶点表的数组
	int vertexnum,edgenum; 
};

对邻接表进行初始化:

algraph::algraph(char a[],int n,int e)
{
	int i,j,k;
	edgenode *s=NULL;
	vertexnum=n; edgenum=e;
	for( i=0;i<vertexnum;i++){
		adjlist[i].vertex=a[i];
		adjlist[i].firstedge=NULL;
	}
	for(k=0;k<edgenum;k++){
		cout<<"请输入边的两个顶点编号:";
		cin>>i>>j;
		s=new edgenode; s->adjvex=j;//i是头顶点,j是尾顶点
		s->next=adjlist[i].firstedge;
		adjlist[i].firstedge=s; //采用头插法 ,s先指向顶点表域的firstedge,然后使adjlist.firstedge 指向s,从而实现边域的加入;
	}
	for(i=0;i<vertexnum;i++){
		cout<<"请输入每个顶点的入度";
		cin>>adjlist[i].in;//看图,手动入度数;
	}
}

 拓扑排序核心算法:

void algraph::topsort(){
	int i,j,k,count=0;
	int s[maxsize],top=-1;
	edgenode*p=NULL;
	for(i=0;i<vertexnum;i++)
	if(adjlist[i].in==0) s[++top]=i;//循环先遍历一遍,将入度为0的入栈
	while(top!=-1){
		j=s[top--];
		cout<<adjlist[j].vertex<<"\t";//输出顶点坐标
		count++;//记录输出顶点数
		p=adjlist[j].firstedge;
		while (p != NULL)               //描顶点表,找出顶点j的所有出边
    		{
				k = p->adjvex;
      			adjlist[k].in--;            
      			if (adjlist[k].in == 0) s[++top] = k;    //将入度为0的顶点入栈
      			p = p->next;          
    		}
	}
	if (count < vertexnum )  cout << "有回路"; 
	
}

析构函数:

algraph::~algraph()
{
	edgenode *p=NULL,*q=NULL;
	for(int i=0;i<vertexnum;i++)
	{
		p=q=adjlist[i].firstedge;
		while (p!=NULL)
		{
			p=p->next;
			delete q;
			q=p;
		}
	  }  
}

主函数测试:

int main(){
	/*测试数据是图6-27,依次输入边是:
	(1 0)(1 3)(2 3)(2 0)(3 0)(3 5)(4 2)(4 3)(4 5)
/*顶点入度数:3,0,1,3,0,2 */
	char ch[ ] = {'A','B','C','D','E','F'};
	int i;
	algraph alg(ch, 6, 9);               //建立具有5个顶点6条边的有向图
	alg.topsort();
	return 0;
}

运行结果:

Copyright © 2002-2019 某某自媒体运营 版权所有