數(shù)據(jù)結(jié)構(gòu)之圖論(續(xù))

前言

在之前的推文中，我們了解了什么是圖，以及一些圖的DFS和BFS的基本操作，這一期本小編將繼續(xù)為大家介紹一些關(guān)于圖的基本算法，一起看下吧。

NO.1

關(guān)節(jié)點(diǎn)和雙聯(lián)通域

在一個(gè)無向圖G中，若將某個(gè)節(jié)點(diǎn)v去除之后后G所包含的連通域增多，則v稱作切割節(jié)點(diǎn)（cut vertex或關(guān)節(jié)點(diǎn)（articulation point）。如果一個(gè)圖不含任何關(guān)節(jié)點(diǎn)則稱之為雙連通圖，最典型的就是完全圖。任一無向圖都可視作由若干個(gè)極大的雙連 通子圖組合而成，這樣的每一子圖都稱作原圖的一個(gè)雙連通域（bi-connected component）。例如下圖中的節(jié)點(diǎn)3和5就是關(guān)節(jié)點(diǎn)。

較之其它頂點(diǎn)，關(guān)節(jié)點(diǎn)更為重要。在網(wǎng)絡(luò)系統(tǒng)中它們對應(yīng)于網(wǎng)關(guān)，決定子網(wǎng)之間能否連通。在航空系統(tǒng)中，某些機(jī)場的損壞，將 同時(shí)切斷其它機(jī)場之間的交通。故在資源總量有限的前提下， 找出關(guān)節(jié)點(diǎn)并重點(diǎn)予以保障，是提高系統(tǒng)整體穩(wěn)定性和魯棒性的基本策略。接下來就讓我們來看下求關(guān)節(jié)點(diǎn)的算法吧。

NO.2

關(guān)節(jié)點(diǎn)算法

????遇事不決先暴力，按照暴力來解決：首先，通過BFS或DFS搜索統(tǒng)計(jì)出圖G所含連通域 的數(shù)目；然后逐一枚舉每個(gè)頂點(diǎn)v，暫時(shí)將其從圖G中刪去，并再次通過搜索統(tǒng)計(jì)出圖G\{v}所含 連通域的數(shù)目。于是，頂點(diǎn)v是關(guān)節(jié)點(diǎn)，當(dāng)且僅當(dāng)圖G\{v}包含的連通域多于圖G。這一算法需執(zhí)行n趟搜索，耗時(shí)O(n(n + e))，等它算出來黃花菜都涼了。

????那我們先分析下，首先在DFS樹上面，葉節(jié)點(diǎn)不可能是關(guān)節(jié)點(diǎn)，因?yàn)閷⑷~節(jié)點(diǎn)刪去后不會(huì)影響樹的連通性。另外，如果根節(jié)點(diǎn)有兩個(gè)及兩個(gè)以上的分支，則根節(jié)點(diǎn)一定是關(guān)節(jié)點(diǎn)，因?yàn)镈FS會(huì)將此節(jié)點(diǎn)以下的所有點(diǎn)加入到分支中，如果有多個(gè)分支則這些分支是不相互連通的。

????現(xiàn)在考慮內(nèi)部節(jié)點(diǎn)。若節(jié)點(diǎn)C的移除導(dǎo)致其某一棵（比如以D為根的）真子樹與其真祖先（比如A）之間無法連通，則C必為關(guān)節(jié)點(diǎn)。反之，若C的所有真子樹都能（如以E為根的子 樹那樣）與C的某一真祖先連通，則C就不可能是關(guān)節(jié)點(diǎn)。那么只要 在DFS搜索過程記錄并更新各頂點(diǎn)v所能（經(jīng)由后向邊）連通的最高祖先（highest connected ancestor, HCA）hca[v]，即可及時(shí)認(rèn)定關(guān)節(jié)點(diǎn)，并報(bào)告對應(yīng)的雙連通域。??

????思路出來了，那就是代碼實(shí)現(xiàn)了

