SDUT《数据结构与算法》专题训练6 图论

最近真的是比较忙，考试...就不说了，现在还要参加Robomaster校赛，之前网站我负责的的辅导员招聘系统的一部分也要提前，有时间还要学习参与微信、QQ小程序开发......干货肯定会有，再等等吧，最晚最晚寒假之前一定更QAQ

数据结构实验之图论一：基于邻接矩阵的广度优先搜索遍历

Time Limit: 1000 ms Memory Limit: 65536 KiB

Problem Description

给定一个无向连通图，顶点编号从0到n-1，用广度优先搜索(BFS)遍历，输出从某个顶点出发的遍历序列。(同一个结点的同层邻接点，节点编号小的优先遍历）

Input

输入第一行为整数n（0< n <100），表示数据的组数。
对于每组数据，第一行是三个整数k，m，t（0＜k＜100，0＜m＜(k-1)*k/2，0＜ t＜k），表示有m条边，k个顶点，t为遍历的起始顶点。
下面的m行，每行是空格隔开的两个整数u，v，表示一条连接u，v顶点的无向边。

Output

输出有n行，对应n组输出，每行为用空格隔开的k个整数，对应一组数据，表示BFS的遍历结果。

Sample Input

Sample Output

0 3 4 2 5 1

Reference Code

#include <stdio.h>
#include <string.h>

int rel[101][101];
int visit[101];
int answer[101];
int k, m, t;
int a, b;
void BFS(int i)
{
    a++;
    if (i == t && visit[t] == 0)
    {
        answer[b++] = t;
        visit[t] = 1;
    }
    for (int j = 0; j <= k - 1; j++)
    {
        if (rel[i][j] == 1 && visit[j] == 0)
        {
            answer[b++] = j;
            visit[j] = 1;
        }
    }
    if (a <= b)
    {
        BFS(answer[a]);
    }
}
int main()
{
    int n;
    scanf("%d", &n);
    while (n--)
    {
        a = 0, b = 0;
        memset(visit, 0, sizeof(visit));
        memset(rel, 0, sizeof(rel));
        scanf("%d %d %d", &k, &m, &t);
        int i;
        int temp1, temp2;
        for (i = 1; i <= m; i++)
        {
            scanf("%d %d", &temp1, &temp2);
            rel[temp1][temp2] = 1;
            rel[temp2][temp1] = 1;
        }
        BFS(t);
        for (i = 0; i < b; i++)
        {
            if (i != k - 1)
            {
                printf("%d ", answer[i]);
            }
            else
            {
                printf("%d\n", answer[i]);
            }
        }
    }
    return 0;
}

数据结构实验之图论二：图的深度遍历

Time Limit: 1000 ms Memory Limit: 65536 KiB

Problem Description

请定一个无向图，顶点编号从0到n-1，用深度优先搜索(DFS)，遍历并输出。遍历时，先遍历节点编号小的。

Input

输入第一行为整数n（0 < n < 100），表示数据的组数。对于每组数据，第一行是两个整数k,m（0 ＜ k ＜ 100，0 ＜ m ＜ k*k），表示有m条边，k个顶点。下面的m行，每行是空格隔开的两个整数u，v，表示一条连接u，v顶点的无向边。

Output

输出有n行，对应n组输出，每行为用空格隔开的k个整数，对应一组数据，表示DFS的遍历结果。

Sample Input

Sample Output

0 1 2 3

Reference Code

#include <stdio.h>
#include <stdlib.h>
#include <string.h>

int rel[101][101], vis[101];
int k, m;
void Dfs(int t)
{
    int i;
    vis[t] = 1;
    for (i = 0; i < k; i++)
    {
        if (!vis[i] && rel[t][i])
        {
            printf(" %d", i);
            Dfs(i);
        }
    }
}

int main()
{
    int n;
    scanf("%d", &n);
    while (n--)
    {
        memset(rel, 0, sizeof(rel));
        memset(vis, 0, sizeof(vis));
        scanf("%d %d", &k, &m);
        while (m--)
        {
            int i, j;
            scanf("%d %d", &i, &j);
            rel[i][j] = rel[j][i] = 1;
        }
        printf("0");
        Dfs(0);
        printf("\n");
    }
}

数据结构实验之图论三：判断可达性

Time Limit: 1000 ms Memory Limit: 65536 KiB

Problem Description

在古老的魔兽传说中，有两个军团，一个叫天灾，一个叫近卫。在他们所在的地域，有n个隘口，编号为1..n，某些隘口之间是有通道连接的。其中近卫军团在1号隘口，天灾军团在n号隘口。某一天，天灾军团的领袖巫妖王决定派兵攻打近卫军团，天灾军团的部队如此庞大，甚至可以填江过河。但是巫妖王不想付出不必要的代价，他想知道在不修建任何通道的前提下，部队是否可以通过隘口及其相关通道到达近卫军团展开攻击。由于n的值比较大（n<=1000），于是巫妖王找到了擅长编程的你 =_=，请你帮他解决这个问题，否则就把你吃掉变成他的魔法。为了拯救自己，赶紧想办法吧。

Input

输入包含多组，每组格式如下。

第一行包含两个整数n,m（分别代表n个隘口，这些隘口之间有m个通道）。

下面m行每行包含两个整数a，b；表示从a出发有一条通道到达b隘口（注意：通道是单向的）。

Output

如果天灾军团可以不修建任何通道就到达1号隘口，那么输出YES，否则输出NO。

Sample Input

Sample Output

NO
YES

Reference Code

#include <stdio.h>
#include <stdlib.h>
#include <string.h>
int n, m;
int map[1001][1001];
int vis[1001];

void Dfs(int t)
{
    int i = 0;
    vis[t] = 1;
    for (i = 0; i < n; i++)
    {
        if (map[t][i] == 1 && vis[i] == 0)
        {
            map[t][i] = 0;
            Dfs(i);
        }
    }
}

int main()
{
    int k;
    int i, j;
    while (~scanf("%d %d", &n, &m))
    {
        memset(map, 0, sizeof(map));
        memset(vis, 0, sizeof(vis));
        for (k = 0; k < m; k++)
        {
            scanf("%d %d", &i, &j);
            map[i][j] = 1;
        }
        Dfs(n);
        if (vis[1] == 1)
            printf("YES\n");
        else
            printf("NO\n");
    }
    return 0;
}

数据结构实验之图论四：迷宫探索

Time Limit: 1000 ms Memory Limit: 65536 KiB

Problem Description

有一个地下迷宫，它的通道都是直的，而通道所有交叉点(包括通道的端点)上都有一盏灯和一个开关；请问如何从某个起点开始在迷宫中点亮所有的灯并回到起点？

Input

连续T组数据输入，每组数据第一行给出三个正整数，分别表示地下迷宫的结点数N(1 < N <= 1000)、边数M(M <= 3000)和起始结点编号S，随后M行对应M条边，每行给出一对正整数，表示一条边相关联的两个顶点的编号。

Output

若可以点亮所有结点的灯，则输出从S开始并以S结束的序列，序列中相邻的顶点一定有边，否则只输出部分点亮的灯的结点序列，最后输出0，表示此迷宫不是连通图。
访问顶点时约定以编号小的结点优先的次序访问，点亮所有可以点亮的灯后，以原路返回的方式回到起点。

Sample Input

Sample Output

1 2 3 4 5 6 5 4 3 2 1

Reference Code

#include <stdio.h>
#include <stdlib.h>
#include <string.h>

int map[1005][1005];
int visit[1005];
int ans[2005];
int n, m, o, k;

void dfs(int i)
{
    visit[i] = 1;
    ans[k++] = i;
    int j;
    for (j = 1; j <= n; j++)
    {
        if (visit[j] == 0 && map[i][j] == 1)
        {
            visit[j] = 1;
            dfs(j);
            ans[k++] = i;
        }
    }
}

int main()
{
    int t;
    scanf("%d", &t);
    while (t--)
    {
        int u, v, i;
        k = 0;
        memset(map, 0, sizeof(map));
        memset(visit, 0, sizeof(visit));
        scanf("%d %d %d", &n, &m, &o);
        for (i = 1; i <= m; i++)
        {
            scanf("%d %d", &u, &v);
            map[u][v] = map[v][u] = 1;
        }
        dfs(o);
        for (i = 0; i < k; i++)
        {
            if (i != k - 1)
                printf("%d ", ans[i]);
            else
                printf("%d", ans[i]);
        }
        if (k != n * 2 - 1)
            printf(" 0");
        printf("\n");
    }
    return 0;
}

数据结构实验之图论五：从起始点到目标点的最短步数（BFS）

Time Limit: 1000 ms Memory Limit: 65536 KiB

Problem Description

在古老的魔兽传说中，有两个军团，一个叫天灾，一个叫近卫。在他们所在的地域，有n个隘口，编号为1..n，某些隘口之间是有通道连接的。其中近卫军团在1号隘口，天灾军团在n号隘口。某一天，天灾军团的领袖巫妖王决定派兵攻打近卫军团，天灾军团的部队如此庞大，甚至可以填江过河。但是巫妖王不想付出不必要的代价，他想知道在不修建任何通道的前提下，部队是否可以通过隘口及其相关通道到达近卫军团展开攻击；如果可以的话，最少需要经过多少通道。由于n的值比较大（n<=1000），于是巫妖王找到了擅长编程的你 =_=，请你帮他解决这个问题，否则就把你吃掉变成他的魔法。为了拯救自己，赶紧想办法吧。

Input

输入包含多组，每组格式如下。

第一行包含两个整数n,m（分别代表n个隘口，这些隘口之间有m个通道）。

下面m行每行包含两个整数a，b；表示从a出发有一条通道到达b隘口（注意：通道是单向的）。

Output

如果天灾军团可以不修建任何通道就到达1号隘口，那么输出最少经过多少通道，否则输出NO。

Sample Input

Sample Output

NO
1

Refrence Code

#include <stdio.h>
#include <stdlib.h>
#include <string.h>
int map[1000][1000], mark[1000];
int n, m;
int num[1000];
void DFS(int x)
{
    int i, t;
    int p[1000];
    int in = 0, out = 0;
    p[in++] = x;
    mark[x] = 1;
    for (i = 1; i <= n; i++)
    {
        num[i] = 10000;
    }
    num[x] = 0;
    while (in > out)
    {
        t = p[out++];
        for (i = 1; i <= n; i++)
        {
            if (map[t][i] == 1 && mark[i] == 0)
            {
                mark[i] = 1;
                p[in++] = i;
                num[i] = num[t] + 1;
            }
        }
    }
    if (num[1] == 10000)
        printf("NO\n");
    else
        printf("%d\n", num[1]);
}

int main()
{
    while (scanf("%d %d", &n, &m) != EOF)
    {
        memset(map, 0, sizeof(map));
        memset(mark, 0, sizeof(mark));
        int i;
        for (i = 1; i <= m; i++)
        {
            int u, v;
            scanf("%d %d", &u, &v);
            map[u][v] = 1;
        }
        DFS(n);
    }
    return 0;
}

数据结构实验之图论六：村村通公路

Time Limit: 1000 ms Memory Limit: 65536 KiB

Problem Description

当前农村公路建设正如火如荼的展开，某乡镇政府决定实现村村通公路，工程师现有各个村落之间的原始道路统计数据表，表中列出了各村之间可以建设公路的若干条道路的成本，你的任务是根据给出的数据表，求使得每个村都有公路连通所需要的最低成本。

Input

连续多组数据输入，每组数据包括村落数目N(N <= 1000)和可供选择的道路数目M(M <= 3000)，随后M行对应M条道路，每行给出3个正整数，分别是该条道路直接连通的两个村庄的编号和修建该道路的预算成本，村庄从1～N编号。

Output

输出使每个村庄都有公路连通所需要的最低成本，如果输入数据不能使所有村庄畅通，则输出-1，表示有些村庄之间没有路连通。

Sample Input

Sample Output

Reference Code

#include <stdio.h>
#include <stdlib.h>
#include <string.h>

#define max 0x3f3f3f3f
int map[1000][1000];
int lowcost[1000];
int vis[1000];
int vex;
int money;
int k;

void zxtree(int n)
{
    int i, j;
    vex = 0;
    vis[1] = 1;
    money = 0;
    for (i = 1; i <= n; i++)
    {
        lowcost[i] = map[i][1];
    }
    for (i = 1; i < n; i++)
    {
        k = max;
        for (j = 1; j <= n; j++)
        {
            if (!vis[j] && k > lowcost[j])
            {
                k = lowcost[j];
                vex = j;
            }
        }
        for (j = 1; j <= n; j++)
        {
            if (!vis[j] && lowcost[j] > map[j][vex])
                lowcost[j] = map[j][vex];
        }
        vis[vex] = 1;
        money = money + k;
        if (k == max)
            money = -1;
    }
    printf("%d\n", money);
}

int main()
{
    int i, j;
    int n, m;
    int a, b, c;
    while (~scanf("%d%d", &n, &m))
    {
        memset(vis, 0, sizeof(vis));
        for (i = 1; i <= n; i++)
        {
            for (j = 1; j <= n; j++)
            {
                if (i == j)
                    map[i][j] = 0;
                else
                    map[i][j] = max;
            }
        }
        for (i = 1; i <= m; i++)
        {
            scanf("%d%d%d", &a, &b, &c);
            if (map[a][b] > c)
                map[a][b] = map[b][a] = c;
        }
        zxtree(n);
    }
    return 0;
}

数据结构实验之图论七：驴友计划

Time Limit: 1000 ms Memory Limit: 65536 KiB

Problem Description

做为一个资深驴友，小新有一张珍藏的自驾游线路图，图上详细的标注了全国各个城市之间的高速公路距离和公路收费情况，现在请你编写一个程序，找出一条出发地到目的地之间的最短路径，如果有多条路径最短，则输出过路费最少的一条路径。

Input

连续T组数据输入，每组输入数据的第一行给出四个正整数N,M，s，d，其中N(2 <= N <= 500)是城市数目，城市编号从0～N-1，M是城市间高速公路的条数，s是出发地的城市编号，d是目的地的城市编号；随后M行，每行给出一条高速公路的信息，表示城市1、城市2、高速公路长度、收费额，中间以空格间隔，数字均为整数且不超过500，输入数据均保证有解。

Output

在同一行中输出路径长度和收费总额，数据间用空格间隔。

Sample Input

Sample Output

3 40

Refrence Code

#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#define max 0x3f3f3f3f

struct node
{
    int len;
    int money;
} road[501][501];
int main()
{
    int t, i, j, k;
    int n, m, s, d, money, len, u, v;
    scanf("%d", &t);
    while (t--)
    {
        scanf("%d %d %d %d", &n, &m, &s, &d);
        for (i = 0; i < n; i++)
        {
            for (j = 0; j < n; j++)
            {
                if (i == j)
                {
                    road[i][j].len = 0;
                    road[i][j].money = 0;
                }
                else
                {
                    road[i][j].len = max;
                    road[i][j].money = max;
                }
            }
        }
        for (i = 1; i <= m; i++)
        {
            scanf("%d %d %d %d", &u, &v, &len, &money);
            road[u][v].len = road[v][u].len = len;
            road[u][v].money = road[v][u].money = money;
        }
        for (k = 0; k < n; k++)
        {
            for (i = 0; i < n; i++)
            {
                for (j = 0; j < n; j++)
                {
                    if (road[i][j].len > road[i][k].len + road[k][j].len)
                    {
                        road[i][j].len = road[i][k].len + road[k][j].len;
                        road[i][j].money = road[i][k].money + road[k][j].money;
                    }
                    else if (road[i][j].len == road[i][k].len + road[k][j].len)
                    {
                        if (road[i][j].money > road[i][k].money + road[k][j].money)
                        {
                            road[i][j].money = road[i][k].money + road[k][j].money;
                        }
                    }
                }
            }
        }
        printf("%d %d\n", road[s][d].len, road[s][d].money);
    }
    return 0;
}

数据结构实验之图论八：欧拉回路

Time Limit: 1000 ms Memory Limit: 65536 KiB

Problem Description

在哥尼斯堡的一个公园里，有七座桥将普雷格尔河中两个岛及岛与河岸连接起来。

能否走过这样的七座桥，并且每桥只走一次？瑞士数学家欧拉最终解决了这个问题并由此创立了拓扑学。欧拉通过对七桥问题的研究，不仅圆满地回答了哥尼斯堡七桥问题，并证明了更为广泛的有关一笔画的三条结论，人们通常称之为欧拉定理。对于一个连通图，通常把从某结点出发一笔画成所经过的路线叫做欧拉路。人们又通常把一笔画成回到出发点的欧拉路叫做欧拉回路。具有欧拉回路的图叫做欧拉图。

你的任务是：对于给定的一组无向图数据，判断其是否成其为欧拉图？

Input

连续T组数据输入，每组数据第一行给出两个正整数，分别表示结点数目N(1 < N <= 1000)和边数M；随后M行对应M条边，每行给出两个正整数，分别表示该边连通的两个结点的编号，结点从1～N编号。

Output

若为欧拉图输出1，否则输出0。

Sample Input

Sample Output

Hint

如果无向图连通并且所有结点的度都是偶数，则存在欧拉回路，否则不存在。

Rrfrence Code

#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#define INF 0x3f3f3f3f

int map[1001][1001];
int vis[1001];
int de[1001];
int n, m;
int sum;

void dfs(int i)
{
    vis[i] = 1;
    int j;
    sum++;
    for (j = 1; j <= n; j++)
    {
        if (vis[j] == 0 && map[i][j] == 1)
        {
            vis[j] = 1;
            dfs(j);
        }
    }
}
int main()
{
    int T;
    scanf("%d", &T);
    while (T--)
    {
        sum = 0;
        int o;
        memset(map, 0, sizeof(map));
        memset(vis, 0, sizeof(vis));
        memset(de, 0, sizeof(de));
        scanf("%d %d", &n, &m);
        int u, v;
        int i;
        for (i = 1; i <= m; i++)
        {
            scanf("%d %d", &u, &v);
            map[u][v] = map[v][u] = 1;
            de[u]++;
            de[v]++;
            if (i == 1)
                o = u;
        }
        dfs(o);
        int k = 0;
        for (i = 0; i <= n; i++)
        {
            if (de[i] % 2 != 0)
            {
                k++;
                break;
            }
        }
        if (k == 0 && sum == n)
            printf("1\n");
        else
            printf("0\n");
    }
    return 0;
}

数据结构实验之图论九：最小生成树

Time Limit: 1000 ms Memory Limit: 65536 KiB

Problem Description

有n个城市，其中有些城市之间可以修建公路，修建不同的公路费用是不同的。现在我们想知道，最少花多少钱修公路可以将所有的城市连在一起，使在任意一城市出发，可以到达其他任意的城市。

Input

输入包含多组数据，格式如下。

第一行包括两个整数n m，代表城市个数和可以修建的公路个数。(n <= 100， m <=10000)

剩下m行每行3个正整数a b c，代表城市a 和城市b之间可以修建一条公路，代价为c。

Output

每组输出占一行，仅输出最小花费。

Sample Input

Sample Output

2
0

Reference Code

#include <stdio.h>
#include <string.h>
#define INF 0x3f3f3f3f

int map[1001][1001];
int vis[1001];
int dis[1001];
int n, m, sum;

void prim(int n)
{
    int i, j, k;
    for (i = 1; i <= n; i++)
    {
        dis[i] = map[1][i];
    }
    vis[1] = 1;
    for (i = 1; i < n; i++)
    {
        int mi = INF;
        int u;
        for (j = 1; j <= n; j++)
        {
            if (vis[j] == 0 && dis[j] < mi)
            {
                u = j;
                mi = dis[j];
            }
        }
        if (mi >= INF)
            break;
        vis[u] = 1;
        sum += mi;
        for (k = 1; k <= n; k++)
        {
            if (vis[k] == 0 && map[u][k] < dis[k])
            {
                dis[k] = map[u][k];
            }
        }
    }
}
int main()
{
    int a, b, c;
    while (scanf("%d %d", &n, &m) != EOF)
    {
        int i, j;
        sum = 0;
        memset(vis, 0, sizeof(vis));
        memset(dis, 0, sizeof(dis));
        for (i = 1; i <= n; i++)
        {
            for (j = 1; j <= n; j++)
            {
                if (i == j)
                    map[i][j] = 0;
                else
                    map[i][j] = INF;
            }
        }
        for (i = 1; i <= m; i++)
        {
            scanf("%d %d %d", &a, &b, &c);
            if (c < map[a][b])
                map[a][b] = map[b][a] = c;
        }
        prim(n);
        printf("%d\n", sum);
    }
    return 0;
}

数据结构实验之图论十：判断给定图是否存在合法拓扑序列

Time Limit: 1000 ms Memory Limit: 65536 KiB

Problem Description

给定一个有向图，判断该有向图是否存在一个合法的拓扑序列。

Input

输入包含多组，每组格式如下。

第一行包含两个整数n，m，分别代表该有向图的顶点数和边数。(n<=10)

后面m行每行两个整数a b，表示从a到b有一条有向边。

Output

若给定有向图存在合法拓扑序列，则输出YES；否则输出NO。

Sample Input

Sample Output

YES
NO

Reference Code

#include <stdio.h>
#include <stdlib.h>
#include <string.h>
int map[1000][1000], vis[1000], d[1000];

int main()
{
    int n, m, a, b, i, j;
    while (~scanf("%d %d", &n, &m))
    {
        memset(map, 0, sizeof(map));
        memset(vis, 0, sizeof(vis));
        memset(d, 0, sizeof(d));
        while (m--)
        {
            scanf("%d %d", &a, &b);
            map[a][b] = 1;
            d[b]++;
        }
        int count = n;
        for (i = 1; i <= n; i++)
        {
            if (d[i] == 0 && vis[i] == 0)
            {
                count--;
                vis[i] = 1;
                for (j = 1; j <= n; j++)
                {
                    if (map[i][j] == 1)
                        d[j]--;
                }
            }
        }
        if (count == 0)
            printf("YES\n");
        else
            printf("NO\n");
    }
    return 0;
}