幅優先探索を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