连通图遍历策略之广度优先搜索(c语言)

广度优先搜索(又称宽度优先搜索)算法是最简便的图的搜索算法之一，该算法属于一种盲目搜寻法，目的是系统地展开并检查图中的所有节点，以找寻结果。换句话说，它并不考虑结果的可能位置，彻底地搜索整张图，直到找到结果为止。

广度优先搜素也是很多重要的图的算法的原型。Dijkstra单源最短路径算法和Prim最小生成树算法都采用了和宽度优先搜索类似的思想。

广度优先搜素类似于树的层次遍历，遍历结果不唯一我们依据邻接表进行遍历，还需要借助到链队的内容。

以如下连通图为例：

构建其对应的邻接表：

采用广度优先搜素的遍历顺序如下：

程序运行时并非运行到这里就结束了，而是会继续遍历，只是进行判断的时候visit[i]数组已经置为1，不需要继续输出了。注：为了标定一个·顶点是否被遍历过了，需要采用辅助数组visit[i]进行判定，没当顶点被遍历则将其对应的visit[i]置为1，避免重读。

广度优先搜索步骤：

从某一顶点出发进行访问，该点首先被读入，visit[i]置为1
依次访问该点的邻接点，将其加入队列
对每个邻接点的邻接点进行入队操作

注意：“先访问顶点的邻接点”应先于“后访问顶点的邻接点” 这也是为什么要采用队列这种结构存储的原因：我们需要保证在一次遍历中记录下某一点的全部邻接点，但是每个点却又对应着自己的邻接点，根据广度优先搜索的要求，我们需要保证“先访问顶点的邻接点”应先于“后访问顶点的邻接点”，所以队列是个不错的辅助工具。我们根据队列的顺序就可以找出对应邻接点的位置，进而确定它所对应的邻接点。

队列变化：队列变化图注：红线划去的代表该顶点的visit[i]=1，无需多次加入队列。

广度优先搜索函数代码：

void BFSTraverse(AdjMatrix *G)//广度优先搜索 
{
	LinkQueue Q;
	for(int v=0;v<G->n;++v) 
		visited[v]=false;
	InitQueue(&Q);
	
	printf("广度优先搜索顺序");
	for(int v=0;v<G->n;++v)
	{
	    if(!visited[v])
	    {
		    EnQueue(&Q,v);//将邻接表的顶点元素入队 
		    while(!QueueEmpty(&Q))
		    {
			    int u;      
			    DeQueue(&Q,u);
				if(!visited[u]) 
			    {
					visited[u]=true;
			   		printf("->%c",G->adjlist[u].vertex);
				} 
			    //对该顶点元素的边关系进行遍历，依次入队 
			    for(EdgeNode *w=G->adjlist[u].edgenext;w;w=w->next)
					if(!visited[w->adjvex]) 
						EnQueue(&Q,w->adjvex);
	       	}
			printf("\n\n"); 
	    }
	}
}

具体代码如下：

#include <stdio.h>  
#include <stdlib.h>  
#define  MaxVertices 100
#define MAX_VERTEX_NUM 20
typedef struct node{   //边表 
   int adjvex;
   node* next;  
}EdgeNode;    
typedef struct{     //顶点表  
   int vertex;  
   EdgeNode* edgenext;  
}VertexNode;  
typedef VertexNode AdjList[MaxVertices];  
typedef struct{   
    AdjList adjlist;  
    int n,e;  
}AdjMatrix; 
typedef struct Qnode{       //链队结点的类型
    int data;
    struct Qnode *next;
}Qnode,*QueuePtr;
typedef struct{         //链队指针类型
   QueuePtr front;
   QueuePtr rear;
}LinkQueue;
int visited[MAX_VERTEX_NUM]; 
void InitQueue(LinkQueue *Q)//初始化链队 
{
  	Q->front=Q->rear=(QueuePtr)malloc(sizeof(Qnode));
 	if(!Q->front) 
  		exit(1); //存储分配失败
	Q->front->next=NULL;
 }
