C++U5-07-图的概念与存储-526互联

上节课作业分析讲解视频

链接：https://pan.baidu.com/s/1vuE1zhm9tKKBHrvJbBpyPA?pwd=m708
提取码：m708

学习目标

引入

图的概念

无向图

有向图

带权图

自环与重边

简单图与多重图

无向完全图与有向完全图

稠密图与稀疏图

图的简单性质

度数：入度与出度

路径-简单路径

简单环路

无环图

连通性

连通分量

图的邻接矩阵

有向图

带权图

无向带权图存储1

【算法分析】
可以用邻接矩阵存图，并将所有的距离初始化为无穷大，然后去更新每条边的权值。注意会存在重边。

【参考代码】
#include <bits/stdc++.h>
using namespace std;

int MAP[109][109];
int main() {
    memset(MAP, 0x3f, sizeof(MAP));
    int n, m, q;
    cin >> n >> m >> q;
    for (int i = 0; i < m; i++) {
        int x, y, len;
        cin >> x >> y >> len;
        MAP[x][y] = MAP[y][x] = min(MAP[x][y], len);
    }
    while (q--) {
        int x, y, len;
        cin >> x >> y >> len;
        if (MAP[x][y] > len) {
            cout << "Accepted" << '\n';
        }
        else {
            cout << "Cancel" << '\n';
        }
    }
    return 0;
}

View Code

有向带权图2

【算法分析】
可以用邻接矩阵存图，在每次询问的时候从小到大遍历每个结点。

【参考代码】
#include <bits/stdc++.h>
using namespace std;

int MAP[109][109];
int main() {
    int n, m, q;
    cin >> n >> m >> q;
    for (int i = 0; i < m; i++) {
        int x, y, len;
        cin >> x >> y >> len;
        MAP[x][y] = len;
    }
    while (q--) {
        int x;
        cin >> x;
        for (int i = 1; i <= n; i++) {
            if (MAP[x][i] > 0) {
                cout << i << " " << MAP[x][i] << '\n';
            }
        }
    }
    return 0;
}

View Code

本节课作业讲解分析：

链接：https://pan.baidu.com/s/1Y7t-3mAygOu0B2M1H7Vljw?pwd=z41l
提取码：z41l