#include#include#include#include#include#includeusing namespace std;const int maxn = 100000;vector G[maxn];bool vis[maxn];int N, prenum[maxn], parent[maxn], hca[maxn], timer = 1;void dfs(int current, int prev);void art_points();int main(){    cout << "輸入數(shù)據(jù)；（點(diǎn)數(shù)）（邊數(shù)）" << endl;    int i, m, s, t;    cin >> N >> m;    cout << "邊的數(shù)據(jù)"<    for (i = 0; i < m; i++)    {
        cin >> s >> t;        G[s].push_back(t);        G[t].push_back(s);    }    art_points();    system("pause");    return 0;}void print(){    cout << "以 G 的任意頂點(diǎn)作為起點(diǎn)進(jìn)行DFS，將各頂點(diǎn) u 的訪問（首次發(fā)現(xiàn)）順序記錄\nparent[i]：";    for (int i = 0; i < N; ++i)    {        cout << i << "-" << parent[i] << " ";    }    cout << endl << endl;    cout << "通過DFS生成一棵樹（DFS Tree）,其中結(jié)點(diǎn) u 的父節(jié)點(diǎn)記錄\nprenum[i]：";    for (int i = 0; i < N; ++i)    {        cout << i << "-" << prenum[i] << " ";    }    cout << endl << endl;    cout << "新各頂點(diǎn)v所能（經(jīng)由后向邊）連通的最高祖先\nhca[i]：";    for (int i = 0; i < N; ++i)    {        cout << i << " " << hca[i] << " ";    }    cout << endl << endl;}void art_points(){    int i, np = 0, p;    set ap;    dfs(0, -1);    for (i = 1; i < N; i++)    {        p = parent[i];        if (p == 0) np++;        else if (prenum[p] <= hca[i]) ap.insert(p);    }    if (np > 1) ap.insert(0);    print();    cout << "關(guān)節(jié)點(diǎn)：";    for (set::iterator it = ap.begin(); it != ap.end(); it++)        cout << *it << " ";}void dfs(int current, int prev){    int next, i;    prenum[current] = hca[current] = timer;    timer++;    vis[current] = 1;    for (i = 0; i < G[current].size(); i++)    {        next = G[current][i];        if (!vis[next])        {            parent[next] = current;            dfs(next, current);            hca[current] = min(hca[current], hca[next]);        }        else if (next != prev)            hca[current] = min(hca[current], prenum[next]);    }}

NO.3

最小支撐樹

在上面我們介紹了關(guān)節(jié)點(diǎn)算法，現(xiàn)在我們來談下另外一個(gè)概念，支撐樹。在一個(gè)聯(lián)通圖G中，某一個(gè)能夠連接所有點(diǎn)的無環(huán)子圖，則稱作G的一棵支撐 樹或生成樹（spanning tree），如果邊帶有權(quán)值，那么生成的支撐樹中所有權(quán)值最小樹就是最小支撐樹或者最小生成樹。?

聚類分析、網(wǎng)絡(luò)架構(gòu)設(shè)計(jì)、VLSI布線設(shè)計(jì)等諸多實(shí)際應(yīng)用問題，都可轉(zhuǎn)化并描述為最小支 撐樹的構(gòu)造問題。在這些應(yīng)用中，邊的權(quán)重大多對應(yīng)于某種可量化的成本，因此作為對應(yīng)優(yōu)化問 題的基本模型，掌握最小生成樹算法很重要。
????這種問題，暴力是不可取的，時(shí)間復(fù)雜度太高，那么讓我們一步步分析下。

