拓撲排序講解

在這裡我們要說的拓撲排序是有前提的

        我們在這裡說的拓撲排序是基於有向無環圖的！！！。

(⊙o⊙)…我所說的有向無環圖都知道是什麼東西吧。。

如果不知道，我們下麵先來來說說什麼是有向無環圖。

所謂有向無環圖，顧名思義是不存在環的有向圖（至於有向圖是什麼不知道的在前面我們有一個圖論講解上都有）。

點的入度：以這個點為結束點的邊數。

點的出度：以這個點為出發點的邊的條數。

拓撲序就是對於一個節點的一個排列，使得（u，v）屬於E，那麼u一定出現在v的前面。然而拓撲排序就是一個用來求拓撲序的東西。

對於左面的這個圖，一個合法的拓撲序是（1,2,4,3,5）。

又有一個問題了，知道了這些東西後，我們又要怎樣求一個有向無環圖的拓撲序呢？

我們可以觀察到拓撲排序的定義是：若(u,v)∈E，那麼u在排列中出現的位置一定在v前面。

也就是說，考慮一個節點u，當我們刪除u在序列中處於他前面的所有點之後，u的入度應該是0.

因此，我們就得到了一個拓撲排序的大致的演算法思路。

具體怎麼著呢  ？。？

迴圈n次

    選定一個入度為0且仍存在（未出現在序列中）的點v

　 刪除點v以及從從點v出發的所有邊，更新剩餘點的入度

重覆上述過程，這樣我們就可以得到一個合法的拓撲序。

既然這樣，我們就總結下拓撲排序的精髓吧。

精髓（具體方法）：
⑴ 從圖中選擇一個入度為0的點加入拓撲序列。
⑵ 從圖中刪除該結點以及它的所有出邊（即與之相鄰點入度減1）。
反覆執行這兩個步驟，直到所有結點都已經進入拓撲序列。

還可不可以消化得了？

如果還不可以的話，下麵我們就來具體講一講拓撲排序吧。

參考博客：http://blog.csdn.net/dm_vincent/article/details/7714519

一。定義

將有向圖中的頂點以線性方式進行排序。即對於任何連接自頂點u到頂點v的有向邊uv，在最後的排序結果中，頂點u總是在頂點v的前面。

如果這個概念還略顯抽象的話，那麼不妨考慮一個非常非常經典的例子——選課。我想任何看過數據結構相關書籍的同學都知道它吧。假設我非常想學習一門機器學習的課程，但是在修這麼課程之前，我們必須要學習一些基礎課程，比如電腦科學概論，C語言程式設計，數據結構，演算法等等。那麼這個制定選修課程順序的過程，實際上就是一個拓撲排序的過程，每門課程相當於有向圖中的一個頂點，而連接頂點之間的有向邊就是課程學習的先後關係。只不過這個過程不是那麼複雜，從而很自然的在我們的大腦中完成了。將這個過程以演算法的形式描述出來的結果，就是拓撲排序。

二。代碼實現

#include <bits/stdc++.h>
using namespace std;

const int maxn=100000+15;
struct Edge
{
    int x,y,next;
    Edge(int x=0,int y=0,int next=0):
    x(x),y(y),next(next) {}
}edge[maxn];
int n,m,head[maxn],sumedge,inn[maxn];
int ins(int x,int y)
{
    edge[++sumedge]=Edge(x,y,head[x]);
    return head[x]=sumedge;
}
int Head,tail,que[maxn];
int main()
{
    scanf("%d%d",&n,&m);
    for (int i=1;i<=m;i++)
    {
        int x,y;
        scanf("%d%d",&x,&y);
        ins(x,y);
        inn[y]++;
    }
    Head=1;tail=0;
    for (int i=1;i<=n;i++)
     if (inn[i]==0) que[++tail]=i;//如果該點的入度為0,刪掉與這個點相連的點,刪後如果入度為0的話,把該點入隊 .
    for (;Head<=tail;Head++)//迴圈枚舉與該點相連的點，把該點入隊。 
    {//迴圈上述過程，直到說有的點都入隊（有向無環圖，每一個點肯定都與一個點相連，這樣我們重覆這個過程，就可以很好地把所有的帶點都考慮到，如此一來，所有的點就都入隊了。 
        int x=que[Head];
        for (int u=head[x];u;u=edge[u].next)
        {
            inn[edge[u].y]--;//刪掉與這個點相連的點
            if (inn[edge[u].y]==0)// 刪後如果入度為0的話
             que[++tail]=edge[u].y;//把該點入隊 
        }
    }
    return 0;
}

就說這些吧，我們在下麵還會再說幾個例題。（那就請看下一頁吧）