【數(shù)據(jù)結(jié)構(gòu)與算法】圖的遍歷與拓?fù)渑判?- Toy模板網(wǎng)

這篇具有很好參考價(jià)值的文章主要介紹了【數(shù)據(jù)結(jié)構(gòu)與算法】圖的遍歷與拓?fù)渑判?。希望?duì)大家有所幫助。如果存在錯(cuò)誤或未考慮完全的地方，請(qǐng)大家不吝賜教，您也可以點(diǎn)擊"舉報(bào)違法"按鈕提交疑問。

一、用數(shù)組模擬鄰接表

再上一篇中我們講了樹的兩種存儲(chǔ)方式：【數(shù)據(jù)結(jié)構(gòu)與算法】圖——鄰接表與鄰接矩陣
這一篇我們可以用數(shù)組來模擬鄰接表。
假設(shè)現(xiàn)在我們要進(jìn)行n次操作，實(shí)現(xiàn)無向圖。
首先需要一個(gè)保存是哪個(gè)節(jié)點(diǎn)的數(shù)組e然后就是類似指針數(shù)組的表h，每個(gè)表都會(huì)連一串單鏈表e,ne

int n;

const int N = 1e5 + 10, M = 2 * N;

int h[N], e[M], ne[M], idx;

void add(int a, int b)
{
    e[idx] = b;
    ne[idx] = h[a];
    h[a] = idx++;
}

int main()
{
    memset(h, -1, sizeof h);
    cin >> n;
    int a, b;
    for(int i = 0; i < n; i++)
    {
        cin >> a >> b;
        add(a, b);
        add(b, a);
    }
    return 0;
}

每次插入其實(shí)就是一次頭插，這里要注意把h數(shù)組初始化成-1，以便標(biāo)識(shí)每個(gè)鏈表的結(jié)尾。

二、圖的深度優(yōu)先遍歷（dfs）

2.1 概念

我們之前接觸過樹的遍歷，其實(shí)樹就是一個(gè)特殊的圖，遍歷圖的時(shí)候我們要注意的是有可能會(huì)遍歷到我們之前遍歷過的點(diǎn)，所以需要一個(gè)標(biāo)志位數(shù)組記錄遍歷過的節(jié)點(diǎn)。
給定一個(gè)節(jié)點(diǎn)u，我們就把這個(gè)節(jié)點(diǎn)的所有直接相連的點(diǎn)（沒有被遍歷過的）都進(jìn)行dfs搜索

void add(int a, int b)
{
    e[idx] = b;
    ne[idx] = h[a];
    h[a] = idx++;
}

void dfs(int u)
{
    cnt[u] = true;
    cout << u << " ";
    for(int i = h[u]; i != -1; i = ne[i])
    {
        int j = e[i];
        if(!cnt[j])
        {
            dfs(j);
        }
    }
}

int main()
{
    memset(h, -1, sizeof h);
    cin >> n;
    int a, b;
    for(int i = 0; i < n; i++)
    {
        cin >> a >> b;
        add(a, b);
        add(b, a);
    }
    dfs(1);
    return 0;
}

【數(shù)據(jù)結(jié)構(gòu)與算法】圖的遍歷與拓?fù)渑判? referrerpolicy=
可以看到所有的點(diǎn)都完成了遍歷。

2.2 例題：樹的重心

題目描述：

給定一顆樹，樹中包含 n個(gè)結(jié)點(diǎn)（編號(hào) 1～n）和 n?1條無向邊。
請(qǐng)你找到樹的重心，并輸出將重心刪除后，剩余各個(gè)連通塊中點(diǎn)數(shù)的最大值。
重心定義：重心是指樹中的一個(gè)結(jié)點(diǎn)，如果將這個(gè)點(diǎn)刪除后，剩余各個(gè)連通塊中點(diǎn)數(shù)的最大值最小，那么這個(gè)節(jié)點(diǎn)被稱為樹的重心。

輸入格式