我們首先假設(shè)G=(V，E）是一個(gè)連通網(wǎng)絡(luò)，U是頂點(diǎn)集V的一個(gè)非空真子集。若(u，v）是G中一條“一個(gè)端點(diǎn)在U中（例如：u∈U），另一個(gè)端點(diǎn)不在U中的邊（例如：v∈V-U），且（u，v）具有最小權(quán)值，則一定存在G的一棵最小生成樹包括此邊（u，v），我們先假設(shè)這條邊為安全邊ri。

這樣，我們假設(shè)我們要的樹是個(gè)只包含一個(gè)點(diǎn)的集合即為U，另外的點(diǎn)為V-U，然后我們就把安全邊加入進(jìn)去，然后更新這兩個(gè)集合的數(shù)據(jù)。依次進(jìn)行下去直到所有點(diǎn)進(jìn)入。但是這樣子的時(shí)間復(fù)雜度還是有點(diǎn)高，我們想一下還有上面優(yōu)化的方法。怎樣才能減少每次更新的時(shí)間呢？我們還有一個(gè)強(qiáng)大的助手STL。

STL中的優(yōu)先隊(duì)列提供了快捷的插入和修改，可以極大地優(yōu)化時(shí)間。

下為示例與優(yōu)化后的代碼：

a> 首先選擇A結(jié)點(diǎn)作為點(diǎn)集

b> 找A--B，A--D，A--G權(quán)值最小的點(diǎn)(B)，之后將其加入點(diǎn)集中

c> 找點(diǎn)集中跨越邊最小的邊，A--D,A--G,B--C,到D的權(quán)值最小，將其加入到點(diǎn)集中

d> 重復(fù)上述過程，A--G,D--G,D--E,B--C，到G的權(quán)值最小，將其加入到點(diǎn)集中

一直重復(fù)上述步驟直到找到的邊數(shù)為n-1條，i就是通過Prim算法找到的最小生成樹了。

#define inf (1 << 30)using namespace std;const int maxn = 110;const int maxm = 5e5 + 50;int dis[110];map G_map;int timer = 1;struct node {    int cost, pre;    char to;    friend bool operator < (node a, node b)    {        return a.cost > b.cost;    }}e[maxm];int id[maxn], cnt;int vis[maxn];bool in[maxn];priority_queue q;void init(int n){    memset(id, 0, sizeof(id));    memset(vis, 0, sizeof(vis));    memset(in, 0, sizeof(in));    cnt = 0;    for (int i = 0; i <= n; i++)        dis[i] = inf;    while (q.size())q.pop();}void add(char from, char to, int cost){    e[cnt].to = to;    e[cnt].cost = cost;    e[cnt].pre = id[G_map[from]];    id[G_map[from]] = cnt++;}int queue_prim(char s, int n){    cout << "首先加入點(diǎn)" << s << endl;    int res = 0;    vis[G_map[s]] = 1;    for (int i = id[G_map[s]]; i; i = e[i].pre)        q.push(e[i]);    for (int i = 1; i < n; i++)    {        if (q.size() == 0)break;        node now = q.top();        q.pop();        if (vis[G_map[now.to]] == 1)        {            while (vis[G_map[now.to]])            {                now = q.top();                q.pop();            }        }        printf("第%d次加入點(diǎn)：%c\n", ++timer, now.to);        res += now.cost;        vis[G_map[now.to]] = 1;        for (int j = id[G_map[now.to]]; j; j = e[j].pre)        {            if (!vis[G_map[now.to]])q.push(e[j]);        }    }    return res;}int main(){    int n,m,tot;    cout << "輸入點(diǎn)數(shù)與邊數(shù)" << endl;    cin >> n >> m;    tot = 0;    char a, b,ST;    int  x;    init(n);    cout << "輸入邊的數(shù)據(jù)：" << endl;    for (int i = 1; i <= m ; i++)     {       cin >> a >> b >> x;       if (i == 1) ST = a;       if (!in[a]) G_map[a] = ++tot, in[a] = 1;       if (!in[b]) G_map[a] = ++tot, in[b] = 1;       add(a, b, x);       add(b, a, x);     }     cout<<"最小生成樹的最小權(quán)值和：" << queue_prim(ST, n);     return 0;}

NO.4

最小生成樹之Krusal

? ? ?Prim算法是把我們要的樹先假設(shè)為空，這是一種思路，接下來我們就來介紹下另外一種經(jīng)典算法Krusal算法。

????我們首先假設(shè) WN=(V,{E}) 是一個(gè)含有 n 個(gè)頂點(diǎn)的連通網(wǎng)，則按照克魯斯卡爾算法構(gòu)造最小生成樹的過程為：先構(gòu)造一個(gè)只含 n 個(gè)頂點(diǎn)，而邊集為空的子圖，若將該子圖中各個(gè)頂點(diǎn)看成是各棵樹上的根結(jié)點(diǎn)，則它是一個(gè)含有 n 棵樹的一個(gè)森林。之后，從網(wǎng)的邊集 E 中選取一條權(quán)值最小的邊，若該條邊的兩個(gè)頂點(diǎn)分屬不同的樹，則將其加入子圖，也就是說，將這兩個(gè)頂點(diǎn)分別所在的兩棵樹合成一棵樹；反之，若該條邊的兩個(gè)頂點(diǎn)已落在同一棵樹上，則不可取，而應(yīng)該取下一條權(quán)值最小的邊再試之。依次類推，直至森林中只有一棵樹，也即子圖中含有 n-1條邊為止。

????這種方法與prim算法有著一定的相似之處，但是Krusal算法可以同時(shí)存在多個(gè)樹，但在prim算法中同時(shí)只能有兩個(gè)樹。

????與此同時(shí)我們也可以用STL進(jìn)行優(yōu)化操作.

#include#include#include#include#includeusing namespace std;#define N 1000int par[N];int rank1[N];int sum;struct node{  char from;  char to;  int p;}f1, f2;
struct cmp{  bool operator()(node f1, node f2){    return f1.p > f2.p;  }};priority_queue, cmp> pq;int find(int x){  if (x == par[x])    return x;  else    return par[x] = find(par[x]);}bool join(int a, int b){  int fa;  int fb;  fa = find(a);  fb = find(b);  if (fa == fb)  {    return false;  }  else if (rank1[fa] > rank1[fb])  {    par[fb] = fa;  }  else   {    if (rank1[fa] == rank1[fb])    {      rank1[fb]++;    }    par[fa] = fb;  }  return true;}void krustal(int num){  int i=1;  while (pq.empty() != 1)  {
    int x = pq.top().from;    int y = pq.top().to;    int s = pq.top().p;    printf("嘗試的第%d條邊: %c %c %d", i++,x,y,s);    pq.pop();    if (join(x, y))    {      cout << " ——加入\n"; sum += s;    }    else    {      cout << "——不加入\n";    }    }  cout << "最小生成樹的最小權(quán)值和：" << sum << endl;}int main(){  int n, m;  cout << "輸入點(diǎn)數(shù)與邊數(shù)" << endl;  cin >> n >> m;  int i;  sum = 0;  int a, b, c;  node k;  cout << "輸入邊的數(shù)據(jù)：" << endl;  for (i = 0; i < m; i++)  {    cin >> k.from >> k.to >> k.p;    par[int(k.from)] = k.from;    par[int(k.to)] = k.to;    rank1[int(k.from)] = 1;    rank1[int(k.to)] = 1;    pq.push(k);  }  krustal(m);  return 0;}