主要记录在学习图的基础所在练习题目的题集：

1.关系查询：

a.题目描述:

b.分析：
其实这一道题目是让我们查询一个无向图的两个顶点是否有边存在，因为a把b当做朋友，b也要把a当做朋友，所以我们可以把a，b看做图中的顶点，在无向图中a如果和b构成边则他们互相就是朋友了，这是必然的。
接下来我们要处理的是输入的数据是字符串，那么我们可以想到用hash或者map将字符串转成唯一的int整型来对应.
比如Mary Tom
mp[“Mary”] = 1;
mp[“Tom”] = 2;
那么我们将他们加入图中，无向图的G[1][2] = G[2][1] = 1，即代表是朋友，即可。

c.AC Code:

#include <iostream>
#include <map>
#include <cstdio>
#include <cstring>
using namespace std;

int G[500][500];
map<string, int> mp;
int id;

int find(string a) {
    if (mp.count(a) == 0) {
        mp[a] = ++id;
    } else {
        return mp[a];
    }
}

int main() {
    int n;
    cin >> n;
//    getchar();
    string s1, s2;
    for (int i = 0; i < n; i++) {
        cin >> s1 >> s2;
        int x = find(s1);
        int y = find(s2);
        G[x][y] = G[y][x] = 1;
    }
    int m;
    string a, b;
    cin >> m;
//    getchar();
    while (m --) {
        cin >> a >> b;
        if (G[find(a)][find(b)] == 1) printf("Yes\n");
        else printf("No\n");
    }
    return 0;
}

2.蒜头君的旅行：

a.问题描述：

b.算法分析：
这一道题目我们仔细看发现顶点数为2e4，那么如果我们使用邻接矩阵那么就要开一个二维2e4 * 2e4 = 4e8空间大小的矩阵，那么必然MLE（内存超限）,所以这里我们使用邻接表，也就是用Vector来存储，因为是带权图我们使用结构所以我们可以采用结构体存入Vector，然后我们先设定一个shortest,代表最短的无向边，再定义一个cur保存当前访问到哪一个顶点了，对每一个顶点访问过就是用一个visited的数组标记访问过，那么每次找到比shortest短的变更新最小长度即可，将答案保存到一个ans数组，最后输出即可。

c.AC Code:

#include <iostream>
#include <cstdio>
#include <vector>
#include <climits>
using namespace std;
const int maxn = 2e4 + 5;

struct node{
  	int v;
    int w;
    node(int vv, int ww) {
        v = vv;
        w = ww;
    }
};
vector<node> G[maxn];
bool visited[maxn];
int ans[maxn];
int shortest = INT_MAX;

int main() {
    int n, m, u, v, w;
    scanf("%d%d", &n, &m);
    while (m --) {
        scanf("%d%d%d", &u, &v, &w);
        G[u].push_back(node(v, w));
        G[v].push_back(node(u, w));
    }
/*    for (int i = 1; i <= n; i++) {
        for (int j = 0; j < G[i].size(); j++) {
            cout << i << " " << G[i][j].v << " " << G[i][j].w << endl;
        }
    }*/
    int cur = 1, tmp, cnt = 0;
    while (1) {
        if (visited[cur]) break;
        visited[cur] = true;
        ans[cnt++] = cur;
        for (int i = 0; i < G[cur].size(); i++) {
            if (G[cur][i].w < shortest) {
                shortest = G[cur][i].w;
                tmp = G[cur][i].v;
            }
        }
        cur = tmp;
    }
    
    for (int i = 0; i < cnt - 1; i++) {
        printf("%d ", ans[i]);
    }
    printf("%d\n", ans[cnt - 1]);
    return 0;
}

3.完全图的判定:

a.问题描述：

