DFS

DFS即深度搜索，每次都沿着路径到不能再前进的时候才退回到最近的岔口。具体不再详细论述。
两个小概念：
（1）连通分量： 在无向图中，如果有两个顶点可以相互到达（可以是通过一定的路径间接到达）那么就称这两个顶点连通。如果图中任意两个点都连通，则称图G为连通图；否则称它为非连通图，且称其中的极大连通子图为连通分量。
（2）强连通分量：在有向图中，如果两个顶点可以各自通过一条有向路径到达另一个顶点，就称这两个顶点强连通。如果图中任意两个顶点都强连通，则称图为强连通图；否则称图为非强连通图，且称其中的极大强连通子图为强连通分量。
伪代码：

DFS(u){
    
vis[u]=true;
	for(从u出发的所有顶点v) //枚举从u出发可以到达的所有顶点v
		if vis[v]=false
		DFS(v);
}
DFSTrave(G){
    
	for(G的所有顶点u）//对G的所有顶点u
		if vis[u]==false
			DFS(u);
}

邻接矩阵模板

int n,G[maxn][maxn];
bool vis[maxn]={
    false};

void DFS(int u,int depth)
{
    
	vis[u]=true;
	for(int v=0;v<n;v++)
	{
    
		if(vis[v]==false&&G[u][v]!=inf)
		DFS(v,depth+1);
	}
}

void DFSTrave()
{
    
	for(int u=0;u<n;u++)
	if(vis[u]==false)
		DFS(u,1);
}

邻接表模板

vector<int> Adj[maxn];
int n;
bool vis[maxn]={
    false};

void DFS(int u,int depth)
{
    
	vis[u]=false;
	for(int i=0;i<Adj[u].size();i++)
	{
    
		int v=Adj[u][i];
		if(vis[v]==false)
			DFS(v,depth+1);
	}
}

void DFSTrave()
{
    
	for(int u=0;u<n;u++)
		if(vis[u]==false)
			DFS(u,1);
}

BFS

即广度优先遍历，每次以扩散的方式向外访问顶点。使用BFS遍历需要一个队列，通过反复取出队首元素将该顶点可以达到的未曾加入过队列的顶点全部入队
伪代码：

BFS(u)
{
    
	queue q;
	将u入队；
	inq[u]=true;
	while(q非空)
	{
    
		取出q的队首元素u进行访问；
		for(从u出发可达的所有顶点v)
		{
    
			if(inf[v]==false)
			{
    
				将v入队;
				inq[v]=true; 
			}
		 } 
	 } 
}

邻接矩阵版

int n,G[maxn][maxn];
bool inq[maxn]={
    false};

void BFS(int u)
{
    
	queue <int> q;
	q.push(u);
	inq[u]=true;
	while(!q.empty())
	{
    
		int u=q.front();
		q.pop();
		for(int v=0;v<n;v++)
		{
    
			if(inq[v]==false&&G[u][v]!INF)
			{
    
				q.push(v);
				inq[v]=true;
			}
		}
	}
}
void BFSTrave()
{
    
	for(int u=0;u<n;u++)
	{
    
		if(inq[u]==false)
			BFS(q);
	}
}

邻接表

vector<int> Adj[maxn];
int n;
bool inq[amxn]={
    false};

void BFS(int u)
{
    
	queue<int> q;
	q.push(u);
	inq[u]=true;
	while(!q.empty())
	{
    
		int u=q.front();
		q.pop();
		for(int i=0;i<Adj[u].size;i++)
		{
    
			int v=Adj[u][i];
			if(inq[v]==false)
			{
    
				q.push(v);
				inq[v]=true;
			}
		}
	}
}
void BFSTrave()
{
    
	for(int u=0;u<n;u++)
	{
    
		if(inq[u]==false)
		{
    
			BFS(q);
		}
	}
}

以上摘自《算法笔记》

#include<iostream>
#include<queue>
using namespace std;
int m[5][5];
int dy[4]={
    0,0,1,-1};
int dx[4]={
    1,-1,0,0};
struct f
{
    
	int x,y;
	int num;
	int path[30][2];
}en;
int k;
void bfs( )
{
    
	queue<f> q;
	f head,temp,now;
	head.x=0; head.y=0;head.num=0;
	q.push(head);
	while(!q.empty())
	{
    
		temp=q.front();
		q.pop();
		for(int i=0;i<4;i++)
		{
    
			now.x=temp.x+dx[i];
			now.y=temp.y+dy[i];
			if(now.x<0||now.x>4||now.y<0||now.y>4||m[now.x][now.y]==1)
			continue;
			if(m[now.x][now.y]==0)
			{
    
				m[now.x][now.y]=1;
				now.path[temp.num ][0]=temp.x;
				now.path[temp.num ][1]=temp.y;
				now.num=temp.num +1;
				q.push(now);
				if(now.x==4&&now.y==4)
				{
    
					now.path[now.num][0]=now.x;
					now.path[now.num][1]=now.y;
					now.num=now.num+1;
					en=now;
					return ;
			 	} 
			}
		}
	}
}
int main( )
{
    
	for(int i=0;i<5;i++)
		for(int j=0;j<5;j++)
			cin>>m[i][j];
			bfs();
			for(int i=0;i<en.num;i++)
			cout<<"("<<en.path[i][0]<<", "<<en.path[i][1]<<")"<<endl;
			return 0;
}