【算法导论】拓扑排序

拓扑排序

一，邻接表（无前驱实现）

该方法的每一步总是输出当前无前趋(即入度为零)的顶点

其抽象算法可描述为：
　　　　NonPreFirstTopSort(G){//优先输出无前趋的顶点
　　　　 while(G中有入度为0的顶点)

do{
　　　　　 　 从G中选择一个入度为0的顶点v且输出之；（栈顶弹出）
　　　　 　　 从G中删去v及其所有出边；（压栈）
　　　　 }
　　　　 if(输出的顶点数目<|V(G)|)
　　　　 //若此条件不成立，则表示所有顶点均已输出，排序成功。
　　　　　　 Error("G中存在有向环，排序失败！")；
　　　　 }
注意：
　无前趋的顶点优先的拓扑排序算法在具体存储结构下，为便于考察每个顶点的人度，可保存各顶点当前的人度。为避免每次选入度为0的顶点时扫描整个存储空间，可设一个栈或队列暂存所有入度为零的顶点：
　在开始排序前，扫描对应的存储空间，将人度为零的顶点均入栈(队)。以后每次选人度为零的顶点时，只需做出栈(队)操作即可。

二，邻接表（DFS深度优先）

当从某顶点v出发的DFS搜索完成时，v的所有后继必定均已被访问过(想像它们均已被删除)，此时的v相当于是无后继的顶点，因此在DFS算法返回之前输出顶点v即可得到 DAG的逆拓扑序列。
　其中第一个输出的顶点必是无后继(出度为0)的顶点，它应是拓扑序列的最后一个顶点。若希望得到的不是逆拓扑序列，同样可增加T来保存输出的顶点。若假设T是栈，并在DFSTraverse算法的开始处将T初始化，
　利用DFS求拓扑序列的抽象算法可描述为：
void DFSTopSort(G，i，T)

{
//在DisTraverse中调用此算法，i是搜索的出发点，T是栈
int j；
visited[i]=TRUE； //访问i
for(所有i的邻接点j)//即<i，j>∈E(G)
if(!visited[j])
DFSTopSort(G，j，T)；
//以上语句完全类似于DFS算法
Push(&T，i)； //从i出发的搜索已完成，输出i
}
　 只要将深度优先遍历算法DFSTraverse中对DFS的调用改为对DFSTopSort的调用，即可求得拓扑序列T。其具体算法不难从上述抽象算法求精后得到。
　 若G是一个DAG，则用DFS遍历实现的拓扑排序与NonSuccFirstTopSort算法完全类似；但若C中存在有向环，则前者不能正常工作。

综合源码

#include "stdio.h"
#include "malloc.h"
#include "stack.h"
#define MaxSize 10
#define Max     100
stack<int> mystack;//调用系统的栈 
int indegree[Max];
/*邻接表  ：Adjacency list*/
typedef struct ArcNode //边 表节点 
{
    int  adjvex;//邻接点 数值 
	ArcNode *next;//下一个节点 
}ArcNode ;
typedef struct  VertexNode //顶点 表节点 
{
	char  vertex; //顶点表示（A,B，C）
	ArcNode  *firstedge;//第一个邻接点 
}VertexNode,AdjList[MaxSize]; //为什么要写在这个地方 ????

 //vertexNode  AdjList[MaxSize]; //这样为什么不对？？ 
 
typedef struct 
{

	AdjList adjlist ;//顶点表   就是竖着的一排  不能是指针么???????????? !!!!!!!!!!!
	int VertexNumber,arcNum;//图的顶点个数，边个数 
}AlGraph;

void CreatALGraph(AlGraph *G,char a[],int n,int e) //顶点 由数组提供， 边需要用户输入 
{
	 int i,k,j; 
	 G->VertexNumber=n;// 顶点个数 
	 G->arcNum=e;//边个数 	 
	 for(i=0;i<G->VertexNumber;i++)//初始化 顶点列表 
	 {     
		 G->adjlist[i].vertex=a[i];
 	     G->adjlist[i].firstedge=NULL; 
 	 } 
 	 
 	 for(k=0;k<G->arcNum;++k)//每次输入 一条边 <i,j> 将该顶点插入 i 顶点后的列链表中 
 	 {
 	 	 printf("please  input the number of edge's two vertex\n"); 
 	 	 scanf("%d%d",&i,&j);//有向图 f
	     ArcNode *s=(ArcNode *)malloc(sizeof(ArcNode));
		
		 s->adjvex=j; //所邻接的 顶点在顶点列表中的下标
		 
		 //接下来 将创建好的边 表节点插入 节点i 的边表的表头 
		 s->next=G->adjlist[i].firstedge;
		 G->adjlist[i].firstedge=s; 		  
 	 }
}
void print_Graph(AlGraph *G) //简单的打印出来 
{
	int i;
	for(i=0;i<G->VertexNumber;++i) //输出每一行 
	{
		ArcNode *node= G->adjlist[i].firstedge; 
		printf("%c",G->adjlist[i].vertex);//输出链表节点 
	
		while(node)//输出后续节点 
		{
			//printf("--->%d", node->adjvex);
			printf("--->%c", G->adjlist[node->adjvex].vertex);
			node=node->next;
		}
		printf("\n");
	}	   
}

