目录
一、链式前向星存图:（n个点，n-1条边）
链式前向星把上面的树图存下来，输入：
9 ///代表要存进去n个点
1 2 ///下面是n-1条边，每条边连接两个点
1 3
1 7
2 4
4 5
4 6
3 8
3 91、先把链式前向星想成链表，建成后（存双向边）：
（数字代表竖线前的点与后面的点相连，1-2、1-3 都是表示边。 注意：链表并不是只建立一条，而是对每个点都建且只建一个）
2、因为链表的建立或者是插入都不是特别简单，直接用链表不太可行，链式前向星就是用数组模拟的链表（就像队列、单调栈都是用数组模拟的，比较简单）。
链表包含head指针和data，因此用数组head[]代替指针，用结构体edge[]代替data存放数据。
a.建立结构体edge[]:
struct node{
int to; ///相连的的点的id
int next; ///指针（说指针可能听不懂，看完就知道了）
}edge[MAX+5];b.为了便于链表的遍历，要给数组head[]赋初值-1：
void init()
{
memset(head,-1,sizeof(head));
ans=0; ///ans表示总共n-1条边，现在建到第ans条边了。
}3、模拟链表的建立和插入：
往链表中存进去一条边，若原来没有这个点的链表那就要新建一条边，不然就是往已有的链表中插入一条边。
a.新建一条链表：
例如要建1-2这条边:（因为前面没建立点1的链表，所以要新建一个链表）
1）、将数据存入结构体edge中：
2））：将指针指向这个链表：
所以如果想知道1这个点的链表存了什么内容，结构体 edge[head[1]] 中存的就是，所以前面说head[]是个指针。
2、往已经存在的链表中插入一条边：
例如要建1-3这条边:（因为前面建立了点1的链表，所以要把这个边插进去）
1）、把数据存入结构体edge中：
2）、指针指向该链表块：
这样就把链表建好了！！！
代码：
#include<bits/stdc++.h>
using namespace std;
typedef long long LL;
const LL MAX=2e5;
struct node{
LL to;
LL next;
}edge[MAX+5];
LL n,ans;
LL head[MAX+5];
void addedge(LL u,LL v)
{
edge[ans].to=v;
edge[ans].next=head[u];
head[u]=ans++;
}
void init()
{
memset(head,-1,sizeof(head));
ans=0;
}
int main()
{
init(); ///链式前向星存图千万不要忘记先把数组head初始化
cin>>n;
for(LL i=0;i<n-1;i++){
LL u,v;
cin>>u>>v;
addedge(u,v);
addedge(v,u);
}
return 0;
}二、两种遍历方法：
感谢：布衣书生real
#include<bits/stdc++.h>
using namespace std;
typedef long long LL;
const LL MAX=2e5;
struct node{ ///下面是链式前向星存图
LL to;
LL next;
}edge[MAX+5];
LL n,ans;
LL head[MAX+5];
void addedge(LL u,LL v)
{
edge[ans].to=v;
edge[ans].next=head[u];
head[u]=ans++;
}
void init()
{
memset(head,-1,sizeof(head));
ans=0;
}
LL cnt;
LL num[MAX+5];
bool vis[MAX+5];
void dfs(int u) ///递归实现深度优先搜索
{
printf("%d ",u);
vis[u]=true;
for(int i=head[u];~i;i=edge[i].next){
int to=edge[i].to;
if(!vis[to]){
dfs(to);
}
}
}
void bfs(int u) ///队列实现广度优先搜索
{
queue<int>q;
vis[u]=true;
q.push(u);
while(!q.empty()){
int k=q.front();
q.pop();
printf("%d ",k);
for(int i=head[k];~i;i=edge[i].next){
int to=edge[i].to;
if(!vis[to]){
q.push(to);
vis[to]=true; ///因为不是递归实现，所以每次放入队列后都需要立即标记。
}
}
}
}
int main()
{
init();
cin>>n;
for(LL i=0;i<n-1;i++){
LL u,v;
cin>>u>>v;
addedge(u,v);
addedge(v,u);
}
cout<<"dfs:"<<endl;
dfs(1);
memset(vis,false,sizeof(vis));
cout<<endl<<"bfs:"<<endl;
bfs(1);
printf("\n");
cout<<endl;
return 0;
}