图的存储
本文最后更新于 216 天前,其中的信息可能已经有所发展或是发生改变。

1. 邻接矩阵


思想

  • 利用二维数组 g[N][N] 存储所有的点到点的权值。
  • 其中 N 为点的数量,g[i][j] 表示点 i 到点 j 的权值。

时间复杂度O(n2)\mathcal{O}(n^2)

空间复杂度O(n2)\mathcal{O}(n^2)

应用

  • 只在点数不多的稠密图使用。
  • 大部分情况下点的数量 n=103n = 10^3,边的数量 m=106m = 10^6

示例

  • 现有 n 个点共 m 条边,以及每条边的起始点和终点及权值。
  • 这些点和边共同构成一个有向图。
  • 存储这些信息并输出。

输入

4 5
1 2 20
1 4 40
2 3 50
2 4 60
3 2 30

代码

#include <bits/stdc++.h>
using namespace std;
const int N = 1010; //图的大小
int n, m;
int g[N][N];
bool vis[N]; //标记是否走过
void dfs(int u){ //深度优先遍历
vis[u] = 1; //标记当前点已经遍历过
for(int i = 1; i <= n; i ++){ //遍历n个点
if(g[u][i] != 0){
cout << u << ' ' << i << ' ' << g[u][i] << endl;
if(vis[i]) continue; //当前的边的终点已经走过则跳过
dfs(i);
}
}
}
void solve(){
cin >> n >> m;
for(int i = 0; i < m; i ++){
int a, b, c; cin >> a >> b >> c;
g[a][b] = c;
// g[b][a] = c; //如果是无向图加一条边
}
dfs(1); //从1号点开始遍历
}
int main(){
solve();
return 0;
}

输出

1 2 20
2 3 50
3 2 30
2 4 60
1 4 40

2. 边集数组


思想

  • 利用结构体数组 e[N] 存储边的信息。
  • 其中 e[i] 包含第 i 条边的 {起始点u, 终点v, 边权w}

时间复杂度O(nm)\mathcal{O}(nm)

空间复杂度O(m)\mathcal{O}(m)

应用

  • Kruskal 算法中,需要将边按照边权排序,直接存边。

示例

  • 现有 n 个点共 m 条边,以及每条边的起始点和终点及权值。
  • 这些点和边共同构成一个有向图。
  • 存储这些信息并输出。

输入

7 6
4 3 90
1 4 30
5 7 80
5 6 60
1 5 20
5 2 70

代码

#include <bits/stdc++.h>
using namespace std;
const int N = 1010; //图的大小
int n, m;
struct edge{
int u, v, w;
}e[N];
bool vis[N]; //标记是否走过
void dfs(int u){ //深度优先遍历
vis[u] = 1; //标记当前点已经遍历过
for(int i = 1; i <= m; i ++){ //遍历m条边
if(u == e[i].u){ //找到当前的边的起始点
cout << e[i].u << ' ' << e[i].v << ' ' << e[i].w << endl;
if(vis[e[i].v]) continue; //当前的边的终点已经走过则跳过
dfs(e[i].v);
}
}
}
void solve(){
cin >> n >> m;
for(int i = 1; i <= m; i ++){
int a, b, c; cin >> a >> b >> c;
e[i] = {a, b, c};
// e[i] = {b, a, c}; //如果是无向图加一条边
}
dfs(1); //从1号点开始遍历
}
int main(){
solve();
return 0;
}

输出

1 4 30
4 3 90
1 5 20
5 7 80
5 6 60
5 2 70

3. 邻接表


思想

  • 利用出边数组 e[N][N] 存储边的信息。
  • 其中 e[u][i] 表示点 u 的所有出边,其出边包含 {终点v, 边权w}

时间复杂度O(n+m)\mathcal{O}(n+m)

空间复杂度O(n+m)\mathcal{O}(n+m)

应用

  • 可以应用于各种图,但是不能处理反向的边(网络流)。

示例

  • 现有 n 个点共 m 条边,以及每条边的起始点和终点及权值。
  • 这些点和边共同构成一个有向图。
  • 存储这些信息并输出。

输入

7 6
4 3 90
1 4 30
5 7 80
5 6 60
1 5 20
5 2 70

代码

#include <bits/stdc++.h>
using namespace std;
const int N = 1010; //图的大小
int n, m;
struct edge{
int v, w;
};
vector<edge> e[N]; //边集
void dfs(int u, int fa){ //深度优先遍历, fa记录当前点的父节点
for(auto p : e[u]){ //遍历所有的出边
if(fa == p.v) continue; //若该出边的终点是父节点,说明已经走过
cout << u << ' ' << p.v << ' ' << p.w << endl;
dfs(p.v, u);
}
}
void solve(){
cin >> n >> m;
for(int i = 1; i <= m; i ++){
int a, b, c; cin >> a >> b >> c;
e[a].push_back({b, c});
// e[b].push_back({a, c}); //如果是无向图加一条边
}
dfs(1, 0); //从1号点开始遍历
}
int main(){
solve();
return 0;
}

输出

1 4 30
4 3 90
1 5 20
5 7 80
5 6 60
5 2 70

4. 链式邻接表


