本文共 3094 字，大约阅读时间需要 10 分钟。

广度优先搜索定义及其性质

BFS，其英文全称是Breadth First Search。

广度优先搜索算法具有完全性。这意指无论图形的种类如何，只要目标存在，则BFS一定会找到。然而，若目标不存在，且图为无限大，则BFS将不收敛（不会结束）。

广度优先搜索的应用

（1）寻找连接元件

（2）寻找非加权图的两点最短路径 （3）检测二分图

算法思想

将A移出队列 将相邻节点依次加入队列

（1）将B移出队列，如果B有邻接点且未被访问过，将其依次压入队列 （2）将C移出队列，如果C有邻接点且未被访问过，将其依次压入队列 （3）将D移出队列，将其邻接点E压入队列 将D移出队列，将其邻接点H，G依次压入队列 对队列中剩余元素重复相同操作，直至所有元素都被访问过

算法实现

（广度优先一般不用递归形式实现）

以上面那个图为例子

#include 
   
    #include 
    
     #define max 1000typedef int elemtype;int visited[max];typedef char VertexType;//BFS//队列的基本操作 typedef struct QueueNode{	elemtype data;	struct QueueNode *next;}Squeue,*queue;typedef struct{	queue front,rear;}Queue,*LinkQueue;//图的声明typedef struct EdgeNode{    int adjvex;    int value;//权值     struct EdgeNode *next;}EdgeNode;//顶点表结点typedef struct VertexNode{    VertexType data;     //顶点信息     EdgeNode *firstedge; //头指针 }VertexNode,AdjList[max];typedef struct{    AdjList adjlist;     int numVertexes,numEdges;}GraphAdjList,*Mgraph;//创建邻接表void init(LinkQueue Q){	Q->front = Q->rear = (queue)malloc(sizeof(Squeue));	Q->front->next = NULL; }bool isEmpty(LinkQueue Q){	if(Q->front==Q->rear) return true;	else return false;}void EnQueue(LinkQueue Q,elemtype x){	queue s = (queue)malloc(sizeof(Squeue));	s->data = x;	s->next = NULL;	Q->rear->next = s;	Q->rear = s;}bool DeQueue(LinkQueue Q){	if(Q->front == Q->rear) return false;	queue p = Q->front->next;	elemtype x =  p->data;	Q->front->next=p->next;	if(Q->rear==p) Q->rear=Q->front;	free(p);	return true;}void Create(GraphAdjList *G){    int i,j,k;    EdgeNode *p;    printf("输入顶点数和边数:\n");    scanf("%d%d",&G->numVertexes,&G->numEdges);    //输入顶点信息    printf("输入顶点信息:\n");    for(i=0;i
     
      numVertexes;i++){       getchar();       scanf("%c",&G->adjlist[i].data);        G->adjlist[i].firstedge=NULL;           //将指向边表的指针初始化     }     //建立边表    printf("输入边(Vi,Vj)中的下标i,j和权值:\n");     for(k=0;k
      
       numEdges;k++){    	int v = 0;         p=(EdgeNode *)malloc(sizeof(EdgeNode));        scanf("%d%d%d",&i,&j,&v);        p->value = v;        p->adjvex=j;                                //存储弧头         p->next=G->adjlist[i].firstedge;            //头插法插入边结点         G->adjlist[i].firstedge=p;        //下面代码有向图无,无向图有         p=(EdgeNode *)malloc(sizeof(EdgeNode));        p->value = v;        p->adjvex=i;                                //存储弧头         p->next=G->adjlist[j].firstedge;            //头插法插入边结点         G->adjlist[j].firstedge=p;    }   	}	void visit(GraphAdjList *G,int v){	 if(G!=NULL)	printf("%c ",G->adjlist[v].data);	}	void BFS(GraphAdjList *G,int v,LinkQueue Q){		visit(G,v);		visited[v]=1;		 EnQueue(Q,v);		while(!isEmpty(Q)){			DeQueue(Q);			EdgeNode  *p = G->adjlist[v].firstedge;			while(p!=NULL){				if(visited[p->adjvex]!=1){					visit(G,p->adjvex);					visited[p->adjvex] = 1;					EnQueue(Q,p->adjvex);				}				p = p->next;			}		}	}	void BFSTraverse(GraphAdjList *G){		   for(int i=0;i
       
        numVertexes;i++){		   		visited[i] = 0;		   }		  LinkQueue Q;		  init(Q);		  for(int i=0;i
        
         numVertexes;i++){ if(visited[i]!=1) BFS(G,i,Q); } } int main(){ GraphAdjList g; Create(&g); BFSTraverse(&g); return 0;}
        
       
      
     
    
   

转载地址：http://ygqen.baihongyu.com/