スポンサーリンク

幅優先探索をc言語で実装

隣接リスト

隣接リストで、上記の経路を表現します。
深さ優先探索の時と経路は同じにしています。
参考：[c言語]隣接リストで深さ優先探索を実装

#define ROW_MAX 6
#define COL_MAX 3

int pathList[ROW_MAX][COL_MAX] = {
	{0},
	{2, 3, 0},
	{4, 0},
	{6, 0},
	{5, 0},
	{0}
};

通過予定経路を管理するために、下記配列を初期化して用意します。
int route[ROW_MAX];

void initRoute(){
	int i;
	for(i = 0; i < ROW_MAX; i++){
		route[i] = 0;
	}
	
	return;
}

下記が、深さ優先探索のサンプルコードになります。
キューの関数についても実装しています。
下段にサンプルコードとして載せています。
下記で紹介したキューの実装とは少々変えています。
pop()時に値をreturnするようにしたのと、isEmpty()も追加しています。
参考：キューのデータ構造をC言語で実装

引数のstartは探索の開始位置、targetは探索ターゲット位置になります。

void bfs(queue_t* pQueue, int start, int target){
	int row, col, plan;
		
	enqueue(pQueue, start);
	while(!isEmpty(pQueue)){
		row = dequeue(pQueue);
		printf("Route:%d\n", row);
		if(row == target){
			printf("Found target\n");
			return;
		}
		for(col = 0; (plan = pathList[row][col]) != 0; col++){
			if(!route[plan]){
				enqueue(pQueue, plan);
				route[plan] = 1;
			}
		}
	}	
	
	return;	
}

スポンサーリンク

サンプルコード

下記がサンプルコードになります。

 $ cat sample.c 
#include 
#define SIZE 3

enum status{
	EMPTY,
	AVAILABLE,
	FULL
};

typedef struct{
	int data[SIZE];
	int head;
	int tail;
	int flag;
}queue_t;

//キューの中身をprint出力
void printQueue(queue_t* pQueue){
	int i;
	for(i = 0; i <= SIZE - 1; i++){
		printf("%d ", pQueue->data[i]);
	}
	printf("\n");
}

int isEmpty(queue_t* pQueue){
	if(pQueue->flag == EMPTY){
		return 1;
	}
	return 0;
}

int isFull(queue_t* pQueue){
	if(pQueue->flag == FULL){
		return 1;
	}
	return 0;
}

//キューの初期化
void initQueue(queue_t* pQueue){
	int i;
	//キューの中身を0埋め
	for(i = 0; i <= SIZE - 1; i++){
		pQueue->data[i] = 0;
	}
	//初期化
	pQueue->head = 0;
	pQueue->tail = 0;
	pQueue->flag = EMPTY;
	printQueue(pQueue);
}


//enqueue関数
void enqueue(queue_t* pQueue, int value){
	printf("enQ(%d)\n", value);
	//キューがFullの処理
	if(isFull(pQueue)){
		printf("Full\n");
		return;
	}
	//キューがFullでないので、enqueue操作
	pQueue->data[pQueue->tail] = value;
	//リングバッファのため、tailが配列の終端だったら0にする
	if(pQueue->tail == SIZE - 1){
		pQueue->tail = 0;
	//終端でなければ、tailをインクリメント
	}else{
		pQueue->tail++;
	}
	//フラグの更新
	if(pQueue->tail == pQueue->head){
		pQueue->flag = FULL;
	}else{
		pQueue->flag = AVAILABLE;
	}
	printQueue(pQueue);
}

//dequeue関数
int dequeue(queue_t* pQueue){
	int ret = 0;
	
	printf("deQ\n");
	//キューがEmptyの処理
	if(isEmpty(pQueue)){
		printf("Empty\n");
		return 0;
	}
	//キューがEmptyでなければ、dequeue操作
	ret = pQueue->data[pQueue->head];
	pQueue->data[pQueue->head] = 0;
	//リングバッファのため、headが配列の終端だったら0にする
	if(pQueue->head == SIZE - 1){
		pQueue->head = 0;
	//終端でなければ、headをインクリメント
	}else{
		pQueue->head++;
	}
	//フラグの更新
	if(pQueue->tail == pQueue->head){
		pQueue->flag = EMPTY;
	}else{
		pQueue->flag = AVAILABLE;
	}
	printQueue(pQueue);
	
	return ret;
}

#define ROW_MAX 6
#define COL_MAX 3

int pathList[ROW_MAX][COL_MAX] = {
	{0},
	{2, 3, 0},
	{4, 0},
	{6, 0},
	{5, 0},
	{0}
};

int route[ROW_MAX];

void initRoute(){
	int i;
	for(i = 0; i < ROW_MAX; i++){
		route[i] = 0;
	}
	
	return;
}

void bfs(queue_t* pQueue, int start, int target){
	int row, col, plan;
		
	enqueue(pQueue, start);
	while(!isEmpty(pQueue)){
		row = dequeue(pQueue);
		printf("Route:%d\n", row);
		if(row == target){
			printf("Found target\n");
			return;
		}
		for(col = 0; (plan = pathList[row][col]) != 0; col++){
			if(!route[plan]){
				enqueue(pQueue, plan);
				route[plan] = 1;
			}
		}
	}	
	
	return;	
}


int main(){
	queue_t queue;
	queue_t* pQueue = &queue;
	
	initQueue(pQueue);	
	initRoute();
	bfs(pQueue, 1, 6);

	return 0;
}

下記が実行結果になります。
Route:Xが、実際に通過した経路になります。
targetが探索されるとFound targetと表示しています。
 $ gcc -o sample sample.c
 $ ./sample 
0 0 0 
enQ(1)
1 0 0 
deQ
0 0 0 
Route:1
enQ(2)
0 2 0 
enQ(3)
0 2 3 
deQ
0 0 3 
Route:2
enQ(4)
4 0 3 
deQ
4 0 0 
Route:3
enQ(6)
4 6 0 
deQ
0 6 0 
Route:4
enQ(5)
0 6 5 
deQ
0 0 5 
Route:6
Found target

スポンサーリンク