第一行包含整數(shù) n，表示樹的結(jié)點(diǎn)數(shù)。接下來 n?1行，每行包含兩個(gè)整數(shù) a和 b，表示點(diǎn) a
和點(diǎn) b之間存在一條邊。

輸出格式

輸出一個(gè)整數(shù) m，表示將重心刪除后，剩余各個(gè)連通塊中點(diǎn)數(shù)的最大值。

數(shù)據(jù)范圍

1≤n≤105

輸入樣例

9
1 2
1 7
1 4
2 8
2 5
4 3
3 9
4 6

輸出樣例：

4

思路分析：
先解釋一下這句話：如果將這個(gè)點(diǎn)刪除后，剩余各個(gè)連通塊中點(diǎn)數(shù)的最大值
舉個(gè)例子：
【數(shù)據(jù)結(jié)構(gòu)與算法】圖的遍歷與拓?fù)渑判? referrerpolicy=
對(duì)于點(diǎn)F，把他刪除后，會(huì)有四個(gè)連通塊。

它的最大值就是6。而這個(gè)題是要把每個(gè)節(jié)點(diǎn)的這個(gè)最大值求出來，然后取最小值。

那么怎么求呢？

還是以F點(diǎn)舉例子，假設(shè)現(xiàn)在我們從上面遍歷到了F點(diǎn)，下面的幾個(gè)點(diǎn)好求，但是上面的已經(jīng)不能再回去了，但是我們知道了一共有多少個(gè)節(jié)點(diǎn)，我們只需要把下面的節(jié)點(diǎn)個(gè)數(shù)加起來然后再用總數(shù)減去即可得到上面有多少個(gè)節(jié)點(diǎn)，然后取最大值。

#include <iostream>
#include <cstring>

using namespace std;

int n;

const int N = 1e5 + 10, M = 2 * N;
int ans = N;

int h[N], e[M], ne[M], idx;
bool cnt[N];

void add(int a, int b)
{
    e[idx] = b;
    ne[idx] = h[a];
    h[a] = idx++;
}

int dfs(int u)
{
    cnt[u] = true;
    int sum = 1;// 包括當(dāng)前節(jié)點(diǎn)
    int ret = 0;// 記錄最大的連通塊
    for(int i = h[u]; i != -1; i = ne[i])
    {
        int j = e[i];
        if(!cnt[j])
        {
            int tmp = dfs(j);
            sum += tmp;
            ret = max(ret, tmp);
        }
    }
    ret = max(ret, n - sum);
    ans = min(ans, ret);
    return sum;
}

int main()
{
    memset(h, -1, sizeof h);
    cin >> n;
    int a, b;
    for(int i = 0; i < n; i++)
    {
        cin >> a >> b;
        add(a, b);
        add(b, a);
    }
    dfs(1);
    cout << ans << endl;
    return 0;
}

三、圖的廣度優(yōu)先遍歷（bfs）

3.1 概念

我們知道廣度優(yōu)先遍歷要借助隊(duì)列結(jié)構(gòu)，當(dāng)一個(gè)節(jié)點(diǎn)入隊(duì)列后，把所有的相連的點(diǎn)入隊(duì)列。知道隊(duì)列為空，還是跟上面一樣，防止重復(fù)遍歷，要加一個(gè)標(biāo)志位。

int n, m;

const int N = 1e5 + 10;

int h[N], e[N], ne[N], idx;
queue<int> q;
bool cnt[N];

void add(int a, int b)
{
    e[idx] = b;
    ne[idx] = h[a];
    h[a] = idx++;
}

void bfs(int u)
{
    cnt[u] = true;
    q.push(u);
    while(q.size())
    {
        int t = q.front();
        q.pop();
        cout << t << " ";
        for(int i = h[t]; i != -1; i = ne[i])
        {
            int j = e[i];
            if(!cnt[j])
            {
                q.push(j);
                cnt[j] = true;
            }
        }
    }
}

