图论之存图 2023.4.25
概述
- 主要有四种
- 每种都有不同的用途
- 为方便，下文记点集为 \(|V|\), 大小为 \(n\);
- 边集为 \(|E|\), 大小为 \(m\)。
01 直接存边
时间复杂度：
- 遍历（DFS，BFS） \(\Theta(\infin)\)
- 判断是否存在 \(\Theta(m)\)
空间复杂度：
- \(\Theta(m)\)
代码
struct Edge{
int u,v,w;
Edge(int a,int b,int c){u=a,v=b,w=c;}
}edge[100010];
int cnt=1;
void addedge(int u,int v,int w){
edge[cnt++](u,v,w);
}
优点
- 可能在某些算法里会用到
- 如
Krustal,Bellman-Ford
缺点
- 无法快速的判断是否存在 \((u,v)\) 边
- 无法
DFS或BFS（即无法遍历图）
02 邻接矩阵
时间复杂度：
- 遍历（DFS，BFS） \(\Theta(n^2)\)
- 判断是否存在 \(\Theta(1)\)
空间复杂度：
- \(\Theta(n^2)\)
代码
#define inf 0x3f3f3f3f
int d[101][101];
void addedge(int u,int v,int w){
d[u][v]=w;
}
void dfs(int u,int fa){
for(int i=1;i<=n;i++){
if(d[u][i]!=inf){
cout<<u<<"->"<<i<<" Val="<<d[u][i]<<endl;
if(i!=fa)dfs(i,u);
}
}
}
优点
- 适合稠密图
- 可以快速判断一条 \((u,v)\) 边是否存在
缺点
- \(\Theta(n^2)\)还是慢了些
- 不支持重边
03 vector
vector YYDS
时间复杂度：
- 遍历（DFS，BFS） \(\Theta(n+m)\)
- 判断是否存在 \(\Theta(m)\)
空间复杂度：
- \(\Theta(m)\)
代码
struct Edge{
int v,w;
Edge(int b,int c){v=b,w=c;}
};
vector<Edge>edge[100010];
void addedge(int u,int v,int w){
edge[u].push_back(Edge(v,w));
}
void bianli(){//用的循环
for(int i=1;i<=n;i++){
if(!a[i].empty()){
for(int j=0;j<a[i].size();j++)cout<<i<<"->"<<a[i][j].to<<" in"<<a[i][j].val<<endl;
cout<<endl;
}
else cout<<i<<endl;
}
}
优点
- 适合稀疏图
- 时间复杂度优秀
- 好写
（最主要的
缺点
- 无法快速的判断是否存在 \((u,v)\) 边
04 链式前向星（邻接表）
好多种叫法。
时间复杂度：
- 遍历（DFS，BFS） \(\Theta(n+m)\)
- 判断是否存在 \(\Theta(m)\)
空间复杂度：
- \(\Theta(m+n)\)
代码
const int maxn=1001,maxm=100001;
struct Edge{
int next;//后继结点
int v;
int val;
};
Edge edge[maxm*2+5];
int first[maxn];//头指针
int vis[maxn];
int cnt,ans,n,m;
void addedge(int u,int v,int w){
cnt++;
edge[cnt].next=first[u];//(1)
edge[cnt].v=v;
edge[cnt].val=w;
first[u]=cnt;//(2)
}
这里其实是和 vector 差不多的链表思路，但是这里使用了定长数组实现。代码中巧妙的地方在于他插入时插入了链表的头部而不是尾部（ (1),(2) 处），避免了遍历整个链表的时间。
优点
- 速度快
- 如果是无向图，则 \(\texttt{这条边的编号}\oplus1=\texttt{这条边的反边编号}\)
缺点
- 还是稍微复杂了点
- 没有
vector简洁