本文最后更新于 216 天前,其中的信息可能已经有所发展或是发生改变。
思想:
- 利用二维数组
g[N][N]
存储所有的点到点的权值。
- 其中
N
为点的数量,g[i][j]
表示点 i
到点 j
的权值。
时间复杂度:O(n2)
空间复杂度:O(n2)
应用:
- 只在点数不多的稠密图使用。
- 大部分情况下点的数量 n=103,边的数量 m=106。
示例:
- 现有
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 ++){ |
| 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; |
| |
| } |
| |
| dfs(1); |
| |
| } |
| |
| int main(){ |
| |
| solve(); |
| |
| return 0; |
| } |
输出:
| 1 2 20 |
| 2 3 50 |
| 3 2 30 |
| 2 4 60 |
| 1 4 40 |
思想:
- 利用结构体数组
e[N]
存储边的信息。
- 其中
e[i]
包含第 i
条边的 {起始点u, 终点v, 边权w}
。
时间复杂度:O(nm)
空间复杂度: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 ++){ |
| 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}; |
| |
| } |
| |
| dfs(1); |
| |
| } |
| |
| int main(){ |
| |
| solve(); |
| |
| return 0; |
| } |
输出:
| 1 4 30 |
| 4 3 90 |
| 1 5 20 |
| 5 7 80 |
| 5 6 60 |
| 5 2 70 |
思想:
- 利用出边数组
e[N][N]
存储边的信息。
- 其中
e[u][i]
表示点 u
的所有出边,其出边包含 {终点v, 边权w}
。
时间复杂度:O(n+m)
空间复杂度: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){ |
| 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}); |
| |
| } |
| |
| dfs(1, 0); |
| |
| } |
| |
| int main(){ |
| |
| solve(); |
| |
| return 0; |
| } |
输出:
| 1 4 30 |
| 4 3 90 |
| 1 5 20 |
| 5 7 80 |
| 5 6 60 |
| 5 2 70 |
思想:
- 利用边集数组
e[N]
存储所有的边的信息,表头数组 h[N][N]
存储点的所有出边的编号。
- 其中
e[j]
存储第 j
条边的 {起始u, 终点v, 边权w}
,h[u][i]
存储 u
点的第 i
条边的编号。
时间复杂度:O(n+m)
空间复杂度: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){ |
| 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); |
| |
| } |
| |
| int main(){ |
| |
| solve(); |
| |
| return 0; |
| } |
输出:
| 1 4 30 |
| 4 3 90 |
| 1 5 20 |
| 5 6 60 |
| 5 2 70 |
思想:
- 一个表头悬挂多个链表。
- 利用边集数组
e[N]
存储所有的出边的信息,表头数组 h[N]
存储点的第一条出边的编号。
- 其中
e[i]
存储第 i
条边的 {终点v, 边权w, 下一条边ne}
,h[u]
存储 u
点的第一条出边的编号。
时间复杂度:O(n+m)
空间复杂度: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]; |
| |
| void add(int a, int b, int c){ |
| e[idx] = {b, c, h[a]}; |
| h[a] = idx ++; |
| } |
| |
| void dfs(int u, int 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); |
| 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); |
| |
| } |
| |
| int main(){ |
| |
| solve(); |
| |
| return 0; |
| } |
输出:
| 1 5 20 |
| 5 2 70 |
| 5 6 60 |
| 1 4 30 |
| 4 3 90 |
- 链式邻接表和链式前向星可以解决绝大部分的图论问题。
- 推荐使用链式前向星,建图方式简便,空间压缩紧密,查找效率高。