新建 文本文档.txt

拓扑排序c版(数据结构)1.邻接表的实现 2.无环情况

struct ArcNode
{
	int adjvex;
	struct ArcNode *nextarc;
};//构造表结点(结构体类型)
struct VNode
{
	int data;
	struct ArcNode *firstarc;
	int OutDegree,InDegree,l;
};构造头结点
main()
{ 
	struct VNode v[20];//定义结构体类型的结点，并设定最大结点数为20
     	struct ArcNode *p1,*p2,*x;//定义头结点指针
	int i,j,a,c,d,k=0,m,n[20],no;
     	printf("input the VertexNum:\n");
     	scanf("%d",&no);//从键盘输入有向图G的顶点数
     	for(i=1;i<=no;i++)
     	v[i].InDegree=0;//每个顶点的入度数赋值为0
     	for(i=1;i<=no;i++)//第一层循环实现输入顶点和出度
    		{ 
			printf("input the vertex_info (vertex_sign and OutDergee):\n");
      			scanf("%d %d",&c,&d);//键盘输入顶点数字代号和顶点的出度数
      			v[i].data=c;//将输入的顶点代号赋值到第i个顶点(结构体)的data区
      			v[i].firstarc=0;
      			v[i].l=1;
      			v[i].OutDergee=d;将输入的顶点的出度数赋值到第i个顶点(结构体)的OutDegree区
      			printf("vertex[%d]_info=%d\n",i,v[i].data);//输出显示顶点信息
       			printf("input arc(input one No. once time):\n");
			for(j=1;j<=v[i].OutDergee;j++)//通过循环输入第i个顶点的链接信息(即邻接点的数字代号)总共循环出度数次
     			{ 
				scanf("%d",&a);//键盘输入第i个顶点的邻接点数字代号赋值到a
				v[a].InDegree++;//第a个顶点的入度加1(v[a]的顶点入度数多了1)
				if(j==1)//如果是输入的是i顶点的第一个邻接点，要创建表结点
     				{ 
					p1=(struct ArcNode *)malloc(sizeof(struct ArcNode));//创建一个表结点
					v[i].firstarc=p1;//v[i].firstarc指针指向第一个依附该顶点的弧的指针
					p1->adjvex=a;//第一个邻接点数字标志是a
					p1->nextarc=0;//下一个邻接点数字标志为0
	 			        printf("v[%d].firstarc=%d\n",i,v[i].firstarc->adjvex);
                                                                                        //屏幕输出i顶点的第一个邻接点为a
				}
	  			else//如果输入的是第二个邻接点的数字代号 
				{ 
					p2=p1;//保存上一条依附该点i的弧的指针
					p1=(struct ArcNode *)malloc(sizeof(struct ArcNode));//再创建一个表结点
					p2->nextarc=p1;//p2->nextarc指向下一条弧的指针
					p1->adjvex=a;//邻接数字标志赋值
					p1->nextarc=0;//下一个邻接数字标志为0
	   				printf("NeighborArc=%d\n",p2->nextarc->adjvex);//屏幕输出i顶点的第一个邻接点为a
				}
     			}
     		}
		printf("v[%d].InDegree=\n",i);//显示i顶点的入度信息
	 	for(i=1; i<=no;i++)//循环顶点总数次
	  	printf(" %d:%d \n",i,v[i].InDegree);//输出显示各顶点的入度信息
       		
		for(j=1;j<=no;j++)//拓扑排序开始
     		{ 
			for (i=1;i<=no;i++)
   					//找出一个入度为0而且没有被访问过的顶点(通过v[i].l标志i顶点是否被访问过)
     			{ 
				if(v[i].InDegree==0&&v[i].l)//入度为零而且v[i].l==1时执行(已经初始赋值v[i].l=1)
      				{ 
					n[k]=v[i].data;//入度为零的顶点入栈
	 				k++;//对入度为零的顶点计数
	 				v[i].l=0;//标识顶点i已经被访问过
					if (v[i].firstarc!=0)//如果i顶点的第一个临界点数字代号不是0
      					{  	
						m=v[i].firstarc->adjvex;//给m赋值等于i顶点的邻接点数字代号
	   					v[m].InDegree--;对第i个顶点的每一个邻接点的入度减1
	   					x=v[i].firstarc;//i顶点第一个邻接点数字代号的信息用指针x指向
	    					while (x->nextarc!=0)//如过第一个邻接点之后的邻接点数字代号不等于0继续执行上                              											    边的语句
	  					{   
							m=x->nextarc->adjvex;
	       						v[m].InDegree--;
	       						x=x->nextarc;
	   					}
					}
                                        printf("The Topogical Order as this: \n  %d",i)//输出有向图G的拓扑排序
	  				break;//跳出循环
	  			}
	 		}
       		}
      		if (k==no)//下边语句判断该有向图是否有环的存在
		printf("circle is  not exist!\n");
	 	else  printf ("error circle exist!\n");
}