文章目录
一、广度优先遍历定义二、基本实现思想三、代码实现（以图的存储结构邻接表为例）四、示例测试
一、广度优先遍历定义
图的广度优先遍历BFS算法是一个分层搜索的过程，和树的层序遍历算法类同，它也需要一个队列以保持遍历过的顶点顺序，以便按出队的顺序再去访问这些顶点的邻接顶点。
二、基本实现思想
顶点v入队列。当队列非空时则继续执行，否则算法结束。出队列取得队头顶点v；访问顶点v并标记顶点v已被访问。查找顶点v的第一个邻接顶点col。若v的邻接顶点col未被访问过的，则col入队列。继续查找顶点v的另一个新的邻接顶点col，转到步骤（5）。直到顶点v的所有未被访问过的邻接点处理完。转到步骤（2）。
广度优先遍历图是以顶点v为起始点，由近至远，依次访问和v有路径相通而且路径长度为1，2，……的顶点。为了使“先被访问顶点的邻接点”先于“后被访问顶点的邻接点”被访问，需设置队列存储访问的顶点。
三、代码实现（以图的存储结构邻接表为例）
typedef struct _queue
{
int head
, tail
;
vertexType vertex
[MAX_VERTEX
];
} Queue
;
int isEmptyQueue(Queue
*q
)
{
return q
->head
== q
->tail
;
}
int isFullQueue(Queue
*q
)
{
return (q
->head
+ 1)%MAX_VERTEX
== q
->tail
;
}
int enqueue(Queue
*q
, vertexType v
)
{
if (isFullQueue(q
))
return -1;
q
->vertex
[q
->head
] = v
;
q
->head
= (q
->head
+ 1)%MAX_VERTEX
;
return 0;
}
int dequeue(Queue
*q
, vertexType
*v
)
{
if (isEmptyQueue(q
))
return -1;
*v
= q
->vertex
[q
->tail
];
q
->tail
= (q
->tail
+ 1)%MAX_VERTEX
;
return 0;
}
int visited
[MAX_VERTEX
];
int BFS(adjListGraph_p adjGraph
, int i
)
{
int j
;
edgeNode_p e
;
Queue q
;
vertexType v
;
if (visited
[i
])
return -1;
memset(&q
, 0 , sizeof(q
));
printf("vertex: %c\n", adjGraph
->graph
[i
].vertex
);
visited
[i
] = 1;
enqueue(&q
, adjGraph
->graph
[i
].vertex
);
while (!isEmptyQueue(&q
)) {
dequeue(&q
, &v
);
j
= locateGraph(adjGraph
, v
);
if (j
== -1) return -2;
e
= adjGraph
->graph
[j
].fistNode
;
while(e
) {
j
= locateGraph(adjGraph
, e
->vertex
);
if (j
== -1) return -2;
if (!visited
[j
]) {
printf("vertex: %c\n", e
->vertex
);
visited
[j
] = 1;
enqueue(&q
, e
->vertex
);
}
e
= e
->next
;
}
}
return 0;
}
int BFSAdjList(adjListGraph_p adjGraph
)
{
int i
;
for(i
= 0; i
< adjGraph
->numVertex
; i
++)
visited
[i
] = 0;
for(i
= 0; i
< adjGraph
->numVertex
; i
++) {
if (!visited
[i
]) {
BFS(adjGraph
, i
);
}
}
return 0;
}
四、示例测试
测试代码：
int main()
{
adjListGraph_s g
;
memset(&g
, 0, sizeof(g
));
crateAdjListGraph(&g
);
printf("打印图:\n");
printfGraph(&g
);
printf("深度优先遍历:\n");
DFSAdjList(&g
);
printf("广度优先遍历:\n");
BFSAdjList(&g
);
return 0;
}
测试结果：
关注公众号"小败日记"，搬砖过程遇到的问题，大家一起探讨，资源共享
