BFSアルゴリズムは最短経路を解く
4170 ワード
このBFSアルゴリズムはこうです.
コードは次のように実装されます.
1) queue.h
#ifndef QUEUE_H
#define QUEUE_H
#define MAX_QUEUE_SIZE 100
#ifndef bool
typedef int bool;
#endif
#ifndef true
#define true 1
#endif
#ifndef false
#define false 0
#endif
struct queue;
//typedef void (*queue_init)(struct queue *queue);
typedef bool (*queue_isEmpty)(struct queue *queue);
typedef bool (*queue_isFull)(struct queue *queue);
typedef bool (*queue_enqueue)(struct queue *queue, int data);
typedef bool (*queue_dequeue)(struct queue *queue, int *data);
typedef int (*queue_size)(struct queue *queue);
struct queue
{
int head;
int tail;
int size;
int data[MAX_QUEUE_SIZE];
// queue_init init;
queue_isEmpty isEmpty;
queue_isFull isFull;
queue_enqueue enqueue;
queue_dequeue dequeue;
};
void InitQueue(struct queue *queue);
#endif
queue.c:
#include "queue.h"
static bool isFull(struct queue *queue);
static bool isEmpty(struct queue *queue);
static bool enqueue(struct queue * queue, int data);
static bool dequeue(struct queue *queue, int *data);
void InitQueue(struct queue *queue)
{
queue->head = -1;
queue->tail = -1;
queue->size = 0;
// queue->init = init;
queue->enqueue = enqueue;
queue->dequeue = dequeue;
queue->isEmpty = isEmpty;
queue->isFull = isFull;
}
static bool enqueue(struct queue * queue, int data)
{
if(isFull(queue))
{
return false;
}
queue->tail = (queue->tail + 1) % MAX_QUEUE_SIZE;
queue->data[queue->tail] = data;
queue->size += 1;
return true;
}
static bool dequeue(struct queue *queue, int *data)
{
if(isEmpty(queue) == true)
{
return false;
}
queue->head = (queue->head + 1) % MAX_QUEUE_SIZE;
*data = queue->data[queue->head];
queue->size -= 1;
return true;
}
static bool isFull(struct queue *queue)
{
return queue->size == MAX_QUEUE_SIZE;
}
static bool isEmpty(struct queue *queue )
{
return queue->size == 0;
}
static int size(struct queue *queue)
{
return queue->size;
}
2)BFSコード:
#include "queue.h"
#include <stdio.h>
#ifndef bool
typedef int bool;
#endif
#ifndef true
#define true 1
#endif
#ifndef false
#define false 0
#endif
enum
{
WHITE,
GRAY,
BLACK,
};
struct vertex
{
int id;
int color;
unsigned int dist;
int pi;
};
#define INFINITE ~0
#define MAX_VERTEX 100
#define NIL -1
int matrix[MAX_VERTEX][MAX_VERTEX];
struct vertex vertex[MAX_VERTEX];
void BFS(int s, int size, struct vertex * vertex, int matrx[][MAX_VERTEX])
{
vertex[s].color = GRAY;
vertex[s].dist = 0;
vertex[s].pi = NIL;
struct queue que;
InitQueue(&que);
que.enqueue(&que, s);
while(que.isEmpty(&que) == false)
{
int d;
que.dequeue(&que, &d);
int i,j;
for(i = 1; i <= size; i++)
{
if(matrix[d][i] == 1)
{
if(vertex[i].color == WHITE)
{
vertex[i].color = GRAY;
vertex[i].dist = vertex[d].dist + 1;
vertex[i].pi = i;
que.enqueue(&que, i);
}
}
}
vertex[d].color = BLACK;
}
int i;
for(i = 1; i <= size;i++)
{
printf(" %d to %d shortest dist: %d
", i, s, vertex[i].dist);
}
}
int main(void)
{
int N;
scanf("%d", &N);
int i, j;
for(i = 1; i <= N; i++)
{
vertex[i].color = WHITE;
vertex[i].dist = INFINITE;
vertex[i].pi = NIL;
vertex[i].id = i;
for(j = 1; j <= N; j++)
{
int value;
scanf("%d", &value);
matrix[i][j] = value;
//vertex[i][j].color = WHITE;
//vertex[i][j].dist = INFINITE;
//vertex[i][j].pi = NIL;
}
}
BFS(4, 6, vertex, matrix);
return 0;
}
テストの例は次のとおりです.
出力は次のとおりです.
$ ./bfs < data.txt
1 to 4 shortest dist: 2
2 to 4 shortest dist: 2
3 to 4 shortest dist: 1
4 to 4 shortest dist: 0
5 to 4 shortest dist: 1
6 to 4 shortest dist: 1
data.txtは入力データです.
$ cat data.txt
6
0 1 1 0 0 0
1 0 1 0 0 0
1 1 0 1 0 0
0 0 1 0 1 1
0 0 0 1 0 1
0 0 0 1 1 0