图

xuanxiao2024 · 2024-08-10 16:05:26 · 个人记录

基本知识

图是什么

由点和线组成的结构就称作图 (\operatorname{Graph})。其中的点称之为顶点 (\operatorname{Vertex}) ，线称为边 (\operatorname{Edge})

如果只存在点，没有边的关系，可以称之为图。
如果只存在边，没有点的关系，不能构成图。

图的分类

有向无向

• 有向图:图的边有方向，只能按箭头从一个点到另一点。
• 无向图:图的边没有方向，可以双向走。
• 混合图:图既有有向边，又有无向边。

  有权无权

• 权值:如果一条边有特定的"长度"，"价格"等，就称为这一条边的权值。
• 有权图:边拥有权值的图
• 无权图:边没有权值的图

  顶点的度

  有向图

• 入度:以这个点为终点的边的数量
• 出度:以这个点为起点的边的数量

  无向图

• 度:直接连接边的数量

  如果想要用双向边表示的话，入度出度按有向图来算

  如何存储图

  二维数组

  这种方法我们一般叫做 邻接矩阵。

  有权

  ##### 无权 $G_{i,j}$ 表示有没有从 $i$ 到 $j$ 的路，0 为没有， 1 为有。 ##### 优点 方便，速度快(常数$\mathcal{O(1)}$) 适合存稠密图 (边多的)。 ##### 缺点 容易炸空间 无法存储重边(有多个 $A \to B$)，自环 (一条边的起点和终点相同) #### $\text{vector}

  这种方法我们一般叫邻接表 拿一个 \text{vector} 数组 G_i。

  如果有边权，开个结构体: ```cpp struct node{//别问我为什么老是取node，问就是好记 int x;// 边权 int e;// 所能走到的顶点 }; ``` ##### 优点 空间可变 可以存储重边，自环 ##### 缺点 时间可能爆炸(常数$\mathcal{O(log_2 \; n)}$)

开始讲题

B3643 图的存储 - 洛谷 | 计算机科学教育新生态

这一题是存图模板题，看他数据范围不超过 3000 (\sqrt[2]{10^{7}} \approx 3162) ，可以用邻接矩阵。
这数据范围才1000，用邻接表也没问题。
基本随便写。

Code

由于邻接矩阵容易爆空间，所以本人喜欢用邻接表(一般不会卡)

#include <iostream>
#include <cstdio>
#include <algorithm>
#include <cmath>
#include <vector>
#include <queue>
using namespace std;
typedef long long ll;
ll n,m;
vector<ll> G[100005];
ll ans[100005];

void dfs(ll x,ll s){
//  cout << x << " " << s << "\n";
    if(ans[x] != 0 && x != s) return ;
    ans[x] = s;
    for(int i = 0;i < G[x].size();i++){
        ll nx = G[x][i];
        if(ans[nx] == 0) dfs(nx,s);
    } 
    return ;
}

int main(){
    cin >> n >> m;
    for(int i = 1;i <= m;i++){
        ll s,e;
        cin >> s >> e;
        G[e].push_back(s);
    }
    for(int i = n;i >= 1;i--){
        if(ans[i] != 0) continue;
        ans[i] = i;
        dfs(i,i);
    }
    for(int i = 1;i <= n;i++){
        cout << ans[i] << " ";
    }
    return 0;
}

P5318 【深基18.例3】查找文献 - 洛谷 | 计算机科学教育新生态

这一题是图上搜索模板题。
图上搜索怎么到另外点?

邻接矩阵

for 循环，\mathcal{O(n)} 寻找。

模板代码

因为是从小到大，所以自带排序(相当于桶排)

for(int i = 1;i <= n;i++){
    if(G[x/*当前查找的数*/][i] == 1){
        //说明找到了,干你想干的   
    }
}

邻接表

由于只存了他能走到的，所以遍历 \text{vector} 就行

模板代码

因为谁也指不定出题人会按照什么顺序给你，所以要在每个节点排序。
我一般放外边，所以这里没给。

for(int i = 0;i < G[x/*要查找的数*/].size();i++){
    //G[x][i] 就是他能走到的点,可以开始操作了 
}

所以直接 \tt DFS 和 \tt BFS 就可以了，每次延伸到没走过且能走到的点即可。