b.分析：
这道题目你只需要了解完全图的概念即可，并且题目所给点的数量较少直接用邻接矩阵存储即可，完全图大概就是说的是给定的每个顶点应该都存在一条对应的边，比如样例1
给定3个顶点，输入3条边
1 2 输入后，因为无向图必然存在2 1
2 3 – 3 2
3 1 – 1 3
那么必然是完全图，
而样例二由于没有存在顶点2到顶点3的边即不为完全图。
我们只要读入邻接矩阵后，在判断有没有G[i][j]的边不存在的，不存在即不为完全图。

c.AC Code:

#include <cstdio>
using namespace std;

int G[105][105];

int main() {
    int n, m, u, v;
    scanf("%d%d", &n, &m);
    bool flag = true;
	while (m --) {
        scanf("%d%d", &u, &v);
        G[u][v] = G[v][u] = 1;
    }
    for (int i = 1; i <= n; i++) {
        for (int j = i + 1; j <= n; j++) {
            if (G[i][j] != 1) flag = false;
        }
    }
    if (flag) printf("Yes\n");
    else printf("No\n");
    return 0;
}

4.稀疏图的判定：

a.问题描述：

b.分析：
这道题目因为给定的顶点数不是很大，还是用邻接矩阵来存储，然后我们只要注意可能有构成G[1][1]类似这样的从自己到自己这样的边，但不算边数，然后我们去遍历矩阵统计有多少边然后与10 * n(顶点数)比较即可。

c.AC Code:

#include <cstdio>
using namespace std;

int G[105][105];
int ans;

int main() {
    int n;
    scanf("%d", &n);
    for (int i = 1; i <= n; i++) {
        for (int j = 1; j <= n; j++) {
            scanf("%d", &G[i][j]);
            if (i != j && G[i][j] == 1) ans++; 
        }
    }
    if (ans <= 10 * n) printf("Yes\n");
    else printf("No\n");
    return 0;
}

5.朋友的距离：

a.问题描述：

b.分析：
这道题目其实还是一个邻接矩阵的题目，我们只要在读入邻接矩阵后进行一个max比较赋值即可，注意邻接矩阵是无向图的，我们必须要给G[u][v] = G[v][u] = max(G[u][v], G[v][u])即可。

c.AC Code:

#include <cstdio>
#include <algorithm>
using namespace std;

int G[105][105];

int main() {
    int n;
    scanf("%d", &n);
    for (int i = 1; i <= n; i++) {
        for (int j = 1; j <= n; j++) {
            scanf("%d", &G[i][j]);
        }
    }
    for (int i = 1; i <= n; i++) {
        for (int j = 1; j <= n; j++) {
           	G[i][j] = G[j][i] = max(G[i][j], G[j][i]);
        }
    }
    for (int i = 1; i <= n; i++) {
        for (int j = 1; j < n; j++) {
           	printf("%d ", G[i][j]);
        }
        printf("%d\n", G[i][n]);
    }
    return 0;
}

6.邻接表的使用：

a.问题描述：

b.算法:
这道题目有两个注意点，用vector存储图后，我们发现他需要将数据倒序输出，然后就是如果某一个点没有边不需要空格在换行，直接换行，注意这两点也就没什么难度了。

c.AC Code:

#include <cstdio>
#include <vector>
using namespace std;

vector<int> G[105];

int main() {
    int n, m, a, x, y;
    scanf("%d%d", &n, &m);
    for (int i = 0; i < m; i++) {
        scanf("%d%d%d", &a, &x, &y);
        if (a == 0) G[x].push_back(y);
        else {
            G[x].push_back(y);
            G[y].push_back(x);
        }
    }
    for (int i = 0; i < n; i++) {
        if (G[i].size() == 0) {
            printf("%d:\n", i);
        } else {
            printf("%d: ", i);
            for (int j = G[i].size() - 1; j > 0; j--) {
            	printf("%d ", G[i][j]);
        	}
        	printf("%d\n", G[i][0]);
        }
    }
    return 0;
}

欢迎关注：
ly’s Blog