首页 > 代码库 > BFS—— Breadth First Search 广度优先算法
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.com
code 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 3
struct 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.com
code 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 = http://www.mamicode.com/to_v;>
init_graph.c
/************************************************************
code file : init_graph.c
code writer : EOF
code date : 2014.11.22
e-mail : jasonleaster@gmail.com
code 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 relationship
for(temp = 0;temp < num_vertex;temp++)
{
p_graph->adjacent[temp].value = http://www.mamicode.com/temp;>
init_table.c
/************************************************************
code file : init_table.c
code writer : EOF
code date : 2014.11.23
e-mail : jasonleaster@gmail.com
code 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.com
code 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 data
If 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 = http://www.mamicode.com/number;>
/***********************************************************************
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.com
code 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.com
code 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.com
code 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 广度优先算法
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。