三种邻接表存图模板:vector邻接表、数组邻接表、链式前向星

vector邻接表:

const int maxn=1e5+;

struct Edge{
int u,v,w;
Edge(int _u=0,int _v=0,int _w=0){u=_u,v=_v,w=_w;}
};
vector<Edge> E;
vector<int> G[maxn];
void init(int l,int r)
{
E.clear();
for(int i=l;i<=r;i++) G[i].clear();
}
void addedge(int u,int v,int w)
{
E.push_back(Edge(u,v,w));
G[u].push_back(E.size()-);
}

遍历某个链表的方法: for(int i=;i<G[u].size();i++)

最喜欢这种写法,写起来快,也非常好理解。

vector邻接表还有一种魔性写法:

const int maxn=1e5+;

struct Edge{
int u,v,w;
Edge(int u=,int v=,int w=){this->u=u,this->v=v,this->w=w;}
};
vector<Edge> E[maxn];
void init(int l,int r){for(int i=l;i<=r;i++) E[i].clear();}
void addedge(int u,int v,int w){E[u].push_back(Edge(u,v,w));}

其实差不多……属于懒人中的懒人写法。

数组邻接表:

const int maxn=1e5+;
const int maxm=1e5+; struct Edge{
int u,v,w;
Edge(int _u=,int _v=,int _w=){u=_u,v=_v,w=_w;}
Edge(Edge &e){u=e.u,v=e.v,w=e.w;}
};
Edge E[maxm];
int head[maxn],next[maxm],ne;
void init()
{
ne=;
memset(head,,sizeof(head));
}
void addedge(int u,int v,int w)
{
E[++ne]=Edge(u,v,w);
next[ne]=head[u];
head[u]=ne;
}

遍历某个链表的方法: for(int i=head[u];i;i=next[i])

在题目卡vector时可以使用,如果include了STL库,可能next数组会产生ambiguous,需要改个名字或者改用链式前向星(如下)。

链式前向星:

const int maxn=1e5+;
const int maxm=1e5+; struct Edge{
int u,v,w;
int next;
};
Edge E[maxm];
int head[maxn],ne;
void init()
{
ne=;
memset(head,,sizeof(head));
}
void addedge(int u,int v,int w)
{
++ne;
E[ne].u=u, E[ne].v=v, E[ne].w=w;
E[ne].next=head[u];
head[u]=ne;
}

把数组邻接表的next数组扔到Edge结构体里保存,就变成了链式前向星……所以,链式前向星其实就是邻接表。

遍历某个链表的方法: for(int i=head[u];i;i=E[i].next)

上一篇:AOV网与拓扑排序


下一篇:基于AOE网的关键路径的求解