机试-图论

预备知识

我们可以用标准库(STL)中的标准模版 std::vector 来使用邻接链表。

首先定义一个结构体，包括邻接结点和边权值

struct Edge{
    int nextNode;
    int cost;
};

为每个结点都建立一个单链表来保存结点信息，使用 vector 来模拟这些单链表。

vector<Edge> edge[N];

该语句建立了一个大小为 N 的数组，而数组中保存的元素就是 vector 对象，edge[i] 表示结点 i 的单链表。

为单链表添加和删除信息：

for (int i=0;i<N;i++){
    edge[i].clear();    //清空其单链表
}

Edge tmp;
tmp.nextNode = 3;
tmp.cost = 38;
edge[1].push_back(tmp);        //添加信息调用 push_back(Edge)

查询某个结点的所有邻接信息：

for (int i=0;i<edge[2].size();i++){
    //对 edge[2] 进行遍历，即对所有与结点2相邻的边进行遍历，edge[2].size()表示其大小
    int nextNode = edge[2][i].nextNode;
    int cost = edge[2][i].cost;
}

删除某些边：

//删除结点1的单链表中edge[1][i]的某些边信息
edge[1].erase(edge[1].begin()+i, edge[1].begin()+i+1)

并查集

并查集用来表示集合信息，用以实现如确定某个集合含有哪些元素，判断两个元素是否在同一个集合中等问题。

用一颗树上的结点来表示在一个集合中的数字，要判断两个数字是否在一个集合中，只需判断它们是否在一棵树中。我们定义一个数组，用双亲表示法来表示各棵树：

int Tree[N]

为了查找结点 x 所在树的根结点，定义以下函数：

int findRoot(int x){
    if (Tree[x] == -1)
        return x;
    else
        return findRoot(Tree[x]);
}

若在查找过程中添加路径压缩的优化：

int findRoot(int x){
    if (Tree[x] == -1)
        return x;
    else{
        tmp = findRoot(Tree[x]);
        Tree[x] = tmp;
        return tmp;
    }
}

• 例4.5 畅通工程

目标是使全省任意两个城镇都可以实现交通，求最少还需要建设多少条道路。该问题可以抽象成在一个图上查找连通分量的个数。

// 输入 第一行：城镇数目 N，道路数目 M；
// 随后的 M 行对应 M 条道路

#include<stdio.h>
using namespace std;
#define N 1000
int Tree[N];
int findRoot(int x){
    // 查找某个节点所在的根结点
    if (Tree[x] == -1){ 
        return x;
    }
    else {
        int tmp = findRoot(Tree[x]);
        Tree[x] = tmp;
        return tmp;
    }
}

int main(){
    int n,m;
    while (scanf("%d%d", &n, &m) != EOF){
        for (int i=1;i<=n;i++){
            Tree[i] = -1;
        }
        while (m--!=0){
            int a, b;
            // 读入边信息
            scanf("%d%d", &a, &b);
            a = findRoot(a);
            b = findRoot(b);
            if (a!=b)
                Tree[a] = b;
        }
        int ans = 0;
        for (int i=1;i<=n;i++){
            if (Tree[i] == -1)
                ans++;
        }
        printf("%d\n", ans-1);
    }
    return 0;
}

• 例4.15 More is better

在1000000个小朋友中，他们之间有 N 对好朋友，且朋友关系具有传递性，在这 N 对朋友关系中，要求我们找出一个最大的集合使得其中任意两人之间都是朋友，输出该最大人数。

#include<stdio.h>
using namespace std;
#define N 10000001

int Tree[N];
int sum[N];

int findRoot(int x){
    if (Tree[x] == -1)
        return x;
    else{
        int tmp = findRoot(Tree[x]);
        Tree[x] = tmp;
        return tmp;
    }
}

int main(){
    int n;
    while (scanf("%d", &n) != EOF){
        for (int i=1;i<N;i++){
            Tree[i] = -1;
            sum[i] = 1;
        }
        int a,b;
        while (n-- != 0){
            scanf("%d%d", &a,&b);
            a = findRoot(a);
            b = findRoot(b);
            if (a!=b){
                Tree[a] = b;
                sum[b] += sum[a];
            }
        }
        int ans = 1;
        for (int i=1;i<N;i++){
            if (Tree[i] == -1 && sum[i] > ans)
                ans = sum[i];
        }
        printf("%d\n", ans);
    }
    return 0;
}

最小生成树MST

在一个无向连通图中，若存在一个连通子图包含原图中的所有结点和部分边且不存在回路，那么我们称这个子图为原图的一颗生成树，在带权图中，所有生成树中边权的和最小的那颗被称为最小生成树。

在要求的连通图中，任意选择一些点属于集合A，剩余的点属于集合B，必定存在一颗最小生成树包含两个顶点分别属于集合A和集合B的边中权值最小的边。

• 例5.3 畅通工程

