在学习宽度优先算法之前，我们要了解图是怎样在计算机中进行存储的。通常，我们用邻接表对图进行存储。邻接表可以理解为一个很大的表，里面存有图中每个顶点的信息，每一个表项存储了图中的一个顶点，然后通过这一个表项我们可以找到与这个结点相邻的所有顶点。
宽度优先搜索算法是一种遍历图的方法，它的基本思想是：首先访问出发结点v，然后访问与结点v邻接的全部结点（已访问过的结点除外）。以此类推，直到图中所有的结点都被访问到为止，或者出发顶点v所在的连通分量的所有顶点都被访问到为止。 在bfs中，我们要做的步骤如下：
1. 把队列置空
2. 打印出发顶点，置该顶点已被访问的标志
3. 让出发顶点进队
4. a. 取出队首中的顶点v
b.在邻接表中，依次取得与顶点v邻接的各个顶点
i. 若当前取得的邻接顶点未被访问，则
（1）打印该顶点，置该顶点已被访问的标志
（2）该顶点进队
ii.取得下一个邻接顶点
c.转4
5. 若队列空，则处理过程结束
void bfs(int u)//宽度优先搜索
{
int v,w;
L_NODE *t;
QTYPE queue;
printf("%d ",u);
visit[u]=1;//标记第一个已访问结点
queue.qa=0;//队首指针
queue.qe=0;//队尾指针
queue.item[0]=u;//第一个结点入队
while(queue.qa<=queue.qe)//队列不为空
{
v=queue.item[(queue.qa)++];//取队首元素
t=head[v];
while(t!=NULL)//结点t不为空
{
w=t->ver;
if(visit[w]==0)//如果结点未曾被访问过
{
printf("%d ",w);
visit[w]=1;
queue.item[++(queue.qe)]=w;//结点进队
}
t=t->link;//下一个邻接节点
}
}
}