树与图的dfs和bfs（C++）

树是图(树是图的子集)，图不一定是树

树有一个根节点，图没有
树可以递归遍历，图要看情况
树有层次划分，图没有

树是一种“层次”关系，
图是“网络”关系

图可分为有向和无向，也可分为有环和无环，树是有向无环图  

图

 

树与图的存储与深度优先遍历

#include 
#include 
#include 
using namespace std;
const int N = 1000010,M = N*2;
int n;
int h[N],e[M],ne[M],idx;
bool st[N];
int ans = N;

void add(int a,int b)//为两个数据之间增加边，建立图
{
	e[idx] = b , ne[idx] = h[a],h[a] = idx ++;
	
}

int dfs(int u)//深度优先遍历，寻找以u节点为根结点的子结点数量
{
	st[u] = true;
	
	int sum = 1,res = 0;
	for(int i=h[u];i!=-1;i=ne[i])
	{
		int j = e[i];
		if(!st[j])
		{
			int s = dfs(j);
			res = max(res,s);
			sum +=s;
		}
	}
	res = max(res,n-sum);
	
	ans = min(ans,res);
	
	return sum ;
}

int main()
{
	ios::sync_with_stdio(false),cin.tie(0),cout.tie(0);
	memset(h,-1,sizeof h);
	cin >> n;
	int a,b;
	for(int i=0;i> a >> b;
		add(a,b),add(b,a);
	}
	
	dfs(1);
	
	cout << ans < 
 树与图的宽度优先遍历
 
#include 
#include 
#include 
using namespace std;
const int N = 1000010;
int n,m;
int h[N],e[N],ne[N],idx;
int d[N],q[N];

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

int bfs()
{
	int hh = 0,tt = 0;
	q[0] = 1;
	memset(d,-1,sizeof d);
	d[1] = 0;
	while(hh <= tt)
	{
		int t =  q[hh ++ ];
		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()
{
	ios::sync_with_stdio(false),cin.tie(0),cout.tie(0);
	memset(h,-1,sizeof h);
	cin >> n;
	int a,b;
	for(int i=0;i> a >> b;
		add(a,b),add(b,a);
	}
	
	cout << bfs() <