广度优先搜索的算法是：（1）从图中的某个节点v出发，依次访问该顶点的各个未曾被访问的邻接点，然后从这些邻接点出发继续访问它的邻接顶点，直到图中所有结点都被访问到（2）如果图中还有没有访问到的结点，选取一个没有访问到的结点，重复（1），直到所有结点都被访问到。
图中的结点被涂成白色，灰色或者黑色，白色代表结点没有访问过，灰色代表结点被访问到，等到这个结点的所有邻接顶点被访问完时，结点的颜色变为黑色。广度优先搜索使用队列存储被访问到的结点，利用了队列先进先出的性质。
假设有图：
它的广度优先搜索的结果是：
它的广度优先搜索结果是：
ABD CE
（1）邻接矩阵表示 广度优先搜索
# include <iostream>
using namespace std;
# include <stdlib.h>
# include <queue>
# define NUM 10
# define ARG 10
char *color[NUM];
queue <int> q;
struct graph{
int num;
int arc;
int a[NUM][NUM];
char name[NUM];
};
int main()
{
void create(graph &g);
void print(graph &g);
void bfsgra(graph &g);
graph g;
create(g);
print(g);
bfsgra(g);
system("pause");
return 0;
}
int locate(graph &g,char a)
{
int i=0;
for(i=0;i<g.num;i++)
if (g.name[i]==a)
return i;
return -1;
}
void create(graph &g)
{
int i,j;
cout<<"input num of nodes and num of edges"<<endl;
cin>>g.num>>g.arc;
for(i=0;i<g.num;i++)
cin>>g.name[i];
for(i=0;i<NUM;i++)
for(j=0;j<NUM;j++)
g.a[i][j]=-1;
for(i=0;i<g.arc;i++)
{
char a,b;
int i,j,w;
cout<<"input name of nodes"<<endl;
cin>>a>>b>>w;
i=locate(g,a);
j=locate(g,b);
g.a[i][j]=w;
g.a[j][i]=w;
}
}
void print(graph &g)
{
int i,j;
for(i=0;i<g.num;i++){
for(j=0;j<g.num;j++)
cout<<g.a[i][j]<<"\t";
cout<<endl;
}
}
void bfs(graph &g,int i,char *color[])
{
int j,k;
if (color[i]=="white")
{
color[i]="gray";
q.push(i);
}
while(!q.empty())
{
j=q.front();
q.pop();
cout<<j<<endl;
for(k=0;k<g.num;k++)
{
if(color[k]=="white"&&g.a[i][j]>0)
{
color[k]="gray";
q.push(k);
}
}
color[i]="black";
}
}
void bfsgra(graph &g)
{
int i=0;
for(;i<g.num;i++)
color[i]="white";
for(i=0;i<g.num;i++)
bfs(g,i,color);
}
邻接矩阵表示的图，广度优先搜索的复杂度：设有n个点，e条边，邻接矩阵中有n^2个元素，在算法中，共有n个顶点，对每个顶点都要遍历n次，时间复杂度为O(n^2)
（2） 邻接链表表示 图的广度优先搜索
# include <iostream>
using namespace std;
# include <stdlib.h>
# include <queue>
# define NUM 10
int visited[NUM];
char *color[NUM];
queue<int> q; //存储被访问到的结点
struct anode{
int data;
anode *next;
};
struct bnode{
char name;
anode *next;
};
struct graph{
int num;
int arc;
bnode arr[NUM];
};
int main()
{
void print(graph &g);
void create(graph &g);
void bfsgra(graph &g);
graph g;
create(g);
print(g);
bfsgra(g);
system("pause");
return 0;
}
int locate(graph &g,char a)
{
int i=0;
for(;i<g.num;i++)
{
if (g.arr[i].name==a)
return i;
}
return -1;
}
void create(graph &g) //创建图的邻接链表表示
{
cout<<"input the num of nodes and num of edges"<<endl;
cin>>g.num>>g.arc;
int i=0;
for(;i<g.num;i++)
{
cout<<"input the names of node"<<endl;
cin>>g.arr[i].name;
g.arr[i].next=NULL;
}
for(i=0;i<g.arc;i++)
{
char a,b;
cout<<"input node a and node b"<<endl;
cin>>a>>b;
int i=locate(g,a);
int j=locate(g,b);
anode *p=new anode;
p->data=j;
p->next=g.arr[i].next;
g.arr[i].next=p;
}
}
void print(graph &g)
{
int i=0;
while(g.arr[i].next!=NULL&&i<NUM)
{
cout<<g.arr[i].name<<":";
anode *e=g.arr[i].next;
while(e)
{
cout<<e->data;
e=e->next;
}
i++;
cout<<endl;
}
}
void bfs(graph &g,int i,char *color[]) //广度优先搜索某个结点
{ int j;
if(color[i]=="white")
{color[i]="gray";
q.push(i);
}
anode *p=new anode;
while(!q.empty())
{ j=q.front();
q.pop();
cout<<j<<endl;
p=g.arr[j].next;
while(p)
{
if(color[p->data]=="white")
{q.push(p->data);
color[p->data]="gray";
}
p=p->next;
}
color[j]="black";
}
}
void bfsgra(graph &g) //广度优先搜索
{
int i=0;
for (;i<g.num;i++)
color[i]="white";
for(i=0;i<g.num;i++)
bfs(g,i,color);
}
邻接链表表示的图，广度优先搜索的复杂度：如果这个邻接表包含n个头结点和e个表结点，算法中对所有结点遍历，时间复杂度为O(n+e)
原文：http://blog.csdn.net/u011608357/article/details/21321485