图的dfs遍历和bfs遍历

dfs遍历，（依次输出遍历顶点)：

用邻接矩阵存图（用一个二维数组把图存起来）！

<span style="font-size:18px;">#include<stdio.h>
#define MAX 9999999//当顶点之间不相通时，标记为一个很大的数
int sum=0;//记录遍历的顶点的个数
int v,s;//顶点数和边数
int book[50]={0},p[30][30];//标记数组和矩阵
void dfs(int k)
{
	printf("%d ",k);//打印顶点
	if(sum==v)//如果已遍历的顶点数等于总顶点数，则退出
	return ;
	for(int count=1;count<=v;count++)//对所有的顶点进行遍历，看哪一个和这个顶点有关系
	{
		sum++;
		if(book[count]==0&&p[k][count]==1)//既没有被访问过，而且和当前顶点还有关系
		{
			book[count]=1;//把此顶点进行标记
			dfs(count);//接着对下一个顶点进行深度搜索
		}
	}
}
int main(void)
{
	int x,y;
	scanf("%d%d",&v,&s);//输入顶点和边数
	for(int i=1;i<=v;i++)
	for(int j=1;j<=v;j++)
	{
		p[i][i]=0;//顶点自己到自己设置为0
		p[i][j]=MAX;//其余的暂且都设置为最大值
	}
	for(int k=1;k<=s;k++)//输入边数
	{
		scanf("%d%d",&x,&y);
		p[x][y]=1;//因为是无向图，所以如果x到y有通路，那么y到x也有通路
		p[y][x]=1;
	}
	book[1]=1;//把第一个顶点标记为已访问
	dfs(1);//从第一个顶点开始深搜
	return 0;
}</span>

图的bfs遍历：

<span style="font-size:18px;">#include<stdio.h>
#define MAX 9999999//此处只是相对的最大值 

int main(void)
{
	int queue[50];//必须保证能存放所有的顶点 
	int book[50]={0};//标记数组 
	int p[50][50];
	int v,s,head=1,tail=1,a,b;//把头尾指针初始化为 1 
	scanf("%d%d",&v,&s);
	for(int i=1;i<=v;i++)//存图的矩阵是一个正方形 
	for(int j=1;j<=v;j++)
	{
		p[i][i]=0;//主对角线都是0，因为是自身到自身 
		p[i][j]=MAX;
	}
	for(int k=1;k<=s;k++)
	{
		scanf("%d%d",&a,&b);
		p[a][b]=1;
		p[b][a]=1;
	}
	queue[tail]=1;//第一个顶点入队 
	book[1]=1;
	 tail++;
	 while(head<tail) 
	 {
	 	for(int k=1;k<=v;k++)
		 {
		 	if(book[k]==0&&p[queue[head]][k]==1)//既没有被标记，又和当前顶点有关系 
		 	{
		 		queue[tail]=k;//当前顶点入队 
		 		book[k]=1;
		 		tail++;
		 	}
		 } 
		 head++;	
	 }
	 for(int k=1;k<tail;k++)//注意；虽然是出队，但是并没有删除，只是指针向后移，而暂且用不到前面的数据，所以前面的数据仍然可以输出 
	 {
	 	printf("%d ",queue[k]);
	 }
	 printf("\n");
	 return 0;
}</span>

图的dfs遍历和bfs遍历

原文：http://blog.csdn.net/u013240038/article/details/45174395