數(shù)據(jù)結(jié)構(gòu)–拓?fù)渑判?/h2>

AOV?

$AOV?$(Activity On Vertex NetWork，?頂點表示活動的?)：
?$DAG圖$（有向?環(huán)圖）表示?個?程。頂點表示活動，有向邊$<V_i,V_j>$表示活動Vi必須先于活動$V_j$進?

$注：如果圖中存在環(huán)路就不是AOV網(wǎng)$

DAG圖是指有向無環(huán)圖（Directed Acyclic Graph），是一種有向圖的特殊形式。它由一些有向邊連接的節(jié)點組成，并且不存在任何形式的環(huán)。換句話說，從任何一個節(jié)點出發(fā)，沿著有向邊的方向無法經(jīng)過一系列的節(jié)點再回到原始節(jié)點。DAG圖常用于表示一些具有依賴關(guān)系的任務(wù)或事件，其中每個節(jié)點表示一個任務(wù)或事件，有向邊表示任務(wù)或事件之間的依賴關(guān)系。DAG圖在計算機科學(xué)和工程中有廣泛的應(yīng)用，例如任務(wù)調(diào)度、編譯器優(yōu)化、數(shù)據(jù)流分析等領(lǐng)域。

拓?fù)渑判?/h3>

$拓?fù)渑判?/span>$：在圖論中，由?個$有向?環(huán)圖$的頂點組成的序列，當(dāng)且僅當(dāng)滿?下列條件時，稱為該圖的?個拓?fù)渑判颍?br> ① 每個頂點出現(xiàn)且只出現(xiàn)?次。
② 若頂點A在序列中排在頂點B的前?，則在圖中不存在從頂點B到頂點A的路徑。或定義為：拓?fù)渑判蚴菍τ邢?環(huán)圖的頂點的?種排序，它使得若存在?條從頂點A到頂點B的路徑，則在排序中頂點B出現(xiàn)在頂點A的后?。每個AOV?都有?個或多個拓?fù)渑判蛐蛄小?/p>

上圖其中一個拓?fù)渑判颍?/p>

拓?fù)渑判虻膶崿F(xiàn)：

① 從AOV?中選擇?個沒有前驅(qū)的頂點并輸出。
② 從?中刪除該頂點和所有以它為起點的有向邊。
③ 重復(fù)①和②直到當(dāng)前的AOV?為空或當(dāng)前?中不存在?前驅(qū)的頂點為?。

$注：拓?fù)渑判蛐蛄锌赡苡卸鄠€$

拓?fù)渑判虼a實現(xiàn)

王道書上代碼

個人code

#include <iostream>
#include <cstring>
using namespace std;
const int N = 100010;
int n, m;
int h[N], e[N], ne[N], idx;
int q[N], d[N];
void add(int a, int b)
{
    e[idx] = b;
    ne[idx] = h[a];
    h[a] = idx++;
}
bool topsort()
{
    int tt = -1, hh = 0;

    for(int i = 1; i <= n; i++)
        if(!d[i])
            q[++tt] = i;

    while(hh <= tt)
    {
        int t = q[hh++];
        for(int i = h[t]; i != -1; i = ne[i])
        {
            int j = e[i];
            d[j]--;
            if(!d[j]) q[++tt] = j;
        }
    }

    return tt == n - 1;
}
int main()
{
    cin >> n >> m;

    memset(h, -1, sizeof(h));

    for(int i = 0; i < n; i++)
    {
        int a, b;
        cin >> a >> b;
        add(a, b);
        d[b]++;
    }

    if(topsort())
    {
        for(int i = 0; i < n; i++)
            cout << q[i] << ' ';
        cout << endl;
    }
    else cout << "-1" << endl;

    return 0;
}

判斷是否存在拓?fù)湫?/p>

時間復(fù)雜度 O(n + m), n 表示點數(shù)，m表示邊數(shù)
bool topsort()
{
    int hh = 0, tt = -1;
    // d[i] 存儲點i的?度
    for (int i = 1; i <= n; i ++ )
        if (!d[i])
            q[ ++ tt] = i;
    while (hh <= tt)
    {
        int t = q[hh ++ ];
        for (int i = h[t]; i != -1; i = ne[i])
        {
            int j = e[i];
            if (-- d[j] == 0)
                q[ ++ tt] = j;
        }
    }
    // 如果所有點都?隊了，說明存在拓?fù)湫蛄?；否則不存在拓?fù)湫蛄小?/span>
    return tt == n - 1;
}

逆拓?fù)渑判?/h3>

對?個AOV?，如果采?下列步驟進?排序，則稱之為$逆拓?fù)渑判?/span>$：
① 從AOV?中選擇?個沒有后繼（$出度為0$）的頂點并輸出。
② 從?中刪除該頂點和所有以它為終點的有向邊。
③ 重復(fù)①和②直到當(dāng)前的AOV?為空。

其中一個逆拓?fù)渑判?/p>

逆拓?fù)渑判虼a實現(xiàn)

逆拓?fù)渑判虻膶崿F(xiàn)（DFS算法）

DFS判斷是否有環(huán)：

int vis[N], cnt; // timestamp
int per[N];
bool cyc[N];// 標(biāo)記
void dfs(int u) //找環(huán) & 標(biāo)記環(huán)
{
    vis[u] = ++cnt;
    for (auto v : g[u])
    {
        if (per[u] == v)
            continue;
        if (!vis[v])
        {
            per[v] = u;
            dfs(v);
        }
        else if (vis[u] > vis[v])
        {
            for (int i = u; i != v; i = per[i])
                cyc[i] = true;
            cyc[v] = true;
        }
    }
}

如果單純判斷是否有環(huán)，只需要引進父結(jié)點（fa）
dfs(u,fa)
如果 u == fa 則存在環(huán)文章來源地址http://www.zghlxwxcb.cn/news/detail-655861.html

知識點回顧與重要考點

到了這里，關(guān)于數(shù)據(jù)結(jié)構(gòu)--拓?fù)渑判虻奈恼戮徒榻B完了。如果您還想了解更多內(nèi)容，請在右上角搜索TOY模板網(wǎng)以前的文章或繼續(xù)瀏覽下面的相關(guān)文章，希望大家以后多多支持TOY模板網(wǎng)！