void topsort(AlGraph *G,int n)//通过记录入度 进行拓扑排序
{
	int i;
	 	
	memset(indegree,0,sizeof(indegree));//初始化数组 
	/*void *memset(void *s, int c, size_t n); 　
	　memset:作用是在一段内存块中填充某个给定的值，
	是对较大的结构体或数组进行清零操作的一种最快方法.*/ 
	
	for(i=0;i<n;++i) //初始化整个图 的入度 
	{
	  ArcNode *node= G->adjlist[i].firstedge;
	  
	  while(node) 
	  {
  		 indegree[node->adjvex]++;//让节点 入度加1
		 node=node->next; 
  	  }
		
	} 
	//	printf("%d\n",indegree[1]); 
	for(i=0;i<n;++i)//将入度为0 的元素入栈 
	{
		if(indegree[i]==0)
		   {
		     mystack.push(i);
		   }
	} 	     	
	int  count=0;
	 ArcNode *p; 
	while(mystack.size()!=0)//当栈内 元素不为空
	{
		i=mystack.top();    //记录栈顶 
		mystack.pop();      //弹出栈顶元素 
		printf("%c",G->adjlist[i]);
		count++;
		
	    p= G->adjlist[i].firstedge;
	  
	  	while(p) 
	  	{
		  	 //int k=p->adjvex;//记录下标 方便判断 
	  		 indegree[p->adjvex]--;//让节点 入度减1
		     if(indegree[p->adjvex]==0)
	              mystack.push(p->adjvex);
			 p=p->next; 
  	  	}
  	  
  	  
	}
	if(count<n)
		printf("有回路\n"); 
	     
} 
void DFS_top_sort(AlGraph *G,int v,int visited[])
{
     //int  visited[v];//用来区别 顶点有没有被访问过
  	 int j;
	 //printf("%c",G->adjlist[v].vertex);//输出顶点 （递归调用 条件下文给出）
	 visited[v]=1;
	 ArcNode *p=G->adjlist[v].firstedge;
	 
	 while(p!=NULL)
	 {
	 	j=p->adjvex;//后继 的节点的下标
		if(visited[j]!=1)//后继顶点没有被访问，则递归访问 
	       DFS_top_sort(G,j,visited);
        
         p=p->next; 
 	 } 	 
	 mystack.push(v); //将某个节点后继访问完后 压栈	
} 
void  DFS_one(AlGraph *G)
{
	int  visited[G->VertexNumber];//用来区别 顶点有没有被访问过
	int i;
	for(i=0;i<G->VertexNumber;++i)
        visited[i]=0; //标志向量初始化
 	for(i=0;i<G->VertexNumber;++i)
	   if(visited[i]==0) //i未访问过 
          DFS_top_sort(G,i,visited);//以i为源点开始DFS搜索 
}


void DFS_top_sort_print(AlGraph *G,stack<int> mystack)//深度优先遍历 打印 
{
	while(mystack.size())
	{
		printf("%c",G->adjlist[mystack.top()]);
		mystack.pop();//弹出不需要参数 
	}
	
} 
void NULL_stack(stack<int> mystack)//清空栈 
{
	while(mystack.size())
	{
		
		mystack.pop();//弹出不需要参数 
	}
	
}
int main()
{
	AlGraph *G=(AlGraph *)malloc(sizeof(AlGraph));
	char a[3]={'A','B','C'};
	int n=3;
	int e=2;  
    printf("********************\n");
    printf("1,创建邻接表类型的图\n");
    printf("2,邻接表真实输出\n"); 
    printf("3,入度法拓扑排序\n");
    printf("4,深度优先遍历法拓扑排序\n");
	//printf("4,邻接表广度优先访问\n");
    printf("********************\n");
	 
    int i;
    
    while(1)
    {
	    scanf("%d",&i);    
    	switch(i)
    	{
    		case 1:CreatALGraph(G,a,n,e);
                   printf("创建完毕请继续……\n");break;
    		case 2:print_Graph(G);break;
    		case 3:NULL_stack(mystack);
			       topsort(G,3); 
			       printf("\n");break;
    		case 4:NULL_stack(mystack);
                   DFS_one(G);//深度优先遍历 
			       DFS_top_sort_print(G,mystack);
                   printf("\n");break;
    		case 5:break;
    		case 6:break;
    		case 7:break;
    		case 8:break;
    		case 9:break; 		
    	
   	    }
    	
    }
    
	return 0;
}