BFS广度优先遍历
这一小节先用邻接表的存储结构实现BFS和DFS
看一下王道课给的例子
邻接矩阵就是二维矩阵
//图---邻接矩阵法
typedef struct{
char Ver[MaxVertexnum]; //顶点表
int Edge[MaxVertexnum][MaxVertexnum];//边表
int Vexnum,arcnum;//顶点数，边数
}MGraph;
该图对应的邻接矩阵为
·· A BCD E FG H I J K
A 0 1 0 0 1 0 0 0 0 0 0
B 1 0 0 0 0 1 0 0 0 0 0
C 0 0 0 1 0 1 1 0 0 0 0
D 0 0 1 0 0 0 1 1 0 0 0
E 1 0 0 0 0 0 0 0 0 0 0
F 0 1 1 0 0 0 1 0 0 0 0
G 0 0 1 1 0 1 0 1 0 0 0
H 0 0 0 1 0 0 1 0 0 0 0
I -0 0 0 0 0 0 0 0 0 1 1
J -0 0 0 0 0 0 0 0 1 0 1
K -0 0 0 0 0 0 0 0 1 1 0
广度优先遍历的思想很简单，类似于树的层序遍历。
使得遍历的层数尽可能的小。
不知道怎么描述。打个比方
如上图
从1开始的BFS序列为
1 2 5 6 3 7 4 8 9 10 11
#间隔的加粗是同一层的 比如，1是一层 2 5 一层········
从2开始的BFS序列为
2 1 6 5 3 7 4 8 9 10 11
听了王道的课应该容易理解的。
代码
其中用到了队列相比大家都已经很熟悉了。
结点符号我用A B C D E F G H I J K代替了
void BFS(MGraph &G,LinkQueue &Q,int v);
//函数求一个结点的第一个邻接点
int FirstNeighbor(MGraph &G,int v){
int i=0;
for(i=0;i<G.Vexnum;i++){
if(G.Edge[v][i]==1) return i;//找到第一个邻接点，并返回下标
}
return -1;//没找到返回-1，从而退出循环
}
//函数求一个结点的下一个邻接点
int NextNeighbor(MGraph &G,int v,int w){
int i=w;
for(i=w+1;i<G.Vexnum;i++){
if(G.Edge[v][i]==1) return i;//找到下一个邻接点，并返回下标
}
return -1;//没找到返回-1，从而退出循环
}
//BFS调用函数
void BFSTravese(MGraph &G){
for(int i=0;i<G.Vexnum;i++) visited[i]=false;
LinkQueue Q;
InitQueue(Q);
for(int i=0;i<G.Vexnum;i++){
if(!visited[i]) BFS(G,Q,i);
}
}
//BFS函数 调用几次BFS就对应了连通分量的数量
void BFS(MGraph &G,LinkQueue &Q,int v){
int w=0;
printf("%c ",G.Ver[v]);//visited函数我直接输出了
visited[v]=true;
EnQueue(Q,v);
while(!isEmptyQueue(Q)){
DeQueue(Q,v);
for(w=FirstNeighbor(G,v);w>=0;w=NextNeighbor(G,v,w)){
if(!visited[w]){
printf("%c ",G.Ver[w]);
visited[w]=true;
EnQueue(Q,w);
}
}
}
}
DFS深度优先遍历
DFS相对BFS比较简单，用递归的思想实现了。
从1开始的DFS序列：
1 2 6 3 4 7 8 5 9 10 11
一条道走到黑
代码
递归调用的过程，不多赘述了。
void DFS(MGraph &G,int v);
void DFSTraverse(MGraph &G){
for(int i=0;i<G.Vexnum;i++) visited[i]=false;
for(int i=0;i<G.Vexnum;i++){
if(!visited[i]) DFS(G,i);
}
}
void DFS(MGraph &G,int v){
printf("%c ",G.Ver[v]);
visited[v]=true;
int w=0;
for(w=FirstNeighbor(G,v);w>=0;w=NextNeighbor(G,v,w)){
if(!visited[w]) DFS(G,w);
}
}
完整的实现代码
#include<stdio.h>
#include<stdlib.h>
#define MaxVertexnum 11
//队列节点的结构定义
typedef struct Linknode{
int data;
struct Linknode *next;
}Linknode;
//队列首尾指针的定义
typedef struct{
Linknode *front,*rear;
}LinkQueue;
//初始化队列
void InitQueue(LinkQueue &Q){
//带头结点的链队列
Q.front=(Linknode*)malloc(sizeof(Linknode));
Q.rear=Q.front;
Q.front->next=NULL;
}
//入队
void EnQueue(LinkQueue &Q,int p){
//S指向新节点，连接Q.rear后面
Linknode *S=(Linknode*)malloc(sizeof(Linknode));
S->data=p;
S->next=NULL;
Q.rear->next=S;
Q.rear=S;
}
//出队
bool DeQueue(LinkQueue &Q,int &p){
//如果队空就不能出队列了
if(Q.front==Q.rear) return false;
Linknode *q=Q.front->next;
p=q->data;
Q.front->next=q->next;
//刚好最后一个结点出队了，把rear指向头结点从而判空
if(q==Q.rear){
Q.rear=Q.front;
}
free(q);
return true;
}
//判空
bool isEmptyQueue(LinkQueue Q){
if(Q.front==Q.rear) return true;
else return false;
}
bool visited[MaxVertexnum];
//图---邻接矩阵法
typedef struct{
char Ver[MaxVertexnum]; //顶点表
int Edge[MaxVertexnum][MaxVertexnum];//边表
int Vexnum,arcnum;//顶点数，边数
}MGraph;
void input_MGraph(MGraph &G){
int x=0,y=0;
for(int i=0;i<MaxVertexnum;i++) G.Ver[i]=65+i;
for(int i=0;i<MaxVertexnum;i++) printf("%c ",G.Ver[i]);
for(int i=0;i<MaxVertexnum;i++){
for(int j=0;j<MaxVertexnum;j++)
G.Edge[i][j]=0;
}
printf("\n请输入图的顶点数：");
scanf("%d",&G.Vexnum);
printf("请输入图的边数：");
scanf("%d",&G.arcnum);
getchar();
for(int i=0;i<G.arcnum;i++){
printf("请输入图边的无序对：");
scanf("%d,%d",&x,&y);
G.Edge[x-1][y-1]=G.Edge[y-1][x-1]=1;
}
for(int i=0;i<MaxVertexnum;i++){
for(int j=0;j<MaxVertexnum;j++)
printf("%d ",G.Edge[i][j]);
printf("\n");
}
}
void BFS(MGraph &G,LinkQueue &Q,int v);
int FirstNeighbor(MGraph &G,int v){
int i=0;
for(i=0;i<G.Vexnum;i++){
if(G.Edge[v][i]==1) return i;
}
return -1;
}
int NextNeighbor(MGraph &G,int v,int w){
int i=w;
for(i=w+1;i<G.Vexnum;i++){
if(G.Edge[v][i]==1) return i;
}
return -1;
}
void BFSTravese(MGraph &G){
for(int i=0;i<G.Vexnum;i++) visited[i]=false;
LinkQueue Q;
InitQueue(Q);
for(int i=0;i<G.Vexnum;i++){
if(!visited[i]) BFS(G,Q,i);
}
}
void BFS(MGraph &G,LinkQueue &Q,int v){
int w=0;
printf("%c ",G.Ver[v]);
visited[v]=true;
EnQueue(Q,v);
while(!isEmptyQueue(Q)){
DeQueue(Q,v);
for(w=FirstNeighbor(G,v);w>=0;w=NextNeighbor(G,v,w)){
if(!visited[w]){
printf("%c ",G.Ver[w]);
visited[w]=true;
EnQueue(Q,w);
}
}
}
}
void DFS(MGraph &G,int v);
void DFSTraverse(MGraph &G){
for(int i=0;i<G.Vexnum;i++) visited[i]=false;
for(int i=0;i<G.Vexnum;i++){
if(!visited[i]) DFS(G,i);
}
}
void DFS(MGraph &G,int v){
printf("%c ",G.Ver[v]);
visited[v]=true;
int w=0;
for(w=FirstNeighbor(G,v);w>=0;w=NextNeighbor(G,v,w)){
if(!visited[w]) DFS(G,w);
}
}
int main(){
MGraph G;
input_MGraph(G);
LinkQueue Q;
InitQueue(Q);
printf("\n广度优先遍历序列：");
BFSTravese(G);
printf("\n深度优先遍历序列：");
DFSTraverse(G);
return 0;
}
结果展示
给的都是从节点1开始遍历的，如果想从其他地方开始，直接先调用BFS，DFS一次在执行DFSTraverse或者BFSTravese。
