把建立图(其实主要是树)的几种方式说一下吧。。。感觉最近自己有选择恐惧症。
邻接矩阵
远古的存图方式,容易被卡内存
代码实现:
vector<vector<int> >mapn(N,vector<int>(N,0));
// 加边
void addEdge(int a,int b,int weight=1)
{
mapn[a][b]=weight;
}
// 删边(貌似没啥用?
void deleteEdge(int a,int b)
{
mapn[a][b]=0;
}
从一个点出发遍历 就是 O(N) 扫一遍
邻接表
省内存!!!
vector 存图
Emmmm 如果常数卡的不是特别紧可以考虑
代码实现:
vector<int>mapn[N];
// 加边
void addEdge(int a,int b)
{
mapn[a].push_back(b);
}
// 遍历
for(int i=0;i<mapn[u].size();++i)
{
int v=mapn[u][i];
// 后边可以乱搞
}
指针链表
这个是个人偏爱的一种做法,虽然需要申请内存,但是写着很舒服。
常数比vector小,比链式前向星大。
代码实现:
struct Edge
{
int to;
Edge *next;
};
Edge *edges[MAXN];
// 加边
void addEdge(int a,int b)
{
Edge *now=new Edge;
now->to=b;
now->next=edges[a];
edges[a]=now;
}
// 遍历
for(Edge *e=edges[u];e;e=e->next)
{
int v=e->to;
// 下边乱搞
}
链式前向星
和指针链表差不多,不过是把内存提前申请完了,比较省空间。
代码实现:
struct Edge
{
int to;
int next;
}edges[M];
int first[N];
int edges_stamp=0;
// 需要在main()中 memset(first,-1,sizeof(first));
void addedge(int a,int b)
{
edges[edges_stamp].to=b;
edges[edges_stamp].next=first[a];
first[a]=edges_stamp;
edges_stamp++;
}