zhanyeye's learning log

(^～^)

0%

图的基础

Posted on Edited on In
邻接矩阵
基于 vector 邻接表

带权邻接表

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
#include <iostream>
#include <vector>
using namespace std;
struct node {
    int v, w;
};
vector<node> G[11];
void insert1(int u, int v, int w) {
    node temp;
    temp.v = v;
    temp.w = w;
    G[u].push_back(temp);
}
void insert2(int u, int v, int w) {
    insert1(u, v, w);
    insert1(v, u, w);
}
void input() {
    int m;
    cin >> m;
    for (int i = 0; i < m; i++) {
        int u, v, w;
        cin >> u >> v >> w;
        insert2(u, v, w);
    }
}

void output() {
    for (int i = 1; i <= 10; i++) {
        for (int j = 0; j < G[i].size(); j++) {
            cout << "(" << i << ", " << G[i][j].v << ", " << G[i][j].w << ")" << endl;
            
        }
    }
}
int main() {
    input();
    output();
    return 0;
}
基于 链表 的邻接表

由于vector的常数较大，对于某些时间限制较为严格的情景，使用vector存储邻接表会导致程序有超时的风险

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
const int N = 1000000;
const int M = 10000;
struct edge {
    int v, w;
    int next; //其实这里的next指向前驱
    edge() {}
    edge(int _v, int _w, int _next): v(_v), w(_w), next(_next) {} 
} e[M];

int head[N]; //head[i] 表示从点 i 
int cnt; //记录边的数量，来作为边的索引

void init() {
    memset(head, -1, sizeof head); //开始链表为空，头指针都初始化为 -1
    cnt = 0;
}

// 插入单向边
void insert(int u, int v, int w) {  
    e[cnt] = edge(v, w, head[u]); //新建一个终点为 v, 权值为 w 的边，插入到表示 u 的链表尾部
    head[u] = cnt; //将点 u 的 head指针移向后移一位，即刚刚插入的那个节点
    cnt++; 
}

// 插入双向边
void insert2(int u, int v, int w) { 
    insert(u, v, w);
    insert(v, u, w);
}

// 输出整张图中的所有边: !注意：输出的顺序和插入的顺序是相反的
void output(int n) { 
    for (int i = 0; i < n; i++) {
        cout << i << " : ";
        for (int j = head[i]; ~j; j = e[j].next) { // 遍历从 i 连出的所有边
            cout << "-> <[" << e[j].v << "]," << e[j].w << ">";
        }
        cout << endl;
    }
}
练习
关系查询

输入 n 对朋友关系，朋友关系是相互的。a 是 b 的朋友，b 也是 a 的朋友。（无向图）
然后有 m 次查询，每次查询询问 a 和 b 是否是朋友。
输入格式
第一行输入一个整数 n*(1≤n≤100)。
接下来 n 行，每行输入两个名字，表示一对朋友关系。
接下来一行输入一个整数 m(1≤m*≤100)，表示 m 个查询。
接下来 m 行，每行输入两个名字，表示一次查询。
输入中的名字只包含大小写字母，长度不超过 20。
输出格式
对于每次查询，如果他们是朋友，输出一行"Yes"，否则输出一行"No"。
样例输入

1
2
3
4
5
6
7
8
9
10
5
Mary Tom
Islands Barty
Andy Amy
Islands Amy
Tom Mary
3
Amy Andy
Islands Tom
Islands Barty

样例输出

1
2
3
Yes
No
Yes
  • 设置一个全局序号
  • 用映射表将string 应设为 int
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
#include <iostream>
#include <map>
#include <string>
using namespace std;

bool G[105][105];

int ids; //全局序号

map<string, int> mp;

int getId(string str) {
    if (mp.count(str)) {
        return mp[str];
    } else {
        mp[str] = ++ids;
        return ids;
    }
}

