图的深度优先与广度优先

1、图的存储方式

树是一种特殊的图，是无环连通图。

图分为有向图与无向图，无向图可以看成两条有向边连接的图

所以只用考虑有向图

有向图的表示分为邻接矩阵，邻接表

邻接矩阵是开个二维数组，存放两个点的关系。

邻接表是链表，存这个点可以到达哪些点，顺序不重要

插入点是插到最前面

所以可以用链表存储

2、图的遍历

（1）深度优先遍历

1、思路

先一条路走到头，然后回溯一下换另一个点走到头，再回溯再走，直到所有点都被走过一遍

2、代码模板

#include<iostream>
#include<cstring>
#include<algorithm>

using namespace std;

const int N=1e5+10;
const int M=2*N;

int n,m; 
int h[N],e[M],ne[M],idx;//h存N个链表的链表头节点的下标，e存每个节点的值是多少，ne存下个节点的位置
bool st[N];				//存储当前点是否被搜过，一般题只过一次 
int ans=N; 				//题上最小的最大值 

void add(int a,int b)	//插入一条a到b的边
{
	e[idx]=b;			//先记下值 
	ne[idx]=h[a];		//让插进来的数指向头节点原来指向的数 
	h[a]=idx++;			//更新当前链表的头节点下标 	
} 
//以n为根节点的子树中，点的数量 
int dfs(int u)
{
	st[u]=true;			//true代表已经被搜过了
	int sum=1;			//点的数量 
	int res=0;			//连通块的最大值 
	for(int i=h[u];i!=-1;i=ne[i])//按照下标遍历 
	{
		int j=e[i];				//j记录一下当前点对应原图中的点
		if(!st[j])				//如果没有被搜过
		{
			int s=dfs(j);		//继续深入，一条路走到底,s记录当前点的数量
			res=max(res,s);
			sum+=s;				//当前的根节点也算上
			 
		}				
	} 
	res=max(res,n-sum);		
	ans=min(ans,res);
	return sum;		
} 

int main()
{
	cin>>n;
	memset(h,-1,sizeof h);//将所有头节点的值设为-1
	for(int i=0;i<n-1;i++)
	{
		int a,b;
		cin>>a>>b;
		add(a,b);
		add(b,a);
	}
	dfs(1);				  //从哪个点开始搜都一样的 
	cout<<ans<<endl;		
}

3、题目

（2）宽度优先遍历

1、思路

2、代码模板

#include<iostream>
#include<cstring>
#include<algorithm>
using namespace std;

typedef pair<int,int> PII;

const int N=1e5+10;
int n,m;
int h[N],e[N],ne[N],idx;
int d[N],q[N];				//d是距离,q是队列

void add(int a,int b)
{
	e[idx]=b;
	ne[idx]=h[a];
	h[a]=idx++;
}

int bfs()
{
	int hh=0,tt=0;			//hh是队列头，tt是队尾 
	q[0]=1;					//起点是1 
	memset(d,-1,sizeof d);	//将距离都初始为-1 
	d[1]=0;					//1这个点距离起点为0，因为1就是起点 
	while(hh<=tt)			//当队列不空时
	{
		int t=q[hh++];		//t存储当前队头的点 
		for(int i=h[t];i!=-1;i=ne[i])//遍历与表头相邻的点 
		{
			int j=e[i];			//记录当前的点 
			if(d[j]==-1)		//要是点没有入队过 
			{
				d[j]=d[t]+1;	//记录距离 
				q[++tt]=j;		//入队 
			}
		}	
	}
	return d[n];				//返回答案的距离 
}

int main()
{
	cin>>n>>m;
	memset(h,-1,sizeof h);//初始化所有表头 
	for(int i=0;i<m;i++)	//用链表存储每条边 
	{
		int a,b;
		cin>>a>>b;
		add(a,b);	
	} 
	cout<<bfs()<<endl;
	return 0;
}

3、题目

4、应用——拓扑序列

只有有向图有

拓扑序列的所有的边都是从前指向后的

证明过了：所有的有向无环图都存在拓扑序列，又称拓扑图

一个有向无环图，至少存在一个入度为0的点

所有入度为0的点都可以排在当前最前面的位置，

所以第一步：把所有入度为9的点入队。

然后就是宽搜的过程

#include<iostream>
#include<algorithm> 
#include<cstring>
using namespace std;

const int N=1e5+10;
int n,m;
int h[N],e[N],ne[N],idx;
int q[N],d[N];				//q是队列，d是当前点的入度
 
void add(int a,int b)		//储存每个点可以到达的点 
{
	e[idx]=b;
	ne[idx]=h[a];
	h[a]=idx++;
}

bool topsort() 
{
	int hh=0,tt=-1;
	for(int i=1;i<=n;i++)		//遍历n个点 
		if(!d[i])				//当该点入度为0时 
			q[++tt]=i;			//入队 
	while(hh<=tt)
	{
		int t=q[hh++];
		for(int i=h[t];i!=-1;i=ne[i])
		{
			int j=e[i];
			d[j]--;
			if(d[i]==0)
				q[++tt]=j;	
		}	
	} 
	return tt==n-1;				//当tt=n-1时，n-1个点都进入队列了 
}

int main()
{
	cin>>n>>m;
	memset(h,-1,sizeof h);
	for(int i=0;i<m;i++)
	{
		int a,b;
		cin>>a>>b;
		add(a,b);
		d[b]++;			//一条a到b的边，b入度+1 
	}
	if(topsort())
	{
		for(int i=0;i<n;i++)//q存的就是拓扑排序 
			printf("%d ",q[i]);
		puts(""); 
	}
	else
		puts("-1");
	return 0;
}

题目：