拓扑排序的c语音实现
//本程序用的是邻接矩阵的方法计算拓扑排序的。 #include<stdio.h>#define N 6//这是代表了 节点的个数 void Topologicalsort(int matrix[][N]);//以下几个是简单的堆栈函数因为文中要用到。 void initstack(int*stack,int*n){ for(int i=0;i<*n+1;i++) stack[i]=-1; *n=0; }void push(int*stack,int *n,int elem){ stack[*n]=elem; (*n)++; }int pop(int*stack,int *n){ int temp; (*n)--; temp=stack[*n] ; stack[*n]=-1; return temp; }int isempty(int*stack,int *n){ if(*n) return 0; return 1; }int main(){ int matrix[N][N]={{0,1,1,1,0,0}, {0,0,0,0,0,0}, {0,1,0,0,1,0}, {0,0,0,0,1,0}, {0,0,0,0,0,0}, {0,0,0,1,1,0}}; //初始化邻接矩阵。 for(int i=0;i<N;i++){ for(int j=0;j<N;j++) printf(" %d ",matrix[i][j]); printf("\n");}//打印矩阵 Topologicalsort(matrix); getchar(); return 0;}//拓扑排序函数 void Topologicalsort(int matrix[][N]){ int indegree[N]={0};//入度矩阵 int sortorder[N]={0};//这是用于存放最后的拓扑排序 的序列 int sortordercurse=0; int stack[N+1]; int curse=N+1; initstack(stack,&curse); int count=0;//用来指示入度为0的顶点个数 for(int j=0;j<N;j++){ for(int i=0;i<N;i++) indegree[j]+=matrix[i][j]; if(!(indegree[j])) push(stack,&curse,j); } //入度为0的顶点入栈 while(!(isempty(stack,&curse))) { int tp; tp=pop(stack,&curse); sortorder[sortordercurse++]=tp; count++; for(int i=0;i<N;i++){ if((indegree[i]==1)&&(matrix[tp][i]==1)) push(stack,&curse,i); indegree[i]-=matrix[tp][i];}//对出栈的顶点所指向的顶点减一 ，并且将入度为0的顶点入栈。 } if(count==N){ printf("\n\nthe Topologicalsort is exist\nit's sort can be:"); for(int i=0;i<sortordercurse;i++) printf(" V%d ",sortorder[i]+1);} else{ printf("\n\nalert!!!\nthe Topologicalsort isnot exist\n");} //判断是否是拓扑排序。 }