int main() {
    int n, m;
    
    ids = 0;
    cin >> n;
    while (n--) {
        string a, b;
        cin >> a >> b;
        int x = getId(a);
        int y = getId(b);
        G[x][y] = true;
        G[y][x] = true;
    }
    cin >> m;
    while (m--) {
        string a, b;
        cin >> a >> b;
        int x = getId(a);
        int y = getId(b);
        if (G[x][y]) {
            cout << "Yes" << endl;
        } else {
            cout << "No" << endl;
        }
    }
}
葱头君的旅行

蒜头君所在的城市可以抽象成为一个有 n*(1≤n≤20000) 个点和 m*(1≤m≤50000) 条无向边的地图。

蒜头君住在 11 号点，他想进行一次环城市旅游。他从 1 点出发，每次沿着和 1 点相连的边中最短的边到下一个城市（如果有很多个最短的边，选择编号最小的走），到达下一个城市以后，还是沿着和这个城市相连的最短边走到下一个点（如果有很多个最短的边，选择编号最小的走），一直这样走下去，直到要走到一个已经走过的，就结束这次旅行。

输入格式

输入第一行两个整数 n，m。

接下来 m 行，每行输入三个整数 u*,v(1≤u,v≤n,u!=v)，w*(1≤w≤10^6)，表示有一条连接 u 和 v 长度为 w 的无向边。

输出格式

输出一行若干个整数，依次表示蒜头君旅行经过的点，每两个数中间用一个空格隔开。

样例输入

1
2
3
4
5
4 4
3 4 4
4 2 5
2 1 7
4 1 5

样例输出

1
1 4 3
  • 遍历点的邻接点，找到权值最小的那一个
  • 设置一个bool数组vis 标记点是否被访问过
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
#include <iostream>
#include <vector>
using namespace std;

struct node {
    int v, w;
    node(int _v, int _w):v(_v), w(_w) {}
};

vector<node> G[20000];
bool vis[20000];

void insert(int u, int v, int w) {
    G[u].push_back(node(v, w));
    G[v].push_back(node(u, w));
}

void func(int v) {

    vis[v] = true;
    int next = 0;
    node min_node = G[v][0];
    for (int i = 0; i < G[v].size(); i++) { //找到一条最小的路径
        if (G[v][i].w < min_node.w) {
            min_node = G[v][i];
            next = i;
        }
    }
    if (vis[G[v][next].v]) {
        cout << v << endl;
        return;
    } else {
        cout << v << " ";
    }
    func(G[v][next].v);
}

int main() {
    int n, m;
    cin >> n >> m;
    while (m--) {
        int u, v, w;
        cin >> u >> v >> w;
        insert(u, v, w);
    }
    func(1);
    return 0;
}
完全图判断

输入一个无向图，判断这个图是不是一个完全图。

输入格式

输入第一行两个整数 n(1≤n≤100) 和 m(1≤m≤20000)，表示输入点数和边数。

接下来 m 行，每行输入两个整数 u*,v(1≤u,v≤*n)，表示 u 和 v 之前有一条无向边。

输入中不存在自己到自己的边，但是可能会有重复的边。

输出格式

如果输入的图是一个完全图，输出"Yes"，否则输出"No"。

  • 无向图是完全图时有 n*(n-1)/2条边
  • 无向图的边(u, v) 和 (v, u) 是一样，所以插入集合前固定大小顺序
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
#include <iostream>
#include <set>
using namespace std;

set<pair<int, int> > st;

void swap(int &a, int &b) {
    int tmp;
    tmp = a;
    a = b;
    b = tmp;
}

int main() {
    int n, m;
    cin >> n >> m;
    while (m--) {
        int u, v;
        cin >> u >> v;
        if (u > v) {
            swap(u, v);
        }
        st.insert(make_pair(u, v));
    }
    if (st.size() == n * (n - 1) / 2) {
        cout << "Yes" << endl;
    } else {
        cout << "No" << endl;
    }
    return 0;
}