最簡單的拓撲排序 拓撲排序方法如下: (1)從有向圖中選擇一個沒有前驅(即入度為0)的頂點並且輸出它. (2)從網中刪去該頂點,並且刪去從該頂點發出的全部有向邊. (3)重復上述兩步,直到剩余的網中不再存在沒有前驅的頂點或者所有的點都排序完畢為止. [cpp] #include<stdio.h> #include<string.h> #define N 505 int map[N][N],index[N],used[N],n,m; //map表示鄰接矩陣，index記錄入度，used記錄是否排序 void toposort() { int i,j,topo=0; while(topo<n){ for(i=1;i<=n;i++){ if(index[i]==0&&used[i]==0){//i從小到大，號碼小的優先 used[i]=1;break;//刪除入度為0的點 } } if(i==n+1)return;//如果沒有入度為一的點則結束 if(topo) printf(" "); printf("%d",i); topo++; for(j=1;j<=n;j++){//將所有以 i 為起點的邊刪除 if(map[i][j]==1){ map[i][j]=0; index[j]--; } } } } int main() { int i,a,b; while(scanf("%d%d",&n,&m)!=EOF){ memset(map,0,sizeof(map)); memset(index,0,sizeof(index)); memset(used,0,sizeof(used)); for(i=1;i<=m;i++){ scanf("%d%d",&a,&b); if(map[a][b]==0){//考慮重邊的情況 map[a][b]=1; index[b]++; } } toposort(); printf("\n"); } return 0; }