思想

  • 利用边集数组 e[N] 存储所有的边的信息,表头数组 h[N][N] 存储点的所有出边的编号。
  • 其中 e[j] 存储第 j 条边的 {起始u, 终点v, 边权w}h[u][i] 存储 u 点的第 i 条边的编号。

时间复杂度O(n+m)\mathcal{O}(n+m)

空间复杂度O(n+m)\mathcal{O}(n+m)

应用

  • 可以应用于各种图,也能处理反向的边。

示例

  • 现有 n 个点共 m 条边,以及每条边的起始点和终点及权值。
  • 这些点和边共同构成一个无向图。
  • 存储这些信息并输出。

输入

6 5
4 3 90
1 4 30
5 6 60
1 5 20
5 2 70

代码

#include <bits/stdc++.h>
using namespace std;
const int N = 1010; //图的大小
int n, m;
struct edge{
int u, v, w;
};
vector<edge> e; //边集
vector<int> h[N]; //点的所有出边
void add(int a, int b, int c){
e.push_back({a, b, c});
h[a].push_back(e.size() - 1);
}
void dfs(int u, int fa){ //深度优先遍历, fa记录当前点的父节点
for(int i = 0; i < h[u].size(); i ++){
int j = h[u][i];
if(fa == e[j].v) continue;
cout << u << ' ' << e[j].v << ' ' << e[j].w << endl;
dfs(e[j].v, u);
}
}
void solve(){
cin >> n >> m;
for(int i = 1; i <= m; i ++){
int a, b, c; cin >> a >> b >> c;
add(a, b, c);
add(b, a, c); //如果是无向图加一条边
}
dfs(1, 0); //从1号点开始遍历
}
int main(){
solve();
return 0;
}

输出

1 4 30
4 3 90
1 5 20
5 6 60
5 2 70

5. 链式前向星


思想

  • 一个表头悬挂多个链表。
  • 利用边集数组 e[N] 存储所有的出边的信息,表头数组 h[N] 存储点的第一条出边的编号。
  • 其中 e[i] 存储第 i 条边的 {终点v, 边权w, 下一条边ne}h[u] 存储 u 点的第一条出边的编号。

时间复杂度O(n+m)\mathcal{O}(n+m)

空间复杂度O(n+m)\mathcal{O}(n+m)

应用

  • 可以应用于各种图,也能处理反向的边。

示例

  • 现有 n 个点共 m 条边,以及每条边的起始点和终点及权值。
  • 这些点和边共同构成一个无向图。
  • 存储这些信息并输出。

输入

6 5
4 3 90
1 4 30
5 6 60
1 5 20
5 2 70

代码

#include <bits/stdc++.h>
using namespace std;
const int N = 1e6 + 3; //图的大小
int n, m;
struct edge{
int v, w, ne;
}e[N]; //边集
int idx, h[N]; //点的第一条出边,idx为下标编号
void add(int a, int b, int c){
e[idx] = {b, c, h[a]};
h[a] = idx ++;
}
void dfs(int u, int fa){ //深度优先遍历, fa记录当前点的父节点
for(int i = h[u]; ~ i; i = e[i].ne){
if(fa == e[i].v) continue;
cout << u << ' ' << e[i].v << ' ' << e[i].w << endl;
dfs(e[i].v, u);
}
}
void solve(){
cin >> n >> m;
memset(h, -1, sizeof h); //初始化第一条出边为-1
for(int i = 1; i <= m; i ++){
int a, b, c; cin >> a >> b >> c;
add(a, b, c);
add(b, a, c); //如果是无向图加一条边
}
dfs(1, 0); //从1号点开始遍历
}
int main(){
solve();
return 0;
}

输出

1 5 20
5 2 70
5 6 60
1 4 30
4 3 90

总结


  • 链式邻接表和链式前向星可以解决绝大部分的图论问题。
  • 推荐使用链式前向星,建图方式简便,空间压缩紧密,查找效率高。
暂无评论

发送评论 编辑评论


				
|´・ω・)ノ
ヾ(≧∇≦*)ゝ
(☆ω☆)
(╯‵□′)╯︵┴─┴
 ̄﹃ ̄
(/ω\)
∠( ᐛ 」∠)_
(๑•̀ㅁ•́ฅ)
→_→
୧(๑•̀⌄•́๑)૭
٩(ˊᗜˋ*)و
(ノ°ο°)ノ
(´இ皿இ`)
⌇●﹏●⌇
(ฅ´ω`ฅ)
(╯°A°)╯︵○○○
φ( ̄∇ ̄o)
ヾ(´・ ・`。)ノ"
( ง ᵒ̌皿ᵒ̌)ง⁼³₌₃
(ó﹏ò。)
Σ(っ °Д °;)っ
( ,,´・ω・)ノ"(´っω・`。)
╮(╯▽╰)╭
o(*////▽////*)q
>﹏<
( ๑´•ω•) "(ㆆᴗㆆ)
😂
😀
😅
😊
🙂
🙃
😌
😍
😘
😜
😝
😏
😒
🙄
😳
😡
😔
😫
😱
😭
💩
👻
🙌
🖕
👍
👫
👬
👭
🌚
🌝
🙈
💊
😶
🙏
🍦
🍉
😣
Source: github.com/k4yt3x/flowerhd
颜文字
Emoji
小恐龙
花!
上一篇
下一篇