邻接表与DFS,BFS
- 邻接表要开大数组,一般直接2e6+10
邻接表存储树或图
int idx=0;//存储当前可用地址
int h[N];//存储的是头指针数组,N为结点最大总数
fill(h,h+N,-1);//初始化时,要将所有头指针全部指向-1(空指针)
int e[M];//存储的一个地址所对应的结点编号
int ne[M];//存储的是一个地址所对应的结点的next指针
添加一条有向边a->b
void add(int a,int b){
//输入的是a与b的结点编号
e[idx]=b;//申请一块边地址给b
ne[idx]=h[a];//头插法
h[a]=idx++;
}
添加一条无向边:加两次有向边
add(a,b),add(b,a);
dfs遍历
bool vis[N];//表示访问过没有
void dfs(int x){
vis[x]=true;
for(int i=h[x];i!=-1;i=ne[i]){
//遍历所有邻边
int j=e[i];//该地址所对应的结点编号
if(!vis[j]){
//没访问过,则访问
dfs(j);
}
}
}
bfs遍历
int d[N];//记录距离和访问情况,值为-1就还没有访问
void bfs(int x){
queue<int>q;
q.push(x);
d[x]=0;
while(!q.empty()){
int t=q.front();
q.pop();
int distance=d[t];
for(int i=h[t];i!=-1;i=ne[i]){
int j=e[i];
if(d[j]==-1){
//还未访问过
d[j]=distance+1;
q.push(j);
}
}
}
}