int main()
{
    memset(h, -1, sizeof h);
    cin >> n >> m;
    int a, b;
    while(m--)
    {
        cin >> a >> b;
        add(a, b);
    }
    bfs(1);
    return 0;
}

【數(shù)據(jù)結(jié)構(gòu)與算法】圖的遍歷與拓?fù)渑判? referrerpolicy=

3.2 例題：圖中點(diǎn)的層次

題目描述：

給定一個(gè) n個(gè)點(diǎn) m條邊的有向圖，圖中可能存在重邊和自環(huán)。所有邊的長(zhǎng)度都是 1，點(diǎn)的編號(hào)為 1～n。請(qǐng)你求出 1號(hào)點(diǎn)到 n號(hào)點(diǎn)的最短距離，如果從 1號(hào)點(diǎn)無法走到 n號(hào)點(diǎn)，輸出 ?1。

輸入格式

第一行包含兩個(gè)整數(shù) n和 m。
接下來 m行，每行包含兩個(gè)整數(shù) a和 b，表示存在一條從 a走到 b的長(zhǎng)度為 1的邊。

輸出格式

輸出一個(gè)整數(shù)，表示 1號(hào)點(diǎn)到 n號(hào)點(diǎn)的最短距離。

數(shù)據(jù)范圍

1≤n,m≤105

輸入樣例：

4 5
1 2
2 3
3 4
1 3
1 4

輸出樣例：

1

思路分析：

廣度優(yōu)先遍歷的話，第一次遇到n節(jié)點(diǎn)的距離一定是最短距離，所以我們這里可以把cnt數(shù)組變成d數(shù)組，代表每個(gè)點(diǎn)離起始位置的距離，先全部初始化成-1，當(dāng)節(jié)點(diǎn)要入隊(duì)列時(shí)，如果距離是-1，說明沒有遍歷過，那么就入隊(duì)列，然后改變當(dāng)前點(diǎn)的距離。

#include <iostream>
#include <cstring>
#include <queue>

using namespace std;

int n, m;

const int N = 1e5 + 10;

int h[N], e[N], ne[N], idx;
queue<int> q;
int d[N];

void add(int a, int b)
{
    e[idx] = b;
    ne[idx] = h[a];
    h[a] = idx++;
}

void bfs(int u)
{
    d[u] = 0;
    q.push(u);
    while(q.size())
    {
        int t = q.front();
        q.pop();
        for(int i = h[t]; i != -1; i = ne[i])
        {
            int j = e[i];
            if(d[j] == -1)
            {
                q.push(j);
                d[j] = d[t] + 1;
            }
        }
    }
}

int main()
{
    memset(h, -1, sizeof h);
    memset(d, -1, sizeof d);
    cin >> n >> m;
    int a, b;
    while(m--)
    {
        cin >> a >> b;
        add(a, b);
    }
    bfs(1);
    cout << d[n] << endl;
    return 0;
}

四、拓?fù)渑判?/h2>

4.1 概念

首先要知道什么是拓?fù)渑判颍?br> 在一個(gè)有向圖中，對(duì)所有的節(jié)點(diǎn)進(jìn)行排序，要求沒有一個(gè)節(jié)點(diǎn)指向它前面的節(jié)點(diǎn)。
先統(tǒng)計(jì)所有節(jié)點(diǎn)的入度，對(duì)于入度為0的節(jié)點(diǎn)就可以分離出來，然后把這個(gè)節(jié)點(diǎn)指向的節(jié)點(diǎn)的入度減一。
一直做改操作，直到所有的節(jié)點(diǎn)都被分離出來。
如果最后不存在入度為0的節(jié)點(diǎn)，那就說明有環(huán)，不存在拓?fù)渑判颍簿褪呛芏囝}目的無解的情況。
這里提到了入度的概念，當(dāng)前點(diǎn)的入度其實(shí)就是有多少個(gè)節(jié)點(diǎn)指向當(dāng)前節(jié)點(diǎn)。
我們以入度為0的節(jié)點(diǎn)為突破口，一層一層剝開，如果沒有環(huán)，則一定能夠把所有點(diǎn)的入度減為0。