要求使任意两个村庄都可以实现公路交通，且公路总长度最短，计算最小的公路总长度。

//还是畅通工程
//在给定的道路中选取一些，使所有的城市直接或间接联通且使道路的总长度最短

#include<stdio.h>
#include<algorithm>
using namespace std;
#define N 101
int Tree[N];

int findRoot(int x){
    if (Tree[x] == -1)
        return x;
    else{
        int tmp = findRoot(Tree[x]);
        Tree[x] = tmp;
        return tmp;
    }
}

struct Edge
{
    // 边结构体
    int a,b;
    int cost;
    bool operator < (const Edge &A) const{
        return cost < A.cost;
    }
}edge[6000];

int main(){
    int n;
    while (scanf("%d", &n) != EOF && n != 0){
        for (int i=1;i<=(n-1)*n/2;i++){
            scanf("%d%d%d", &edge[i].a, &edge[i].b, &edge[i].cost);
        }
        sort(edge+1, edge+1+(n-1)*n/2);
        for(int i=1;i<=n;i++){
            Tree[i] = -1;
        }

        int ans = 0;
        for (int i=1;i<=(n-1)*n/2;i++){
            int a = findRoot(edge[i].a);
            int b = findRoot(edge[i].b);
            if (a!=b){
                // printf("%d %d\n", a, b);
                Tree[a] = b;
                ans += edge[i].cost;
            }
        }
        printf("%d\n", ans);
    }
    return 0;
}

• 例5.4 Freckles

平面上有若干个点，我们需要用一些线段来将这些点连接起来使任意两个点能够通过一系列的线段相连，求一种连接方式使所有线段的长度和最小，求该长度和。

#include<stdio.h>
#include<math.h>
#include<algorithm>

// 输入 N,表示 N 个坐标
// 输出连接这 N 个点的最短距离
using namespace std;
#define N 101
int Tree[N];
int findRoot(int x){
    if (Tree[x] == -1)
        return x;
    else{
        int tmp = findRoot(Tree[x]);
        Tree[x] = tmp;
        return tmp;
    }
}

struct Edge
{
    int a,b;
    double cost;
    bool operator < (const Edge &A) const{
        return cost < A.cost;
    }
}edge[6000];

struct Point
{
    double x,y;
    double getDistance(Point A){
        double tmp = (x - A.x)*(x - A.x) + (y - A.y)*(y - A.y);
        return sqrt(tmp);
    }
}list[101];

int main(){
    int n;
    while(scanf("%d", &n) != EOF){
        for (int i=1;i<=n;i++){
            scanf("%lf%lf", &list[i].x, &list[i].y);
        }
        int size = 0;
        for (int i=1;i<=n;i++){
            for (int j=i+1;j<=n;j++){
                edge[size].a = i;
                edge[size].b = j;
                edge[size].cost = list[i].getDistance(list[j]);
                size ++;
            }
        }
        sort(edge, edge+size);
        for (int i=1;i<=n;i++){
            Tree[i] = -1;
        }
        double ans = 0;
        for (int i=0;i<size;i++){
            int a = findRoot(edge[i].a);
            int b = findRoot(edge[i].b);
            if (a!=b){
                Tree[a] = b;
                ans += edge[i].cost;
            }
        }
        printf("%.2lf", ans);
    }
    return 0;
}

最短路径

• floyd算法：用邻接矩阵保存原图，若edge[ i ][ j ] 表示从结点i到结点j，中间只能经过编号小于 k 的点时的最短路径长度，我们可以由这些值确定当中间允许经过编号小于等于k的结点时，他们之间的最短路径长度。若新情况中允许出现在中间路径的结点新增了编号为k的结点，我们比较edge[ i ][ k ] + edge[ k ][ j ]与edge[ i ][ j ]的值，若前值较小，则该值代表了新情况中从结点i到结点j的最短路径长度，否则，新情况中该路径长度依旧保持不变。
• 算法：开始时edge[ i ][ j ]表示由结点i到结点j中间不经过任何结点时的最短距离，那么依次为中间允许经过的结点添加结点1，结点2，……，直到结点N，当添加完这些结点后，从结点i到结点j允许经过所有结点的最短路径长度就可以确定了。
• 例5.5 最短路：

// floyd 算法求最短路

#include<stdio.h>
int ans[101][101];

int main(){
    int n,m;
    while (scanf("%d%d", &m, &n) != EOF){
        if (n==0 && m==0)
            break;
        for (int i=1;i<=n;i++){
            for (int j=1;j<=n;j++){
                ans[i][j] = -1;
            }
            ans[i][i] = 0;
        }
        while (m--){
            int a,b,c;
            scanf("%d%d%d", &a, &b, &c);
            ans[a][b] = ans[b][a] = c;
        }

        for (int k=1;k<=n;k++){
            for (int i=1;i<=n;i++){
                for (int j=1;j<=n;j++){
                    if (ans[i][k] == -1 || ans[k][j] == -1)
                        continue;
                    if (ans[i][j] == -1 ||ans[i][k] + ans[k][j] < ans[i][j])
                        ans[i][j] = ans[i][k] + ans[k][j];
                }
            }
        }
        printf("%d\n", ans[1][n]);
    }
    return 0;
}

