树 - Billchenchina

把建立图（其实主要是树）的几种方式说一下吧。。。感觉最近自己有选择恐惧症。

邻接矩阵

远古的存图方式，容易被卡内存

代码实现：

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++;
}