图的学习

167天前 · OI · 12次阅读

什么是图

图是描述物件之间的关系。
物件就是结点,物件之间的关系即是边。

所以我们可以发现几乎所有的关系都可以表示成图,dp可以表示成DAG(有向无环图),搜索本质上是图的遍历算法,树也是特殊的图……

且图的存在也是非常重要的,很多问题都需要图的解决,比如导航就可以用图实现。

图的储存方式

图有多种储存方式,比如邻接矩阵,比如用vector。

邻接矩阵

定义 $map[u][v]$ (map是c++关键字)表示u和v节点直接有一条边。

空间复杂度为$O(n^{2})$,在$n<=10^3$的时候适用。

举个例子,现在输入2个人,他们是朋友,最后统计每个人有多少个朋友。

我们可以定义$w[1e3+5$][1e3+5]来存储2个人是否为朋友,遍历$w[i][1~n]$即可判断是否为朋友。

这样我们就用实现了$O(n)$输入,$O(n)$查询。

#include <bits/stdc++.h>
using namespace std;

bool w[1005][1005];  // w[x][y]: x 与 y 是否为朋友
int n, m;


void input() {
    cin >> n >> m;
    for(int i=1; i<=m; i++) {
        int u, v;
        cin >> u >> v;

        // u, v 是朋友
        w[u][v] = 1;        // v 是 u 的朋友
        w[v][u] = 1;        // u 是 v 的朋友
    }
}

// 统计 x 有多少个朋友
int getCnt(int x) {
    // 枚举每一个人,判断他是否为 x 的朋友
    int res = 0;

    for(int i=1; i<=n; i++)
        if(w[x][i]) res++;
    return res;
}

void work() {
    for(int i=1; i<=n; i++)
        cout << getCnt(i) << endl;
}

int main() {
    input();
    work();

    return 0;
}

vector存图

vector存图可能是用的最多的了,有的人喜欢用链式前向星来存图,但实际上vector就是在做链式前向星做的事。

对于每一个点,开一个vector存下他的边,空间复杂度:$O(m)$,查询时间复杂度:$O(m)$是不是比邻接矩阵好多了?

当然当节点较少时还是邻接矩阵方便。

再将刚刚的问题用vector表示一下:

#include <iostream>
#include <vector>
using namespace std;
int n, m;
vector<int> e[100005];
int main()
{
    cin >> n >> m;
    for (int i = 1; i <= m; i++)
    {
        int u, v;
        cin >> u >> v;
        e[u].push_back(v);
        e[v].push_back(u);
    }
    for (int i = 1; i <= n; i++)
        cout << e[i].size() << endl;
    return 0;
}

总结

邻接矩阵:用$w[u][v]$存边权即可。
vector:需要写个结构体,来把邻居编号和边权打包起来;

邻接矩阵和vector存图的选择

图分为稀疏图和稠密图,当节点非常多,而边非常少的时候,他为稀疏图,反之则为稠密图。

因为vector没东西的时候几乎不用空间,所以我们可以选择vector,而当节点非常少,边非常多的时候我们就可以选择邻接矩阵存图。

有向图

刚刚我们为什么要把u和v都存一下对方呢?因为刚刚我们存储的是无向图,即两边都通,所以我们就需要把u和v都存一条通向对方的边。

有向图只需要只存一条边即可。

This post was written on Aug 16, 2022.
👍 1

none

最后修改于12天前

评论

贴吧 狗头 原神 小黄脸
收起

贴吧

  • 贴吧泡泡
  • 贴吧泡泡
  • 贴吧泡泡
  • 贴吧泡泡
  • 贴吧泡泡
  • 贴吧泡泡
  • 贴吧泡泡
  • 贴吧泡泡
  • 贴吧泡泡
  • 贴吧泡泡
  • 贴吧泡泡
  • 贴吧泡泡
  • 贴吧泡泡
  • 贴吧泡泡
  • 贴吧泡泡
  • 贴吧泡泡
  • 贴吧泡泡
  • 贴吧泡泡
  • 贴吧泡泡
  • 贴吧泡泡
  • 贴吧泡泡
  • 贴吧泡泡
  • 贴吧泡泡
  • 贴吧泡泡
  • 贴吧泡泡
  • 贴吧泡泡
  • 贴吧泡泡
  • 贴吧泡泡
  • 贴吧泡泡
  • 贴吧泡泡
  • 贴吧泡泡
  • 贴吧泡泡
  • 贴吧泡泡
  • 贴吧泡泡
  • 贴吧泡泡
  • 贴吧泡泡
  • 贴吧泡泡
  • 贴吧泡泡
  • 贴吧泡泡
  • 贴吧泡泡
  • 贴吧泡泡
  • 贴吧泡泡
  • 贴吧泡泡
  • 贴吧泡泡
  • 贴吧泡泡
  • 贴吧泡泡
  • 贴吧泡泡
  • 贴吧泡泡
  • 贴吧泡泡
  • 贴吧泡泡
  • 贴吧泡泡
  • 贴吧泡泡
  • 贴吧泡泡
  • 贴吧泡泡
  • 贴吧泡泡
  • 贴吧泡泡
  • 贴吧泡泡
  • 贴吧泡泡
  • 贴吧泡泡
  • 贴吧泡泡
  • 贴吧泡泡
  • 贴吧泡泡
  • 贴吧泡泡
  • 贴吧泡泡
  • 贴吧泡泡
  • 贴吧泡泡
  • 贴吧泡泡
  • 贴吧泡泡
  • 贴吧泡泡
  • 贴吧泡泡
  • 贴吧泡泡

狗头

  • 狗头
  • 狗头
  • 狗头
  • 狗头
  • 狗头
  • 狗头
  • 狗头
  • 狗头
  • 狗头
  • 狗头
  • 狗头
  • 狗头

原神

  • 原神
  • 原神
  • 原神
  • 原神
  • 原神
  • 原神
  • 原神
  • 原神
  • 原神
  • 原神
  • 原神
  • 原神
  • 原神
  • 原神
  • 原神
  • 原神
  • 原神
  • 原神
  • 原神
  • 原神
  • 原神
  • 原神
  • 原神

小黄脸

  • 小黄脸
  • 小黄脸
  • 小黄脸
  • 小黄脸
  • 小黄脸
  • 小黄脸
  • 小黄脸
  • 小黄脸
  • 小黄脸
  • 小黄脸
  • 小黄脸
  • 小黄脸
  • 小黄脸
  • 小黄脸
  • 小黄脸
  • 小黄脸
  • 小黄脸
  • 小黄脸
  • 小黄脸
  • 小黄脸
  • 小黄脸
  • 小黄脸
  • 小黄脸
  • 小黄脸
  • 小黄脸
  • 小黄脸
  • 小黄脸
  • 小黄脸
  • 小黄脸
  • 小黄脸
  • 小黄脸
  • 小黄脸
  • 小黄脸
  • 小黄脸
  • 小黄脸
  • 小黄脸
  • 小黄脸
  • 小黄脸
  • 小黄脸
  • 小黄脸
  • 小黄脸
  • 小黄脸
  • 小黄脸
  • 小黄脸
  • 小黄脸

目录

avatar

only_matthew

人生如戏,戏如人生。

41

文章数

2

评论数

7

分类