前言：图的遍历是指对图的所有顶点按一定的顺序进行访问，遍历方法一般有两种，深度优先搜索（DFS）和广度优先搜（ BFS）。
一、深度优先搜索（DFS）遍历图
1.DFS遍历图
深度优先显然是以深度作为关键词进行遍历，每次都是沿着路径到不能再前进时才回退到最近的岔路口 ，就像走迷宫一样，一直沿着一条路走，直到碰到走不通的通道然后回到上一个最近的路口。
2.用邻接矩阵实现DFS遍历图
不明白邻接矩阵存储图的可以去看上一篇博客。
#define maxv 1000
int n,G[maxv][maxv];
bool vis[maxv]={false};
void DFS(int visit)
{
vis[visit]=true;//设置visit顶点已经被访问标志
for(int v=0;v<n;v++)//访问与点visit相连的全部顶点
{
if(vis[v]==false&&G[visit][v]!=inf)//若v未被访问且visit可以到达v
DFS(v);//要说明的一点是DFS（）里面的参数不固定，可以根据题目需要添加参数，例如每
连通块中含有的顶点个数等。
}
}
void DFSTrave()//遍历整个图
{
for(int i=0;i<n;i++)//对于图的每一个顶点
{
if(vis[i]==false)//如果顶点i未被访问
DFS(i);//调用dfs访问i所在的连通块，不懂什么是连通块的可以先百度一下联通分量和强
联通分量的概念
}
}
3.用邻接表实现DFS遍历图
vector<int> adj[maxv];
int n;
bool vis[maxv]={false};
void DFS(int visit)
{
vis[visit]=true;
//如果要对visit进行一些操作可以在此处进行
for(int j=0;j<adj[visit].size();j++)//根据邻接表的特点访问与顶点visit相连接的所有顶点
与邻接矩阵的访问不相同的地方就在于此，可以对比
邻接矩阵进行理解记忆
{
int v=adj[visit][j];
if(vis[v]==false)
DFS(v);
}
}
void Trave()
{
for(int u=0;u<n;u++)
{
if(vis[u]==false)
DFS(u);
}
}
二、广度优先搜索（BFS）遍历图
1.BFS遍历图
与dfs不同的是使用bfs遍历图的时候需要使用一个队列，通过反复取出队首顶点，将该顶点可到达的未曾加入过队列的顶点（不是未曾访问过的顶点）全部入队，直到队列为空时遍历结束。
2.邻接矩阵实现BFS
//可对比dfs的邻接矩阵实现方法和下面的bfs的邻接表实现方法，此处不再做详细讲解
int n,G[maxv][maxv];
bool vis[maxv]={false};
void BFS(int visit)
{
queue<int> q;
q.push(visit);
vis[visit]=true;
while(!q.empty())
{
int u=q.front();
q.pop();
for(int v=0;v<n;v++)
{
if(vis[v]==false&&G[u][v]!=INF)
{
q.push(v);
vis[v]=true;
}
}
}
}
void Trave()
{
for(int i=0;i<n;i++)
{
if(vis[i]==false)
BFS(i);
}
}
3.邻接表实现BFS
#define maxv 1000
vector<int> vec[maxv];
int vis[maxv];
void BFS(int visit)
{
queue<int> q;//定义一个队列
q.push(visit);//当前定点入队
vis[visit]=1;//进行标记
while(!q.empty())//如果对列为空则访问此连通块结束
{
int u=q.front();//取出队首元素
q.pop();//将队首顶点出队
for(int v=0;v<vec[u].size();v++)//访问u能到达的每一个顶点
{
int j=vec[u][v];
if(vis[j]==0)//如果没有入过队列，就将其加入到队列当中
{
vis[j]=1;
q.push(j);
}
}
}
}
void Trave()//遍历图的每一个顶点，和dfs类似
{
for(int i=0;i<n;i++)
{
if(vis(i)==false)
BFS(i);
}
}
更完~~~~~~~~~~~~~