Code

#include <iostream>
#include <cstdio>
#include <algorithm>
#include <cmath>
#include <vector>
#include <queue>
using namespace std;
typedef long long ll;
ll n,m;
vector<ll> G[100005];
bool vis[100005];

void dfs(int x){
    cout << x << " ";
    vis[x] = 1;
    for(int i = 0;i < G[x].size();i++){
        ll nx = G[x][i];
        if(vis[nx] == 0){
            dfs(nx);
        }
    }
}

void bfs(){
    queue<int> q;
    q.push(1);
    vis[1] = 1;
    while(q.size() > 0){
        ll x = q.front();
        q.pop();
        cout << x << " ";
        for(int i = 0;i < G[x].size();i++){
            ll nx = G[x][i];
            if(vis[nx] == 0){
                q.push(nx);
                vis[nx] = 1;
            }
        }
    }
}

int main(){
    cin >> n >> m;
    for(int i = 1;i <= m;i++){
        ll s,e;
        cin >> s >> e;
        G[s].push_back(e);
    }
    for(int i = 1;i <= n;i++){
        vis[i] = 0;
    }
    for(int i = 1;i <= n;i++){
        sort(G[i].begin(),G[i].end());
    }
    dfs(1);
    cout << "\n";
    for(int i = 1;i <= n;i++){
        vis[i] = 0;
    }
    bfs();
    return 0;
}

B3613 图的存储与出边的排序 - 洛谷 | 计算机科学教育新生态

这题一看，大于 3000 了，邻接矩阵做不了了。
直接输出能到的点即可(不想多说)

Code

#include <iostream>
#include <cstdio>
#include <algorithm>
#include <cmath>
#include <vector>
using namespace std;
typedef long long ll;
ll n,m;
vector<ll> G[500005];

void init(){
    for(int i = 1;i <= n;i++){
        G[i].clear();
    }
    return ;
}

void work(){
    cin >> n >> m;
    for(int i = 1;i <= m;i++){
        ll s,e;
        cin >> s >> e;
        G[s].push_back(e);
    }
    for(int i = 1;i <= n;i++){
        sort(G[i].begin(),G[i].end());
        for(int j = 0;j < G[i].size();j++){
            cout << G[i][j] << " ";
        }
        cout << "\n";
    }
    init();
}

int main(){
    ll T;
    cin >> T;
    while(T--) work();
    return 0;
}

P3916 图的遍历 - 洛谷 | 计算机科学教育新生态

先考虑爆搜，10^5 的数据不太行， 10^3 的数据可以，所以可以去写 B3862 图的遍历（简单版） - 洛谷 | 计算机科学教育新生态

这里用到了一个反向建图的技巧，看下图：

这是样例的图，如果直接爆搜，我们就得从每个点出发。
那我们可不可以像当初贪心那样反向想一想。
那我们能不能终点找起点?

从大到小枚举，每次从一个点进行搜索。如果遇到走过了的，就这个分支停止(都有大的能走到这了，那么剩下这个分支你能走到大的也能走到，那走还有什么意义?)，将所有走过的点就标记为这个数。由于是从大到小，他自然是能走到这最大的。

但是直接走就反了，我们所以我们将图的边的反过来。

这就对了。

Code

#include <iostream>
#include <cstdio>
#include <algorithm>
#include <cmath>
using namespace std;
typedef long long ll;
ll n,m;
int vis[1005][1005];

int main(){
    cin >> n >> m;
    for(int i = 1;i <= m;i++){
        ll l,r;
        cin >> l >> r;
        vis[l][r] = 1;
        vis[r][l] = 1;
    }
    for(int i = 1;i <= n;i++){
        for(int j = 1;j <= n;j++){
            cout << (vis[i][j] > 0 ? 1 : 0) << " ";
        }
        cout << "\n";
    } 
    for(int i = 1;i <= n;i++){
        ll sum = 0;
        for(int j = 1;j <= n;j++){
            sum += vis[i][j];
        }
        cout << sum << " ";
        for(int j = 1;j <= n;j++){
            if(vis[i][j] == 1){
                cout << j << " ";
            }
        }
        cout << "\n"; 
    }
    return 0;
}