作者:白云飞羽_389 | 来源:互联网 | 2023-12-10 15:00
本文介绍了一种图的存储和遍历方法——链式前向星法,该方法在存储带边权的图时时间效率比vector略高且节省空间。然而,链式前向星法存图的最大问题是对一个点的出边进行排序去重不容易,但在平行边无所谓的情况下选择这个方法是非常明智的。文章还提及了图中搜索树的父子关系一般不是很重要,同时给出了相应的代码示例。
链式前向星法存的带边权的图,(尤其在多组数据时)时间效率比vector略高且节省空间,缺点是不容易对一个点的出边进行排序去重,当平行边无所谓时选择这个方法是非常明智的。链式前向星法存图的最大的问题是要记得给反向边预留空间。
图的存储和遍历,在图中搜索树的父子关系其实一般不是很重要。注意下面的代码是没有对vis进行清空的,因为其实并不是每次搜索前都会需要清空,有时候有一些其他的操作(特别是有向图)。需要管边权的去找dijkstra算法就好了。
struct Graph {
static const int MAXN = 200000;
static const int MAXM = 400000;
int n;
int head[MAXN + 5], top;
struct Edge {
int v, w, next;
} edge[MAXM + 5];
void Init(int _n) {
n = _n;
top = 0;
memset(head, 0, sizeof(head[0]) * (n + 1));
}
void AddEdge(int u, int v, int w) {
edge[++top].next = head[u];
edge[top].v = v;
edge[top].w = w;
head[u] = top;
}
bool vis[MAXN + 5];
void dfs(int u, int w) {
vis[u] = 1;
for(int i = head[u]; i; i = edge[i].next) {
int v = edge[i].v;
if(vis[v])
continue;
dfs(v, edge[i].w);
}
}
int que[MAXN + 5], front, back;
void bfs(int s) {
frOnt= 1, back = 0;
vis[s] = 1;
que[++back] = s;
while(front <= back) {
int u = que[front++];
for(int i = head[u]; i; i = edge[i].next) {
int v = edge[i].v;
if(vis[v])
continue;
vis[v] = 1;
que[++back] = v;
}
}
}
} G;
树的存储和遍历,dfs中带有父节点p的编号,树一般就不需要什么bfs了,距离都是唯一的。
struct Graph {
static const int MAXN = 200000;
static const int MAXM = 400000;
int n;
int head[MAXN + 5], top;
struct Edge {
int v, w, next;
} edge[MAXM + 5];
void Init(int _n) {
n = _n;
top = 0;
memset(head, 0, sizeof(head[0]) * (n + 1));
}
void AddEdge(int u, int v, int w) {
edge[++top].next = head[u];
edge[top].v = v;
edge[top].w = w;
head[u] = top;
}
void dfs(int u, int p, int w) {
for(int i = head[u]; i; i = edge[i].next) {
int v = edge[i].v;
if(v == p)
continue;
dfs(v, u, edge[i].w);
}
}
} G;
模板 - 图论 - 图的存储和遍历