树与图的遍历

void dfs(int x){
	v[x]=1;
	for(int i=head[x];i;i=next[i]){
		int y=ver[i];
		if(v[y])continue;
		dfs(y);
	}
}

• 以每个节点第一次被访问的顺序标记

• 刚进入该节点以及递归该节点结束时各记录一下编号

• void dfs(int x){
  	a[++m]=x;//储存dfs序 
  	v[x]=1;
  	for(int i=head[x];i;i=next[i]){
  		int y=ver[i];
  		if(v[y])continue;
  		dfs(y);
  	}
  	a[++m]=x; 
  }
  

• 设节点x这两次编号分别为L[x]与R[x]，则区间[L[x],R[x]]就是以x为根的子树的dfs序

• 自顶向下递推，数组储存

• void dfs(int x){
  	v[x]=1;
  	for(int i=head[x];i;i=next[i]){
  		int y=ver[i];
  		if(v[y])continue;
  		d[y]=d[x]+1;
  		dfs(y);
  	}
  	a[++m]=x; 
  }
  

• 若删除节点p后，能使得产生的最大子树最小化，则节点p为子树的重心

• void dfs(int x){
  	v[x]=1;
  	size[x]=1;//子树x的大小 
  	int max_part=0;//删掉x后的最大子树大小 
  	for(int i=head[x];i;i=next[i]){
  		int y=ver[i];
  		if(v[y])continue;
  		dfs(y);
  		size[x]+=size[y];//从子节点向父节点递推 
  	}
  	max_part=max(max_part,n-size[x]);//n为整棵树的节点数
  	if(max_part<ans){
  		ans=max_part;
  		pos=x;
  	} 
  	a[++m]=x; 
  }
  

• void dfs(int x){
  	v[x]=cnt;
  	for(int i=head[x];i;i=next[i]){
  		int y=ver[i];
  		if(v[y])continue;
  		dfs(y);
  	}
  }
  for(int i=1;i<=n;i++){//主程序中 
  	memset(v,0,sizeof(v));
  	if(!v[i]){
  		cnt++;
  		dfs(i);
  	}
  }
  

void bfs(){
	memset(d,0,sizeif(d));
	queue<int>q;
	q.push(1);
	d[1]=1;
	while(!q.empty()){
		int x=q.front();q.pop();
		for(int i=head[x];i;i=next[i]){
			int y=ver[i];
			if(d[y])continue;
			d[y]=d[x]+1;
			q.push(y); 
		}
	}
}

• 给定一张有向无环图，若一个由图中所有点构成的序列A满足：对于给定的边（x,y），x在A中都出现在y之前，则称A时该有向无环图定顶点的一个拓扑序列。
• 我们只要不断选择图中入度为0的点，将其连向的边的入度减一。
  1. 建立空的拓扑序列。
  2. 预处理出所有点的入读deg[i],起初把所有入读为0的点入队。
  3. 取出队头节点x，把x加入拓扑序列A的末尾。
  4. 对于从x出发的每条边（x,y),把deg[y]–。若被减为0，则把y入队。
  5. 重复第第3~4步直到队列为空为止。

     void add(int x,int y){
     	ver[++tot]=y;
     	next[tot]=head[x];
     	head[x]=tot;
     	deg[y]++;
     }
     void topsort(){
     	queue<int>q;
     	int cnt=0;
     	for(int i=1;i<=n;i++)
     		if(deg[i]==0)q.push(i);
     	while(q.size()){
     		int x=q.front();q.pop();
     		a[++cnt]=x;
     		for(int i=head[x];i;i=next[i]){
     			int y=ver[i];
     			if(--deg[y]==0)q.push(y);		
     		}
     	}
     }
     int main(){
     	cin>>n>>m;
     	for(int i=1;i<=n;i++){
     		int x,y;
     		cin>>x>>y;;
     		add(x,y);
     	}
     	topsort();
     	for(int i=1;i<=cnt;i++)cout<<a[i]<<" ";
     	cout<<endl;
     }

•  拓扑排序可以判定有向图中是否存在环。我们可以对任意有向图执行上述过程，完成后检查A的长度。若A序列的长度小于图中点的数量，则说明某些节点未被遍历，进而说明图中存在环。