[数据结构与算法]图的深度优先遍历和广度优先遍历

#include<bits/stdc++.h>
#include<iostream>
#include<algorithm>
using namespace std;
const int N = 1e5+9;
int g[1009][1090];
int head[N];
int cnt;
bool visit[N]; 
void addG(int a,int b)
{
	g[a][b] = 1;
}
struct node
{
	int ne;
	int to;
};
node e[N];
void add(int u,int v)
{
	e[++cnt].to = v;
	e[cnt].ne = head[u];
	head[u] = cnt;
}
queue<int>q;
void dfs(int u)
{
	visit[u] = 1;
	cout<<u<<" ";
	for(int i = head[u];i;i = e[i].ne)
	{
		int tmp = e[i].to;
		if(!visit[tmp]){
			visit[tmp] = 1;	
			dfs(tmp);
		}
	}
}
void bfs(int u)
{
	q.push(u);
	cout<<u<<" ";
	visit[u] = 1;
	while(!q.empty())
	{
		int t = q.front(); 
		//cout<<t<<" ";
		q.pop();
		for(int i = head[t];i;i = e[i].ne)
		{
			int j = e[i].to;
			if(!visit[j])
			{
				q.push(j); 
				visit[j] = 1;
				cout<<j<<" ";
			}
		}
	}
}
int main()
{
	cout<<"请输入分别输入点数和输入边数"<<endl; 
	int n,m;
	cin>>n>>m;
	cout<<"请输入分别输入边数和边数之间的连接"<<endl; 
	for(int i =1;i<=m;++i)
	{
		int a,b;
		cin>>a>>b;
		add(a,b);	
		add(b,a); 
		addG(a,b);
		addG(b,a);
	}
	int u;
	cout<<"请输入你要开始遍历的结点"<<endl; 
	cin>>u;
	cout<<endl;
	cout<<"接下来输出广度优先遍历"<<endl; 
	bfs(u);
	cout<<endl;
	memset(visit,0,sizeof visit);
	cout<<"请输入你要开始遍历的结点"<<endl;
	cin>>u;
	cout<<"接下来输出深度度优先遍历"<<endl;
	dfs(u);
	return 0;
}