【C言語】トポロジカル・ソートの実装：有向グラフの依存関係を整理するアルゴリズム

#include <stdio.h>
#include <stdlib.h>
#include <stdbool.h>
#define MAX_VERTICES 100
// グラフの頂点を表す構造体
typedef struct Node {
    int vertex;
    struct Node *next;
} Node;
// グラフを表す構造体
typedef struct {
    int numVertices;         // 頂点の数
    Node* adjLists[MAX_VERTICES];  // 各頂点の隣接リスト
    int inDegree[MAX_VERTICES];    // 各頂点の入次数
} Graph;

#include <stdio.h>
#include <stdlib.h>
#include <stdbool.h>
#include <string.h>
#define MAX_VERTICES 100
typedef struct Node {
    int vertex;
    struct Node *next;
} Node;
typedef struct {
    int numVertices;
    Node* adjLists[MAX_VERTICES];
    int inDegree[MAX_VERTICES];
} Graph;
// グラフを初期化する関数
void initializeGraph(Graph *graph, int vertices) {
    graph->numVertices = vertices;
    for (int i = 0; i < vertices; i++) {
        graph->adjLists[i] = NULL;
        graph->inDegree[i] = 0;
    }
}
// ノードを作成する関数
Node* createNode(int vertex) {
    Node *newNode = (Node*)malloc(sizeof(Node));
    newNode->vertex = vertex;
    newNode->next = NULL;
    return newNode;
}
int main() {
    // グラフを初期化する例
    Graph graph;
    int vertices = 6;
    initializeGraph(&graph, vertices);
    // 初期化完了のメッセージを表示する
    printf("Graph initialized with %d vertices\n", vertices);
    return 0;
}

Graph initialized with 6 vertices

#include <stdio.h>
#include <stdlib.h>
#include <stdbool.h>
#define MAX_VERTICES 100
typedef struct Node {
    int vertex;
    struct Node *next;
} Node;
typedef struct {
    int numVertices;
    Node* adjLists[MAX_VERTICES];
    int inDegree[MAX_VERTICES];
} Graph;
typedef struct {
    int items[MAX_VERTICES];
    int front;
    int rear;
} Queue;
void initializeGraph(Graph *graph, int vertices) {
    graph->numVertices = vertices;
    for (int i = 0; i < vertices; i++) {
        graph->adjLists[i] = NULL;
        graph->inDegree[i] = 0;
    }
}
Node* createNode(int vertex) {
    Node *newNode = (Node*)malloc(sizeof(Node));
    newNode->vertex = vertex;
    newNode->next = NULL;
    return newNode;
}
void enqueue(Queue *queue, int value) {
    queue->items[queue->rear++] = value;
}
int dequeue(Queue *queue) {
    return queue->items[queue->front++];
}
bool isQueueEmpty(Queue *queue) {
    return queue->front == queue->rear;
}
// トポロジカル・ソートを実行する関数
void topologicalSort(Graph *graph) {
    Queue queue = {.front = 0, .rear = 0};
    // 入次数が0の頂点をキューに追加
    for (int i = 0; i < graph->numVertices; i++) {
        if (graph->inDegree[i] == 0) {
            enqueue(&queue, i);
        }
    }
    printf("Topological order:\n");
    // キューが空でない間処理を実施
    while (!isQueueEmpty(&queue)) {
        int currentVertex = dequeue(&queue);
        printf("%d ", currentVertex);
        Node *temp = graph->adjLists[currentVertex];
        // 隣接する各頂点の入次数を1減少させる
        while (temp != NULL) {
            graph->inDegree[temp->vertex]--;
            if (graph->inDegree[temp->vertex] == 0) {
                enqueue(&queue, temp->vertex);
            }
            temp = temp->next;
        }
    }
    printf("\n");
}
int main() {
    Graph graph;
    int vertices = 6;
    initializeGraph(&graph, vertices);
    // グラフの辺を登録(例: 5 → 2, 5 → 0, 4 → 0, 4 → 1, 2 → 3, 3 → 1)
    // 各辺の追加と同時に入次数の更新を行う
    graph.adjLists[5] = createNode(2);
    graph.adjLists[5]->next = createNode(0);
    graph.inDegree[2]++;
    graph.inDegree[0]++;
    graph.adjLists[4] = createNode(0);
    graph.adjLists[4]->next = createNode(1);
    graph.inDegree[0]++;
    graph.inDegree[1]++;
    graph.adjLists[2] = createNode(3);
    graph.inDegree[3]++;
    graph.adjLists[3] = createNode(1);
    graph.inDegree[1]++;
    // トポロジカル・ソートの実行
    topologicalSort(&graph);
    return 0;
}

Topological order:
4 5 2 0 3 1

#include <stdio.h>
#include <stdlib.h>
Node* createNode(int vertex) {
    Node *newNode = (Node*)malloc(sizeof(Node));
    if (newNode == NULL) {
        fprintf(stderr, "Memory allocation error for vertex %d\n", vertex);
        exit(EXIT_FAILURE);
    }
    newNode->vertex = vertex;
    newNode->next = NULL;
    return newNode;
}