Floyd 解决的全源最短路问题。

• Dijkstra算法：求某个特定结点到其他所有结点的最短路径长度。设已经确定最短路径长度的结点集合为集合K，其中保存了最短路径长度最短的前m个结点，他们是p1,p2,….,pm，并已经得出他们的最短路径长度，那么第m+1近的结点与结点1的最短路径上的中间结点一定全部属于集合K。
• 用 dijkstra算法重写例4.5

// dijkstra 算法
#include<stdio.h>
#include<vector>
using namespace std;
struct E{
    // 邻接链表中的链表元素结构体
    int next;  // 代表直接相邻的节点
    int c;        //代表该边的权值
};

vector<E> edge[101];

bool mark[101];        // mark[j] 为 true 时表示结点 j 的最短路径长度已经得到，该结点已经加入集合 K
int dis[101];         //距离向量

int main(){
    int n,m;
    while (scanf("%d%d", &n, &m) != EOF){
        if (n==0 && m==0)
            break;
        for (int i=1;i<=n;i++){
            edge[i].clear();        //初始化邻接链表
        }
        while(m--){
            int a,b,c;
            scanf("%d%d%d", &a,&b,&c);
            E tmp;
            tmp.c = c;
            tmp.next = b;
            edge[a].push_back(tmp);
            tmp.next = a;
            edge[b].push_back(tmp);
        }
        for (int i=1;i<=n;i++){
            //初始化
            dis[i] = -1;
            mark[i] = false;
        }
        dis[1] = 0;
        mark[1] = true;
        int newP = 1;        //集合 K    中新加入的点为结点1
        for (int i=1;i<n;i++){
            for (int j=0;j<edge[newP].size();j++){
                int t = edge[newP][j].next;
                int c = edge[newP][j].c;
                // printf("%d %d\n", t,c);
                if (mark[t] == true)
                    continue;
                if (dis[t] == -1 || dis[t] > dis[newP] + c){
                    dis[t] = dis[newP] + c;
                    // printf("%d\n", dis[t]);
                }
            }
            int min = 123123123;
            for (int j=1;j<=n;j++){
                if (mark[j] == true)
                    continue;
                if (dis[j] == -1)
                    continue;
                if (dis[j] < min){
                    min = dis[j];
                    newP = j;
                }
            }
            mark[newP] = true;
            // dis[newP] = min;
        }
        printf("%d\n", dis[n]);
    }
    return 0;
}

拓扑排序

设一个有向无环图，拓扑排序指的是对于所有的边(U,V)，在该序列中结点U都排列在结点V之前，满足该要求的结点序列，被称为满足拓扑次序的序列。

所有有入度的结点均不可能排在第一个，选择一个入度为0的结点，作为序列的第一个结点，然后删去该结点，同时删去以该结点为弧尾的所有边得到一个新图，然后在新图上选择一个入度为0的结点，重复上述步骤，直到所有的结点和边都从原图中删去，若在所有结点尚未被删去时出现了找不到入度为0的结点的情况，则说明剩余结点形成一个环路。

• 例5.7 Legal or Not

输入群里的所有师徒关系，问是否存在非法的情况：A是B的师傅，B是C的师傅，但C又是A的师傅。

// legal or not
// 判断该图是否是有向无环图

#include<stdio.h>
#include<queue>
#include<vector>

using namespace std;
vector<int> edge[501];        //邻接链表
queue<int> Q;        //保存入度为 0 的结点的序列

int main(){
    int inDegree[501];        //统计每个结点的入度
    int n,m;
    while (scanf("%d%d", &n, &m) != EOF){
        if (n==0 && m==0)
            break;
        for (int i=0;i<n;i++){
            inDegree[i] = 0;
            edge[i].clear();
        }
        while (m--){
            int a,b;
            scanf("%d%d", &a, &b);
            inDegree[b]++;
            edge[a].push_back(b);
        }
        while (Q.empty() == false){
            Q.pop();
        }
        for (int i=0;i<n;i++){
            if (inDegree[i] == 0)
                Q.push(i);
        }
        int cnt;    //确定已经入度为 0 的结点
        while (Q.empty() == false){
            int nowP = Q.front();
            Q.pop();
            cnt++;
            for (int i=0;i<edge[nowP].size();i++){
                inDegree[edge[nowP][i]]--;
                if (inDegree[edge[nowP][i]] == 0)
                    Q.push(edge[nowP][i]);
            }
        }
        if (cnt == n)
            printf("YES\n");
        else
            printf("NO\n");
    } 
    return 0;
}