一、图的存储方式
图的存储主要分为五类:邻接矩阵、边集数组、邻接表、链式邻接表、链式前向星。
1.邻接矩阵
用二维数组w[u][v]表示从u到v的边权
时间复杂度:O(n^2)
空间复杂度:O(n^2)
1.模板
//图的存储
for(int i=1;i<=m;++i){//m为边的数量
cin>>a>>b>>c;
w[a][b]=c;
w[b][a]=c;//无向边时需反向存储
}
//图的遍历
void dfs(int u){
vis[u]=1//标记访问过的点
for(int v=1;v<=n;++i){
if(w[u][v]{//有边才访问
if(vis[v]) continue;//判重
dfs(v);
}
}
注:邻接矩阵适用于点数不多的稠密图中
2.边集数组
用结构体数组存储第i条边{起点u,终点v, 权值 w}
时间复杂度:O(nm)
空间复杂度:O(m)
1、模板
//建立数组
strcut edge{
int u,v,w;//起点,终点,权值
}e[M];
//图的存储
for(int i=1;i<=m;++i){//m为边数
cin>>a>>b>>c;
e[i]={a,b,c}
//e[i+1]={b,a,c}//无向边反向存储
}
//图的遍历
void dfs(int u){
vis[u]=1;//标记访问过的边
for(int i=1;i<=m;++i){
if(e[i].u==u){
if(vis[u]) continue;//判重
dfs(e[i].v);
}
}
注:复杂度过高,常用于Kruskal算法,需将边按边权排序存储。
3.邻接表
用出边数组e[i]来存储{终点v,边权w}
时间复杂度:O(n+m)
空间复杂度:O(n+m)
1.模板
//建立数组
struct edge{
int v,w;//终点,边权
};
vector<edge> e[N];//出边数组 尾插存入
//存储图
for(int i=1;i<=m;++i){
cin>>a>>b>>c;
e[a].push_back({b,c});
e[b].puah_back({a,c});//无向边反向存储
}
//图的遍历
void dfs(int u,int fa){//当前节点,父节点
for(auto ed:e[u]){//遍历当前节点所连接的边 ==for(int i=0;i<sizeof(e[u]);++i)
if(ed.u==fa) continue;//判重
bfs(ed.v,u);
}
}
注:不能用于含环的图的存储,不能处理反向边
4.链式邻接表
用边集数组e[i]存储{起点u,终点v,边权w} 用表头数组h[i][j]存储每条边所以出边的编号
时间复杂度:O(n+m)
空间复杂度:O(n+m)
1、模板
//数组建立
struct edge{
int u,v,w//起点,终点,边权
}
vector<edge> e;//边集数组--记录边的信息
vector<int> h[N];//表头数组--记录边的编号
// 图的存储
for(int i=1;i<=m;++i){
cin>>a>>b>>c;
add(a,b,c);
add(b,a,c);//相邻存储--可用异或快速寻找反向边
}
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=1;i<=h[u].size();++i){
int j=h[u][i];//边的编号
int v=e[j].v;
if(v==fa) continue;//判重
dfs(v,u);
}
}
注:能处理各种图和反向边
5.链式前向星
边集数组e[i]存{终点v,边权w,下一条边编号ne} 表头数组h[i] 存储i号点的第一条出边,idx为边的编号
时间复杂度:O(n+m)
空间复杂度:O(n+m)
1、模板
//数组建立
struct edge{
int v,w,ne;//终点,边权,下一条边的编号
}e[N];
int h[N],idx=0;//头插入
//边的存入
memset(h,-1,sizeof(h));//初始化表头数组
for(int i=1;i<=m;++i){
cin>>a>>b>>c;
add(a,b,c);
add(b,a,c);
}
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){
int v=e[i].v;
if(v==fa) continue;//判重
dfs(v,u);
}
}
注:能处理各种图,反向边
二、总结
临界矩阵 | 边集数组 | 邻接表 | 链式邻接表 | 链式前向星 | |
定义 | int w[N][N] //边 | struct edge{ }e[N];//边 | struct edge{ } vector<edge> e[N]//边 | struct edge{ int u,v,w; } vector<int>h[N];//表头 vector<edge>e//边 | struct edge{ }e[N];//边 int h[N];//表头 |
建边 | w[a][b]=c | e[i]={a,b,c} | e[a]={b,c} | e.push_back({a,b,c}); h[a].push_back(e.size()+1) | e[idx]={b,c,h[a]}; h[a]=idx++ |
访问 | 按行列访问 for(int v=1;v<=m;++v){ if(w[u][v]){ vis[v]; dfs(v); } } | 按边顺序访问 for(int i=1;i<=m;++i){ if(e[i].u==u){ dfs(e[i].v); | 先插入后访问 for(auto ed:e[u]){ if(ed.v==fa) continue; dfs(ed.v,u); } | 先插入后访问 for(int i=1;i<=h.size();++i){ if(e[j].v==fa) continue; dfs(e[j].v,u); | 先插入后访问 for(int i=h[u];~i;i=e[u].ne){ dfs(e[i].v,u); |
时间复杂度 | O(n^2) | O(mn) | O(n+m) | O(n+m) | O(n+m) |
空间复杂度 | O(n^2) | O(m) | O(n+m) | O(n+m) | O(n+m) |
应用 | 稠密图 | Kruskal算法 | 各种图 不能处理反向边 | 各种图 能处理反向边 | 各种图 能处理反向边 |