看着星空都想起图论了

图论的存储在图论学习中是一个非常重要的内容,只有掌握图的存储形式,才能更好地学习更深的图论知识.

本文着重介绍的图的三种存储方式.

其中,你需要了解的:

• 在本文中u v w 一般代表着起点,终点和这两点连线的权值,一般来说表示从u 点到v 点这条线的权值为w

• adj 通常表示存图的数组,在不同的存储方式有不同的含义.

• 一般题目会给你节点数边数然后直接给你一堆u,v,w

• 在图论相关的复杂度分析语境中，$d^{+}(u)$ 表示顶点u 的出度 。 出度指的是从顶点u 出发的边的数量。

1.邻接矩阵

1.1概括

很容易想到可以用一个数组表示两连线边的权值.

我们定义一个二维数组adj[i][j],其中adj[u][v]=w表示从u点到v点这条边的权值为w.通过这个数组,我们可以容易的把这个图存储起来.如果没有非正数权值,且adj[i][j]=0,就代表从点i到点j没有线段(看你怎么初始化adj数组,我习惯初始化为0)

但是如果这个图是一个无向图该怎办?很容易想到一个无向图等于一个双向的有向图,也就是如果a,b之间有一个无向的线段权值为w,那么只需要存储下来adj[a][b]=adj[b][a]=w就做到了无向图的存储.

1.2详细

1.3代码

然后我们很容易就写出来了这个程序的代码,这里我为你提供了一个add 和look_up 方法,注释里有详细说明.

#include<bits/stdc++.h>
using namespace std;
const int MAXX = 1000;
int adj[MAXX][MAXX]; //邻接矩阵
int n, m; //n个顶点，m条边
void add(int u, int v, int w) {//存图
    adj[u][v] = w;
    //adj[v][u] = w; //无向图
}
int look_up(int u, int v) {//查找u到v的权值
    return adj[u][v];
}
int main() {
    int u, v, w;//u到v的权值为w
    cin >> n >> m;
    for (int i = 1; i <= m; i++) {
        cin >> u >> v >> w;
        add(u, v, w);
    }
    for (int i = 1; i <= n; i++) {
        for (int j = 1; j <= n; j++) {
            cout << adj[i][j] << " ";
        }
        cout << endl;
    }
    return 0;
}

输入:
4 5
1 2 1
2 3 3
3 4 5
1 3 4
1 4 2
输出:
0 1 4 2 
0 0 3 0
0 0 0 5
0 0 0 0

1.4分析

空间复杂度$O(n^2)$ (n是所有顶点数量)

时间复杂度:

• 查找A 点到B 点的边: $O(1)$

• 添加一条边: $O(1)$

• 遍历某个顶点的所有邻接点：$O(n)$

• 遍历所有边：$O(n^2)$

对于一些稀疏图,使用邻接表很容易就把内存给爆掉了.

通过这样的数据结构构造我们发现利用邻接矩阵存图实在是太浪费空间了,整个数组会有很多没有存东西.那么有没有不浪费空间的存储算法呢?

有的兄弟,有的

2.邻接表

2.1概括

很容易想到我们可以这样定义避免内存上的开销

struct node{
  int v;//这条边的终点
  int w;//权值
};
vector<node>adj[MAXN];

这样一来,adj[u][i].v就表示以点u为起点的第i 条边的终点.adj[u][i].w就表示以点u为起点的第i 条边的权值.

然后用adj[u].push_back((node) { v, w }); 来存图

2.2详细

我们既然存边会耗费掉很多空间,那我们就试试存点,通过点来获得线段的信息,于是,我们可以定义一个结构体node

struct node{
  int v;//这条边的终点
  int w;//权值
};

那么就要定义一个二维的数组adj来表示一条边,可是不能用两个点表示一条边了,我们就想到可以以一个点为起点,记录以它为起点的第几条边,于是可以想到adj[u][i]可以表示这个结构体,它的意义是以点u为起点的第i条边的终点和权值.

为了不浪费空间,我们可以使用vector 来存储第几条边.因为题目会给出点的数量,那么u就可以用一个普通的数组存储,这样就节省了浪费掉的空间.

于是得到这样的声明:

struct node{
  int v;//这条边的终点
  int w;//权值
};
vector<node>adj[MAXN];

其中MAXN 表示数据范围最大值,如果你觉得这个声明不太好理解,那么可以像我一样理解:

定义一个容量为MAXN 类型为vector<node>的数组adj,

所以adj 的任意一个元素adj[i] 都表示一个类型为vector<node>的元素,也就是我们说的存第几条边的信息,

