数据结构之图论(续)

前言

在之前的推文中，我们了解了什么是图，以及一些图的DFS和BFS的基本操作，这一期本小编将继续为大家介绍一些关于图的基本算法，一起看下吧。

NO.1

关节点和双联通域

在一个无向图G中，若将某个节点v去除之后后G所包含的连通域增多，则v称作切割节点（cut vertex或关节点（articulation point）。如果一个图不含任何关节点则称之为双连通图，最典型的就是完全图。任一无向图都可视作由若干个极大的双连 通子图组合而成，这样的每一子图都称作原图的一个双连通域（bi-connected component）。例如下图中的节点3和5就是关节点。

较之其它顶点，关节点更为重要。在网络系统中它们对应于网关，决定子网之间能否连通。在航空系统中，某些机场的损坏，将 同时切断其它机场之间的交通。故在资源总量有限的前提下， 找出关节点并重点予以保障，是提高系统整体稳定性和鲁棒性的基本策略。接下来就让我们来看下求关节点的算法吧。

NO.2

关节点算法

    遇事不决先暴力，按照暴力来解决：首先，通过BFS或DFS搜索统计出图G所含连通域 的数目；然后逐一枚举每个顶点v，暂时将其从图G中删去，并再次通过搜索统计出图G\{v}所含 连通域的数目。于是，顶点v是关节点，当且仅当图G\{v}包含的连通域多于图G。这一算法需执行n趟搜索，耗时O(n(n + e))，等它算出来黄花菜都凉了。

    那我们先分析下，首先在DFS树上面，叶节点不可能是关节点，因为将叶节点删去后不会影响树的连通性。另外，如果根节点有两个及两个以上的分支，则根节点一定是关节点，因为DFS会将此节点以下的所有点加入到分支中，如果有多个分支则这些分支是不相互连通的。

    现在考虑内部节点。若节点C的移除导致其某一棵（比如以D为根的）真子树与其真祖先（比如A）之间无法连通，则C必为关节点。反之，若C的所有真子树都能（如以E为根的子 树那样）与C的某一真祖先连通，则C就不可能是关节点。那么只要 在DFS搜索过程记录并更新各顶点v所能（经由后向边）连通的最高祖先（highest connected ancestor, HCA）hca[v]，即可及时认定关节点，并报告对应的双连通域。  

    思路出来了，那就是代码实现了

#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 << "输入数据；（点数）（边数）" << endl;    int i, m, s, t;    cin >> N >> m;    cout << "边的数据"<    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 的任意顶点作为起点进行DFS，将各顶点 u 的访问（首次发现）顺序记录\nparent[i]：";    for (int i = 0; i < N; ++i)    {        cout << i << "-" << parent[i] << " ";    }    cout << endl << endl;    cout << "通过DFS生成一棵树（DFS Tree）,其中结点 u 的父节点记录\nprenum[i]：";    for (int i = 0; i < N; ++i)    {        cout << i << "-" << prenum[i] << " ";    }    cout << endl << endl;    cout << "新各顶点v所能（经由后向边）连通的最高祖先\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 << "关节点：";    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

最小支撑树

在上面我们介绍了关节点算法，现在我们来谈下另外一个概念，支撑树。在一个联通图G中，某一个能够连接所有点的无环子图，则称作G的一棵支撑 树或生成树（spanning tree），如果边带有权值，那么生成的支撑树中所有权值最小树就是最小支撑树或者最小生成树。 

聚类分析、网络架构设计、VLSI布线设计等诸多实际应用问题，都可转化并描述为最小支 撑树的构造问题。在这些应用中，边的权重大多对应于某种可量化的成本，因此作为对应优化问 题的基本模型，掌握最小生成树算法很重要。
    这种问题，暴力是不可取的，时间复杂度太高，那么让我们一步步分析下。

我们首先假设G=(V，E）是一个连通网络，U是顶点集V的一个非空真子集。若(u，v）是G中一条“一个端点在U中（例如：u∈U），另一个端点不在U中的边（例如：v∈V-U），且（u，v）具有最小权值，则一定存在G的一棵最小生成树包括此边（u，v），我们先假设这条边为安全边ri。

这样，我们假设我们要的树是个只包含一个点的集合即为U，另外的点为V-U，然后我们就把安全边加入进去，然后更新这两个集合的数据。依次进行下去直到所有点进入。但是这样子的时间复杂度还是有点高，我们想一下还有上面优化的方法。怎样才能减少每次更新的时间呢？我们还有一个强大的助手STL。

STL中的优先队列提供了快捷的插入和修改，可以极大地优化时间。

下为示例与优化后的代码：

a> 首先选择A结点作为点集

b> 找A--B，A--D，A--G权值最小的点(B)，之后将其加入点集中

c> 找点集中跨越边最小的边，A--D,A--G,B--C,到D的权值最小，将其加入到点集中

d> 重复上述过程，A--G,D--G,D--E,B--C，到G的权值最小，将其加入到点集中

一直重复上述步骤直到找到的边数为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 << "首先加入点" << 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次加入点：%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 << "输入点数与边数" << endl;    cin >> n >> m;    tot = 0;    char a, b,ST;    int  x;    init(n);    cout << "输入边的数据：" << 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<<"最小生成树的最小权值和：" << queue_prim(ST, n);     return 0;}

NO.4

最小生成树之Krusal

     Prim算法是把我们要的树先假设为空，这是一种思路，接下来我们就来介绍下另外一种经典算法Krusal算法。

    我们首先假设 WN=(V,{E}) 是一个含有 n 个顶点的连通网，则按照克鲁斯卡尔算法构造最小生成树的过程为：先构造一个只含 n 个顶点，而边集为空的子图，若将该子图中各个顶点看成是各棵树上的根结点，则它是一个含有 n 棵树的一个森林。之后，从网的边集 E 中选取一条权值最小的边，若该条边的两个顶点分属不同的树，则将其加入子图，也就是说，将这两个顶点分别所在的两棵树合成一棵树；反之，若该条边的两个顶点已落在同一棵树上，则不可取，而应该取下一条权值最小的边再试之。依次类推，直至森林中只有一棵树，也即子图中含有 n-1条边为止。

    这种方法与prim算法有着一定的相似之处，但是Krusal算法可以同时存在多个树，但在prim算法中同时只能有两个树。

    与此同时我们也可以用STL进行优化操作.

#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 << "最小生成树的最小权值和：" << sum << endl;}int main(){  int n, m;  cout << "输入点数与边数" << endl;  cin >> n >> m;  int i;  sum = 0;  int a, b, c;  node k;  cout << "输入边的数据：" << 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;}