C言語で実装する幅優先探索の解説：キューを用いたグラフと木の探索アルゴリズム

#include <stdio.h>
#include <stdlib.h>
// ノード構造体
typedef struct Node {
    int data;                     // ノードの値
    struct Node **neighbors;      // 隣接ノードの配列
    int numNeighbors;             // 隣接ノードの数
} Node;

#include <stdio.h>
#include <stdlib.h>
// キュー構造体
typedef struct Queue {
    Node **data;     // ノードのポインタ配列
    int front;       // キューの先頭インデックス
    int rear;        // キューの末尾インデックス
    int size;        // 現在の要素数
    int capacity;    // キューの最大容量
} Queue;

#include <stdio.h>
#include <stdlib.h>
// enqueue関数：キューにノードを追加する処理
void enqueue(Queue *q, Node *node) {
    if(q->size >= q->capacity) {
        // キューの容量が不足した場合の拡張処理
        q->capacity *= 2;
        q->data = (Node**)realloc(q->data, sizeof(Node*) * q->capacity);
    }
    q->data[q->rear] = node;
    q->rear = (q->rear + 1) % q->capacity;
    q->size++;
}
// dequeue関数：キューからノードを取り出す処理
Node* dequeue(Queue *q) {
    if(q->size == 0) return NULL;  // キューが空の場合はNULLを返す
    Node* node = q->data[q->front];
    q->front = (q->front + 1) % q->capacity;
    q->size--;
    return node;
}

#include <stdio.h>
#include <stdlib.h>
// 基本的なノード構造体(簡略化)
typedef struct Node {
    int data;    // ノードの値
} Node;
// キュー構造体
typedef struct Queue {
    Node **data;
    int front;
    int rear;
    int size;
    int capacity;
} Queue;
// キューの初期化関数
Queue* createQueue(int capacity) {
    Queue *q = (Queue*)malloc(sizeof(Queue));
    q->data = (Node**)malloc(sizeof(Node*) * capacity);
    q->front = 0;
    q->rear = 0;
    q->size = 0;
    q->capacity = capacity;
    return q;
}
// enqueue関数
void enqueue(Queue *q, Node *node) {
    if(q->size >= q->capacity) {
        q->capacity *= 2;
        q->data = (Node**)realloc(q->data, sizeof(Node*) * q->capacity);
    }
    q->data[q->rear] = node;
    q->rear = (q->rear + 1) % q->capacity;
    q->size++;
}
int main() {
    Node nodeA = {1};  // 初期ノードの例
    Queue *queue = createQueue(4);
    enqueue(queue, &nodeA);
    printf("Starting node enqueued. Queue size: %d\n", queue->size);
    // メモリの解放
    free(queue->data);
    free(queue);
    return 0;
}

Starting node enqueued. Queue size: 1

#include <stdio.h>
#include <stdlib.h>
#include <stdbool.h>
#define INITIAL_CAPACITY 4
// ノード構造体
typedef struct Node {
    int data;                    // ノードの値
    struct Node **neighbors;     // 隣接ノードの配列
    int numNeighbors;            // 隣接ノードの数
} Node;
// キュー構造体
typedef struct Queue {
    Node **data;    // ノードのポインタ配列
    int front;      // 先頭インデックス
    int rear;       // 末尾インデックス
    int size;       // 現在の要素数
    int capacity;   // 配列の容量
} Queue;
// キューの初期化
Queue* createQueue(int capacity) {
    Queue *q = (Queue*)malloc(sizeof(Queue));
    q->data = (Node**)malloc(sizeof(Node*) * capacity);
    q->front = 0;
    q->rear = 0;
    q->size = 0;
    q->capacity = capacity;
    return q;
}
// キューが空か確認する関数
bool isEmpty(Queue *q) {
    return (q->size == 0);
}
// キューにノードを追加する関数
void enqueue(Queue *q, Node *node) {
    if(q->size >= q->capacity) {
        q->capacity *= 2;
        q->data = (Node**)realloc(q->data, sizeof(Node*) * q->capacity);
    }
    q->data[q->rear] = node;
    q->rear = (q->rear + 1) % q->capacity;
    q->size++;
}
// キューからノードを取り出す関数
Node* dequeue(Queue *q) {
    if(isEmpty(q)) return NULL;
    Node *node = q->data[q->front];
    q->front = (q->front + 1) % q->capacity;
    q->size--;
    return node;
}
// 幅優先探索の実装
void bfs(Node **graph, int numNodes, int start, int target) {
    bool *visited = (bool*)calloc(numNodes, sizeof(bool));
    Queue *queue = createQueue(INITIAL_CAPACITY);
    // 開始ノードをキューに追加
    enqueue(queue, graph[start]);
    visited[start] = true;
    while(!isEmpty(queue)) {
        Node *current = dequeue(queue);
        printf("訪問ノード: %d\n", current->data);
        // 目的のノードに到達した場合、探索を終了
        if(current->data == target) {
            printf("目的のノード %d に到達しました。\n", target);
            break;
        }
        // 隣接ノードを探索
        for (int i = 0; i < current->numNeighbors; i++) {
            int neighborIndex = current->neighbors[i]->data;  // ノード値をインデックスとして利用
            if(!visited[neighborIndex]) {
                visited[neighborIndex] = true;
                enqueue(queue, current->neighbors[i]);
            }
        }
    }
    // メモリの解放
    free(visited);
    free(queue->data);
    free(queue);
}
// メイン関数
int main() {
    int numNodes = 4;
    // ノードの動的確保と初期化
    Node **graph = (Node**)malloc(sizeof(Node*) * numNodes);
    for (int i = 0; i < numNodes; i++) {
        graph[i] = (Node*)malloc(sizeof(Node));
        graph[i]->data = i;
        graph[i]->neighbors = NULL;
        graph[i]->numNeighbors = 0;
    }
    // グラフの構築
    // ノード0: 隣接はノード1, ノード2
    graph[0]->numNeighbors = 2;
    graph[0]->neighbors = (Node**)malloc(sizeof(Node*) * 2);
    graph[0]->neighbors[0] = graph[1];
    graph[0]->neighbors[1] = graph[2];
    // ノード1: 隣接はノード2, ノード3
    graph[1]->numNeighbors = 2;
    graph[1]->neighbors = (Node**)malloc(sizeof(Node*) * 2);
    graph[1]->neighbors[0] = graph[2];
    graph[1]->neighbors[1] = graph[3];
    // ノード2: 隣接はノード3
    graph[2]->numNeighbors = 1;
    graph[2]->neighbors = (Node**)malloc(sizeof(Node*) * 1);
    graph[2]->neighbors[0] = graph[3];
    // ノード3: 隣接はなし
    graph[3]->numNeighbors = 0;
    graph[3]->neighbors = NULL;
    // 幅優先探索を実行(開始ノード0から目的ノード3へ)
    bfs(graph, numNodes, 0, 3);
    // 作成したノードと隣接リストのメモリを解放
    for (int i = 0; i < numNodes; i++) {
        if(graph[i]->neighbors != NULL) {
            free(graph[i]->neighbors);
        }
        free(graph[i]);
    }
    free(graph);
    return 0;
}

訪問ノード: 0
訪問ノード: 1
訪問ノード: 2
訪問ノード: 3
目的のノード 3 に到達しました。