本文主要是介绍BFS—— Breadth First Search 广度优先算法，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！
Breadth First Search
BFS家伙还是很有用的，特地从wiki扒了一个动态的图，来帮助感性的理解这个动态搜索的过程。
对于如下一个无权值的有向图，在进行广度优先搜索呢？这里我们的代码实现是，以节点３为入口
对于BFS的理论基础介绍，个人觉得还是看《DSAA》比较好.这里不做介绍，注重分析该搜索算法的实现。
如果对于图这种数据结构不熟悉，这个BFS一般是搞不定的...
下面分别是无向图的邻接表实现和邻接矩阵实现
http://blog.csdn.net/cinmyheart/article/details/41381845
http://blog.csdn.net/cinmyheart/article/details/41370465
－－－－－－－－－－－－－－－－－－－－－－－－－－－－－－－－－－－－－－－－－－－－－
如果看过上面的图的实现，看下面的代码应该是非常“熟悉”的。很部分都是在上面的图基础上修改而来的。
首先我们，这里对图进行抽象，然后把关键的实现的API 放到头文件中。
/************************************************************
code file : BFS.h
code writer : EOF
code date : 2014.11.22
e-mail : jasonleaster@gmail.comcode description:This file is a header file for out test program.
We are using digraph but not undirected graph in BFS.************************************************************/#ifndef _BFS_H_
#define _BFS_H_#include <stdio.h>#include <stdlib.h>#define CONNECTED 1#define DISCONNECTED 0#define SUCCESS 0#define FAILED -1#define QUEUE_SIZE 10#define ARRAY_SIZE 20#define EMPTY_QUEUE -1#define UNEMPTY_QUEUE 0 /*** We use these macro as index for struct table*/#define KNOW_OFFSET 0 //vertex that have been found#define DIST_OFFSET 1 //distance of vertex#define PATH_OFFSET 2 //parent vertex of current vertex#define FOUND 1#define NOT_FOUND 0/*** Liitle trick. I use minus one to ** represent positive infinite :)*/#define INFINITE -1#define ENTRY_POINT 3struct node{struct node* previous;struct node* next;int data;};struct vertex{int value;struct vertex* next;struct vertex* end;};struct graph{int num_vertex;int num_edge;struct vertex adjacent[0];};struct table{int height;int width;int msg[0];//we store message of table in this array.};void unweighted_path(struct table* p_table,struct graph* p_graph);struct graph* init_graph(int vertex,int edge);void release_graph(struct graph* p_graph);int add_edge(struct graph* p_graph,char from_v,char to_v);int print_graph(struct graph* p_graph);/*** Creat and desctory a table which's size is row*col.*/struct table* init_table(int row,int col);void table_print(struct table* p_table);void release_table(struct table* p_table);/*** I implement some API to use ADT-Queue*/int queue_destory(struct node* p_queue_tail);int queue_enter(struct node** pp_queue_header,struct node** pp_queue_tail,int number);int queue_init(struct node** pp_queue_header,struct node** pp_queue_tail);int queue_out(struct node** pp_queue_header,struct node** pp_queue_tail);void queue_print(struct node* p_queue_tail);#endifadd_edge.c
/************************************************************
code file : add_edge.c
code writer : EOF
code date : 2014.11.22
e-mail : jasonleaster@gmail.comcode description:This function will help us to add a new connection
between different vertex which is in the graph.*************************************************************/
#include "BFS.h"int add_edge(struct graph* p_graph,char from_v,char to_v)
{if(!p_graph || from_v < 0 || to_v < 0){return FAILED;}struct vertex* p_to_v = (struct vertex*)malloc(sizeof(struct vertex));if(!p_to_v){printf("malloc failed in function %s()\n",__FUNCTION__);return FAILED; }if(!(p_graph->adjacent[from_v].end)){p_graph->adjacent[from_v].next = p_to_v;p_graph->adjacent[from_v].end = p_to_v;p_to_v->next = NULL;p_to_v->value = to_v;}else{p_graph->adjacent[from_v].end->next = p_to_v;p_graph->adjacent[from_v].end = p_to_v;//update the new end node.p_to_v->next = NULL;p_to_v->value = to_v;}return SUCCESS;
}init_graph.c
/************************************************************
code file : init_graph.c
code writer : EOF
code date : 2014.11.22
e-mail : jasonleaster@gmail.comcode description:This function is used for initializing the graph
with inputed parameter @vertex and @edge.************************************************************/
#include "BFS.h"struct graph* init_graph(int num_vertex,int num_edge)
{if(num_vertex <= 0 || num_edge <= 0){return NULL;}struct graph* p_graph = NULL;p_graph = (struct graph*)malloc(sizeof(struct graph) +\num_vertex*sizeof(struct vertex));if(!p_graph){printf("malloc failed in function %s()\n",__FUNCTION__);return NULL;}p_graph->num_vertex = num_vertex;p_graph->num_edge = num_edge;int temp = 0;//initialize the adjacent relationshipfor(temp = 0;temp < num_vertex;temp++){p_graph->adjacent[temp].value = temp;p_graph->adjacent[temp].next = NULL;p_graph->adjacent[temp].end = NULL;}return p_graph;
}init_table.c
/************************************************************
code file : init_table.c
code writer : EOF
code date : 2014.11.23
e-mail : jasonleaster@gmail.comcode description:This function will help us to create a table which's
size is @row multiply @col. And the size of each unit int
this table is sizeof(int).************************************************************/#include "BFS.h"struct table* init_table(int row,int col)
{if(row <= 0 || col <= 0){return NULL;}struct table* p_table = (struct table*)malloc(sizeof(struct table) + row*col*sizeof(int));if(!p_table){return NULL;}p_table->height = row;p_table->width = col;int num_row = row;int num_col = col;//We must initialize the table !for(row = 0;row < num_row;row++){*((int*)(p_table->msg) + row*num_col + KNOW_OFFSET) = NOT_FOUND;if(row != ENTRY_POINT){*((int*)(p_table->msg) + row*num_col + DIST_OFFSET) = INFINITE;}else{*((int*)(p_table->msg) + row*num_col + DIST_OFFSET) = 0;}*((int*)(p_table->msg) + row*num_col + PATH_OFFSET) = 0;}return p_table;
}
/************************************************************
code file : print_graph.c
code writer : EOF
code date : 2014.11.22
e-mail : jasonleaster@gmail.comcode description:This function will print out the connection of graph
which @p_graph point to.************************************************************/#include "BFS.h"int print_graph(struct graph* p_graph)
{if(!p_graph){return FAILED;}int from_v = 0;int to_v = 0;int num_vertex = p_graph->num_vertex;struct vertex* p_vertex = NULL;for(from_v = 0;from_v < num_vertex;from_v++){ p_vertex = &(p_graph->adjacent[from_v]);while(p_vertex){printf("\t%d",p_vertex->value);p_vertex = p_vertex->next;}printf("\n");}return SUCCESS;
}
/******************************************************************
code writer : EOF
code date : 2014.09.13
e-mail : jasonleaster@gmail.com
Attention:Just a implementation of function queue_init. I would be
happy, if my code will help you to know what is queue.
we assuem that ...Input data ---> tail | | |queue| | | header ---> Output dataIf something wrong with my code please touch me by e-mail.*******************************************************************/
#include "BFS.h"int queue_init(struct node** pp_queue_header,struct node** pp_queue_tail)
{(*pp_queue_header) = NULL;(*pp_queue_tail) = NULL;return SUCCESS;
}
/****************************************************************
code writer : EOF
code date: 2014.03.07
e-mail: jasonleaster@gmail.com
code purpose:Just a implementation of function queue_enter. I would be
happy, if my code will help you to know what is queue.
****************************************************************/
#include "BFS.h"int queue_enter(struct node** pp_queue_header ,struct node** pp_queue_tail,int number)
{struct node* p_new_node = NULL;struct node* p_temp_node = NULL;p_new_node = (struct node*)malloc(sizeof(struct node));if(p_new_node == NULL){printf("malloc error!\nqueue enter failed\n");return FAILED;}if(!(*pp_queue_tail)) {*pp_queue_tail = p_new_node;*pp_queue_header = p_new_node;p_new_node->data = number;//Before 2014.11.22, I forgot to add this line and this is a //little bug, but now everything goes right after I adding this :)p_new_node->previous = NULL;p_new_node->next = NULL;}else{p_temp_node = (*pp_queue_tail);p_new_node->data = number;p_new_node->next = p_temp_node;p_new_node->previous = NULL;p_temp_node->previous = p_new_node;(*pp_queue_tail) = p_new_node;}return SUCCESS;
}
/***********************************************************************
code writer : EOF
code date : 2014.09.13
e-mail: jasonleaster@gmail.com
code purpose:Just a implementation of function queue_out. I would be
happy, if my code will help you to know what is queue.If something wrong with my code, please touch me by e-mail.************************************************************************/
#include "BFS.h"int queue_out(struct node** pp_queue_header,struct node** pp_queue_tail)
{struct node* p_temp_node = NULL;int ret = 0;if( !(*pp_queue_header)){/*** There is no way to check the return value.** when we use "queue_out()". So, you needn't to do** that.*/printf("ATTENTION! There is nothing in the queue.\n");return EMPTY_QUEUE;}p_temp_node = (*pp_queue_header);(*pp_queue_header) = (*pp_queue_header)->previous;if(*pp_queue_header)//If there are not only one element left in the queue{(*pp_queue_header)->next = NULL;}else{*pp_queue_tail = NULL;*pp_queue_header = NULL;}ret = p_temp_node->data;free(p_temp_node);p_temp_node = NULL;return ret;
}
/******************************************************************************
code writer : EOF
code date : 2014.03.07
e-mail: jasonleaster@gmail.com
code purpose:Just a implementation of function queue_print. I would be
happy, if my code will help you to know what is queue.If something wrong with my code, please touch me by e-mail.***********************************************************************************/#include "BFS.h"
void queue_print(struct node* p_queue_tail)
{struct node* p_temp_node = NULL;p_temp_node = p_queue_tail;printf("queue data at this time:\n");while(p_temp_node != NULL){printf("%d ",p_temp_node->data);p_temp_node = p_temp_node->next;}printf("\n");
}
/*********************************************************************
code writer : EOF
code date : 2014.03.07
e-mail: jasonleaster@gmail.com
code purpose:Just a implementation of function queue_enter. I would be
happy, if my code will help you to know what is queue.
*******************************************************************/
#include "BFS.h"int queue_destory(struct node* p_queue_tail)
{if(!p_queue_tail){return SUCCESS;}struct node* p_temp_node = NULL;p_temp_node = p_queue_tail->next;while(p_temp_node != NULL){p_queue_tail->next = p_temp_node->next;free(p_temp_node);p_temp_node = p_queue_tail->next;} free(p_queue_tail);return SUCCESS;
}
/************************************************************
code file : release_graph.c
code writer : EOF
code date : 2014.11.22
e-mail : jasonleaster@gmail.comcode description:It's easy and convenient for us to call this API once
and free all the graph.*************************************************************/
#include "BFS.h"void release_graph(struct graph* p_graph)
{if(!p_graph){return ;}int temp = 0;int num_vertex = p_graph->num_vertex;struct vertex* p_temp = NULL;for(temp = 0;temp < num_vertex;temp++){if(p_graph->adjacent[temp].next){p_temp = (p_graph->adjacent[temp].next->next);while(p_temp){free(p_graph->adjacent[temp].next);p_graph->adjacent[temp].next = p_temp;p_temp = p_temp->next;}free(p_graph->adjacent[temp].next);}}free(p_graph);
}
#include "BFS.h"void release_table(struct table* p_table)
{if(!p_table){return;}free(p_table);
}#include "BFS.h"void table_print(struct table* p_table)
{if(!p_table){return;}int row_num = p_table->height;int col_num = p_table->width;int row = 0;int know = 0;int dist = 0;int path = 0;printf("\tknow\tdist\tpath\n");for(row = 0;row < row_num;row++){know = p_table->msg[row*col_num + KNOW_OFFSET];switch(know){case FOUND:{printf("\tFound");break;}case NOT_FOUND:{printf("\tNFond");break;}default:printf("error value of varible @know\n");return;}dist = p_table->msg[row*col_num + DIST_OFFSET];switch(dist){case INFINITE:{printf("\tINF");break;}default:printf("\t%d",dist);}path = p_table->msg[row*col_num + PATH_OFFSET];switch(path){case 0:{printf("\t0");break;}default:printf("\tv%d",path);}printf("\n");}printf("\n\n\n");
}/************************************************************
code file : unweighted_path.c
code writer : EOF
code date : 2014.11.23
e-mail : jasonleaster@gmail.comcode description:This function will do the work of searching.
This job is based on a ADT--Queue. You could read "BFS.h"
and find that decleration of these functions which is used
for Queue.************************************************************/#include "BFS.h"void unweighted_path(struct table* p_table,struct graph* p_graph)
{if(!p_table || !p_graph){return;}struct node* p_queue_tail;struct node* p_queue_header;queue_init(&p_queue_header,&p_queue_tail); queue_enter(&p_queue_header,&p_queue_tail,p_graph->adjacent[ENTRY_POINT].value);int vertex_index = 0;struct vertex* p_vertex = NULL;while(!!p_queue_header){vertex_index = queue_out(&p_queue_header,&p_queue_tail);printf("v%d dequeue\n",vertex_index);*((int*)(p_table->msg)\+ vertex_index*(p_table->width) + KNOW_OFFSET) = FOUND;p_vertex = (struct vertex*)p_graph->adjacent + vertex_index;p_vertex = p_vertex->next;for(;p_vertex;p_vertex = p_vertex->next){if(*((int*)(p_table->msg) \+ (p_vertex->value)*(p_table->width)+ DIST_OFFSET ) == INFINITE){*((int*)(p_table->msg) \+ (p_vertex->value)*(p_table->width)+ DIST_OFFSET ) = \*((int*)(p_table->msg)\+ (vertex_index)*(p_table->width)\+ DIST_OFFSET) + 1;*((int*)(p_table->msg) \+ (p_vertex->value)*(p_table->width)+ PATH_OFFSET ) = vertex_index;queue_enter(&p_queue_header,&p_queue_tail,p_vertex->value);}}table_print(p_table);}queue_destory(p_queue_tail);
}
/****************************************************************
code file : test_graph.c
code writer : EOF
code date : 2014.11.22
e-mail : jasonleaster@gmail.comcode description:This test program is used for testing BFS.*****************************************************************/
#include "BFS.h"int main()
{struct graph* p_graph = NULL;FILE* fp = fopen("./text.txt","r+");if(!fp){printf("fopen() failed!\n");return 0;}int ret = 0;int vertex = 0;int edge = 0;int from_v = 0;int to_v = 0;fscanf(fp,"%d",&vertex);fscanf(fp,"%d",&edge);p_graph = init_graph(vertex,edge);int temp = 0;for(temp;temp < edge;temp++){/*** I think it's necessary to check the returned value** of scanf() family.*/ret = fscanf(fp,"%d %d",&from_v,&to_v);if(ret != 2){break;}add_edge(p_graph,from_v,to_v);}struct table* p_table = init_table(vertex,3);unweighted_path(p_table,p_graph);print_graph(p_graph);release_table(p_table);release_graph(p_graph);fclose(fp);return 0;
}测试用文本文件text.txt:
测试结果：
图的邻接关系表示及实际图对照
由出队的顺序，各个元素出对后的table的情况
最后，所有的节点都会被检索到(０节点不考虑，这里我们初始数据中没有０节点，这是哑节点～)
我们可以知道，Found 0 0 的是入口节点，即节点３，而Found 1 v3，表示距离初始节点有１个edge距离，而该节点的上一个节点为v3, 同样的，Found 3 v4 表示，距离初始节点有３个edge距离，而该节点的上一个节点为v4.
这篇关于BFS—— Breadth First Search 广度优先算法的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！
