本篇文章讲述的图的构建方式
本文从解决算法问题的角度,给出几种图的构建方式,他们的代码实现,特点以及优缺点分析。 这些构建方式分别是:
#include<cstring>
using namespace std;
const int N = 1e3;
int graph[N][N];
void init()
{
memset(graph , 0x3f , sizeof graph);
}
void add(int a , int b , int c)
{
graph[a][b] = min(graph[a][b] , c);
}
256MB
的情况下, 最多可以开出数量级为1e3
。#include<vector>
#include<utility>
using namespace std;
typedef pair<int , int> edge;
const int N = 1e5;
vector<edge> graph[N];
void init()
{
return;
}
void add(int a , int b , int c)
{
graph[a].push_back({b , c});
}
#include<unordered_map>
using namespace std;
const int N = 1e5;
unordered_map<int , int> graph[N];
void init()
{
return;
}
void add(int a , int b , int c)
{
if(graph[a].count(b) > 0)
{
graph[a][b] = min(graph[a][b] , c);
}
else
graph[a][b] = c;
}
#include<cstring>
using namespace std;
const int N = 1e5 , M = 3e5;
int h[N] , e[M] , ne[M] , w[M] , idx;
void init()
{
memset(h , -1 , sizeof h);
}
void add(int a , int b , int c)
{
e[idx] = b; w[idx] = c; ne[idx] = h[a]; h[a] = idx++;
}
建图方式\特点 | 建图速度 | 0(1)判边 | 0(1)去重 | 图规模 | 图特点 |
---|---|---|---|---|---|
邻接矩阵 - 二维数组 | 快 | 是 | 是 | 小 | 稠密 |
邻接表 - 向量表 | 中 | 否 | 否 | 中 | 稀疏 |
邻接表 - 哈希表 | 中 | 是 | 是 | 中大 | 一般 |
邻接表 - 模拟数组 | 快 | 否 | 否 | 中大 | 稀疏 |