4.2 例題：有向圖的拓?fù)湫蛄?/h3>

題目描述：

給定一個(gè) n個(gè)點(diǎn) m條邊的有向圖，點(diǎn)的編號(hào)是 1到 n，圖中可能存在重邊和自環(huán)。
請(qǐng)輸出任意一個(gè)該有向圖的拓?fù)湫蛄?，如果拓?fù)湫蛄胁淮嬖?，則輸出 ?1。
若一個(gè)由圖中所有點(diǎn)構(gòu)成的序列 A滿足：對(duì)于圖中的每條邊 (x,y)，x在 A中都出現(xiàn)在 y之前，則稱 A是該圖的一個(gè)拓?fù)湫蛄小?/p>

輸入格式

第一行包含兩個(gè)整數(shù) n 和 m。
接下來 m 行，每行包含兩個(gè)整數(shù) x 和 y，表示存在一條從點(diǎn) x 到點(diǎn) y 的有向邊 (x,y)。

輸出格式

共一行，如果存在拓?fù)湫蛄?，則輸出任意一個(gè)合法的拓?fù)湫蛄屑纯伞?br> 否則輸出 ?1。

數(shù)據(jù)范圍

1≤n,m≤105

輸入樣例：

3 3
1 2
2 3
1 3

輸出樣例：

1 2 3

思路分析

這道題我們也是用廣度優(yōu)先遍歷的思想，先找到所有入度為0的點(diǎn)，全部入隊(duì)列，然后一層層的遍歷，把入度為0的點(diǎn)剝離，把該節(jié)點(diǎn)指向的節(jié)點(diǎn)入度減去1，只要入度為0，就入隊(duì)列，如此循環(huán)即可。
然后出隊(duì)列的元素順序即為拓?fù)渑判颉Ｎ覀冎恍枰涗浫腙?duì)列的數(shù)據(jù)個(gè)數(shù)等不等于總節(jié)點(diǎn)個(gè)數(shù)就可以判斷是否是拓?fù)湫蛄小?span toymoban-style="hidden">文章來源地址http://www.zghlxwxcb.cn/news/detail-445262.html

#include <iostream>
#include <queue>
#include <cstring>

using namespace std;

const int N = 1e5 + 10;

int h[N], e[N], ne[N], idx;
int in[N];// 入邊
queue<int> q;
int res[N];

int n, m, cnt;

void add(int a, int b)
{
    e[idx] = b;
    ne[idx] = h[a];
    h[a] = idx++;
}

void topology()
{
    for(int i = 1; i <= n; i++)
    {
        if(in[i] == 0)
        {
            q.push(i);
        }
    }
    while(q.size())
    {
        int t = q.front();
        q.pop();
        res[cnt++] = t;
        for(int i = h[t]; i != -1; i = ne[i])
        {
            int j = e[i];
            in[j]--;
            if(in[j] == 0)
            {
                q.push(j);
            }
        }
    }
}

int main()
{
    memset(h, -1, sizeof(h));
    cin >> n >> m;
    int a, b;
    while(m--)
    {
        cin >> a >> b;
        add(a, b);
        in[b]++;
    }
    
    topology();
    
    if(cnt == n)
    {
        for(int i = 0; i < n; i++)
        {
            cout << res[i] << " ";
        }
    }
    else
    {
        cout << -1;
    }
    return 0;
}

到了這里，關(guān)于【數(shù)據(jù)結(jié)構(gòu)與算法】圖的遍歷與拓?fù)渑判虻奈恼戮徒榻B完了。如果您還想了解更多內(nèi)容，請(qǐng)?jiān)谟疑辖撬阉鱐OY模板網(wǎng)以前的文章或繼續(xù)瀏覽下面的相關(guān)文章，希望大家以后多多支持TOY模板網(wǎng)！