图的深度优先搜索和广度优先搜索算法

 

DFS和BFS是图论中应用最广泛的两种遍历算法，

DFS 的思想就是不断利用递归，去遍历图。

BFS借助于队列进行遍历，一圈一圈的走

/**
图论算法 
DFS 和BFS的标准代码，以供参考 
*/
#include<iostream>
#include<bits/stdc++.h>
#include<queue> 
using namespace std;//注意命名空间的位置 
const int Max=100;
bool visited[Max];
int G[Max][Max];
int Nv;//dingdianshu
int Ne;//bianshu
queue<int> Q;

//对顶点V进行深度优先搜索 
void DFS(int v)
{
	visited[v]=true;
	cout<<v<<" ";
	for(int i=0;i<Nv;i++)
	{
		if(!visited[i])
		{
			if(G[i][v]||G[v][i])//
			{
				DFS(i);
			}
		}
	}
}
//对顶点V进行广度优先搜索 
void BFS(int v)
{
	visited[v]=true;
	Q.push(v);
	int w;
	while(!Q.empty())
	{
		w=Q.front();
		Q.pop();
		cout<<w<<" ";
		for(int i=0;i<Nv;i++)
		{
			if(!visited[i])
			{
				if(G[i][w]||G[w][i])
				{
					visited[i]=true;//这里代码很关键！
					Q.push(i);
				}
			}
		}
	}
}
int main()
{
	cout<<"输入边数，顶点数"<<endl;
	cin>>Nv>>Ne;
	for(int i=0;i<Max;i++)
	{
		for(int j=0;j<Max;j++)
		{
			G[i][j]=0;
		}
	}
	int V,M;
	for(int i=0;i<Ne;i++)
	{
		cin>>V>>M;
		G[V][M]=1;
		G[M][V]=1;
	}
	memset(visited,false,sizeof(visited));
	cout<<"对图进行广度优先搜索"<<endl;
	for(int i=0;i<Nv;i++)//以免有的图不连通， 
	{
		if(!visited[i])
		{
			cout<<"{";
			BFS(i);
			cout<<"}";
			cout<<endl;
		}
	}
	memset(visited,false,sizeof(visited));
	cout<<"对图进行深度优先搜索"<<endl;
	for(int i=0;i<Nv;i++)
	{
		if(!visited[i])
		{
			cout<<"{";
			DFS(i);
			cout<<"}";
			cout<<endl;
		}
	}
	
	return 0;
}

 

 

测试如下

测试的结果是：