所以任意的adj[i][j] 都表示一个类型为结构体node 的元素.

很容易得到adj[u].push_back((node) { v, w }); 可以直接存储下来一对u,v,w

说完了有向图,那么同样的,对于无向图,我们再次声明adj[v].push_back((node) { u, w }); 即可.

2.3代码

很显然,这样的存储逻辑可以用代码表示

这段代码输入了n,m表示n个点，m条边, 简单地用邻接表存图.然后用一个while 循环输入两个数u 和v 然后输出u 点到v 点这条边的权值

这个示例代码里,add(u,v,w) 表示添加一个以u 为起点v 为终点且权值为w 的边.look_up(u,v) 表示查找从u到v的边的权重

#include<bits/stdc++.h>
using namespace std;
const int MAXN = 1000;
struct node {
    int v;//边的终点
    int w;//边的权重
};
vector<node>adj[MAXN]; //邻接表存图
int n, m; //n个点，m条边
void add(int u, int v, int w) {
    adj[u].push_back((node) { v, w });//添加一条从u到v，权重为w的边
    //adj[v].push_back((node) { u, w });//添加一条从v到u，权重为w的边,如果是无向图
}
int look_up(int u, int v) {//查找从u到v的边的权重
    for (int i = 0;i < adj[u].size();i++) {
        if (adj[u][i].v == v) {
            return adj[u][i].w;
        }
    }
    return -1;
}
int main() {
    int u, v, w;
    cin >> n >> m;
    for (int i = 0;i < m;i++) {
        cin >> u >> v >> w;
        add(u, v, w);
    }
    while (cin >> u >> v) {
        cout << look_up(u, v) << endl;
    }
    return 0;
}

输入:
4 5
1 2 1
2 3 3
3 4 5
1 3 4
1 4 2
1 2
2 3
3 4
1 3
1 4
输出:
1
3
5
4
2

2.4分析

存各种图都很适合

复杂度 查询是否存在u到v的边：O(d⁺(u))（如果事先进行了排序就可以使用二分查找做到O(\log(d⁺(u))) ）

遍历点u的所有出边：O(d⁺(u))

遍历整张图：O(n + m)

空间复杂度：O(m)

From OI Wiki

3.链式前向星

如果说邻接表是不好写但效率好，邻接矩阵是好写但效率低的话，前向星就是一个相对中庸的数据结构。前向星固然好写，但效率并不高。而在优化为链式前向星后，效率也得到了较大的提升。虽然说，世界上对链式前向星的使用并不是很广泛，但在不愿意写复杂的邻接表的情况下，链式前向星也是一个很优秀的数据结构。 ——摘自《百度百科》

3.1概括

我们定义一个数组head和edge ,head[i]存储以节点i为起点的所有边的起始位置,edge[i]存储第i条边的信息.

3.2详细

文字和图片不好展示,我可以提供一个讲得比较好得视频,请看此视频最后的内容 等到有时间我一定要详细做一个

或者有一个博客讲的挺好的

3.3代码

这里提供一个模板,有添加,修改,查找功能.

#include<bits/stdc++.h>
using namespace std;
const int MAXN = 1000;
struct Edge {
    int to, w, nxt;//to是这条边的终点，w是这条边的权值，nxt是下一条边的编号
}edge[MAXN];
int head[MAXN], cnt;//head存每个点的第一条边，cnt存边的数量
int n, m;//n个点,m条边
void add(int u, int v, int w) {
    edge[++cnt].to = v;//终点是v
    edge[cnt].w = w;//权值是w
    edge[cnt].nxt = head[u];//下一条边的编号是head[u]
    head[u] = cnt;//head[u]存的是第一条边的编号
}
int look_up(int u, int v) {//查权值
    for (int i = head[u];i;i = edge[i].nxt)
        if (edge[i].to == v) return edge[i].w;
    return -1;
}
void modify(int u, int v, int w) {//改权值
    for (int i = head[u];i;i = edge[i].nxt)
        if (edge[i].to == v) edge[i].w = w;
}
int main() {
    memset(head, -1, sizeof(head));//初始化head数组为-1
    int u, v, w;
    cin >> n >> m;
    for (int i = 1;i <= m;i++) {//Input
        cin >> u >> v >> w;
        add(u, v, w);
    }
    return 0;
}

3.4分析

查询是否存在 u 到 v的边：$O (d⁺(u))$

遍历点u的所有出边：$O (d⁺(u))$

遍历整张图：$O (n + m)$

空间复杂度：$O (m)$

相关资料