void EnQueue(LinkQueue *Q,int e)//入队 
{ 
	QueuePtr p;
  	p=(QueuePtr)malloc(sizeof(Qnode));
 	p->data=e;
 	p->next=NULL;
  	Q->rear->next=p;
  	Q->rear=p;
}
int QueueEmpty(LinkQueue *Q)//判断队空 
{
    return(Q->front==Q->rear? 1:0);
}
void DeQueue(LinkQueue *Q,int &e)//出队 
{ 
	QueuePtr p;
  	if(QueueEmpty(Q))
    {
	    printf("\n Queue is free!");
	    exit(1);
  	}//if
	p=Q->front->next;
	e=p->data;
	Q->front->next=p->next;
	if(Q->front->next==NULL) Q->rear=Q->front;
		free(p);

}
void CreateGraph(AdjMatrix* G)//构造图  
{  
    int i,j,k,w,v;  
    EdgeNode *s;  
    printf("输入顶点数和边数（中间以空格分开）：");  
    scanf("%d%d",&G->n,&G->e);  
  
    printf("建立顶点表\n"); 
    for (i=0;i<G->n;i++)  
    {  
		//fflush(stdin);  
		//如果 stream 指向输入流（如 stdin），那么 fflush 函数的行为是不确定的。
		//故而使用 fflush(stdin) 是不正确的。
		getchar(); 
		printf("请输入第%d个顶点的信息:",i+1);
		G->adjlist[i].vertex=getchar();
		G->adjlist[i].edgenext=NULL;  
    }  
	//前插法 
    printf("建立边表\n");  
    for (k=0;k<G->e;k++)  
    {  
       printf("输入有连接的顶点序号：");  
       scanf("%d%d",&i,&j);  
       //对于直接相连的进行编入(即对输入“0 1”时，在0对应的边表中编入1) 
       i-=1;j-=1; 
       s=(EdgeNode*)malloc(sizeof(EdgeNode));  
       s->adjvex=j;//边表赋值 
       s->next=G->adjlist[i].edgenext;  
       G->adjlist[i].edgenext=s;  
       //对于间接相连的进行编入(即对输入“0 1”时，在1对应的边表中编入0)
       s=(EdgeNode*)malloc(sizeof(EdgeNode));  
       s->adjvex=i;  
       s->next=G->adjlist[j].edgenext;  
       G->adjlist[j].edgenext=s;  
    }  
}   
void DispGraph(AdjMatrix *G)//销毁图 
{
	int i;
	for (i=0;i<G->n;i++)  
    {  
        printf("%d->",i+1);  
        while(1)  
        {             
			if(G->adjlist[i].edgenext==NULL)
            {
            	printf("^");
				break;	
			}
            printf("%d->",G->adjlist[i].edgenext->adjvex+1);  
            G->adjlist[i].edgenext=G->adjlist[i].edgenext->next;  
 
        }  
        printf("\n");  
    }  
}
void BFSTraverse(AdjMatrix *G)//广度优先搜索 
{
	LinkQueue Q;
	for(int v=0;v<G->n;++v) 
		visited[v]=false;
	InitQueue(&Q);
	
	printf("广度优先搜索顺序");
	for(int v=0;v<G->n;++v)
	{
	    if(!visited[v])
	    {
		    EnQueue(&Q,v);//将邻接表的顶点元素入队 
		    while(!QueueEmpty(&Q))
		    {
			    int u;      
			    DeQueue(&Q,u);
				if(!visited[u]) 
			    {
					visited[u]=true;
			   		printf("->%c",G->adjlist[u].vertex);//visit一下
				} 
			    //对该顶点元素的边关系进行遍历，依次入队 
			    for(EdgeNode *w=G->adjlist[u].edgenext;w;w=w->next)
					if(!visited[w->adjvex]) 
						EnQueue(&Q,w->adjvex);
	       	}
			printf("\n\n"); 
	    }
	}
}
int main()  
{  
    //freopen("1.txt","r",stdin);
    AdjMatrix* G= (AdjMatrix*)malloc(sizeof(AdjMatrix));  
    CreateGraph(G);
	BFSTraverse(G);  
    DispGraph(G); 
}

测试数据如下： 注：由于测试输入数据较多，程序可以采用文件输入

5 7 1 2 3 4 5 1 2 1 3 1 4 2 3 2 4 3 5 4 5

n.xuanrui

退无可退，一往无前

连通图遍历策略之广度优先搜索(C语言)