【C言語】第8章第7回：グラフ構造と基本操作

Warning: preg_match(): Compilation failed: regular expression is too large at offset 46000 in /home/wp769435/a-mun.com/public_html/wp-content/plugins/easy-table-of-contents/easy-table-of-contents.php on line 1806

グラフ構造は、ノード（頂点）とそれらを接続するエッジ（辺）で構成される柔軟なデータ構造です。本記事では、グラフ構造の基本とその操作について学びます。

0. 記事の概要

この記事を読むメリット

• ネットワーク構造の理解：グラフ構造は、インターネットや交通網などを表現するのに適しています。
• 応用力の向上：経路探索アルゴリズムやソーシャルネットワーク解析の基礎を学べます。
• プログラミングの幅を拡大：基本的なグラフ操作を理解することで、複雑なデータを扱うスキルが向上します。

この記事で学べること

• グラフ構造の概念と種類
• 基本操作（頂点の追加、エッジの追加、探索）
• 実装例とその応用

活用のイメージ

グラフ構造は、地図の最短経路検索、ネットワークのトポロジー解析、ソーシャルネットワークの推薦アルゴリズムなどに応用されます。

1. グラフ構造の基本

1.1 グラフ構造とは？

グラフ構造は、頂点（vertex）とエッジ（edge）で構成されるデータ構造です。エッジによって頂点が接続され、ネットワークを形成します。

1.2 グラフの種類

• 無向グラフ：エッジが方向を持たないグラフ
• 有向グラフ：エッジが方向を持つグラフ
• 重み付きグラフ：エッジに重みが割り当てられたグラフ

1.3 表現方法

• 隣接行列：行列を用いて頂点間の接続を表現
• 隣接リスト：各頂点の隣接する頂点のリストを保持

2. グラフの実装

2.1 隣接リストによる実装

#include <stdio.h>
#include <stdlib.h>

// ノードの定義
typedef struct Node {
    int vertex;
    struct Node* next;
} Node;

// グラフの定義
typedef struct Graph {
    int numVertices;
    Node** adjLists;
} Graph;

// ノードを作成
Node* createNode(int v) {
    Node* newNode = malloc(sizeof(Node));
    newNode->vertex = v;
    newNode->next = NULL;
    return newNode;
}

// グラフを作成
Graph* createGraph(int vertices) {
    Graph* graph = malloc(sizeof(Graph));
    graph->numVertices = vertices;

    graph->adjLists = malloc(vertices * sizeof(Node*));

    for (int i = 0; i < vertices; i++) {
        graph->adjLists[i] = NULL;
    }
    return graph;
}

// エッジを追加
void addEdge(Graph* graph, int src, int dest) {
    Node* newNode = createNode(dest);
    newNode->next = graph->adjLists[src];
    graph->adjLists[src] = newNode;

    // 無向グラフの場合
    newNode = createNode(src);
    newNode->next = graph->adjLists[dest];
    graph->adjLists[dest] = newNode;
}

// グラフを表示
void printGraph(Graph* graph) {
    for (int i = 0; i < graph->numVertices; i++) {
        Node* temp = graph->adjLists[i];
        printf("Vertex %d: ", i);
        while (temp) {
            printf("%d -> ", temp->vertex);
            temp = temp->next;
        }
        printf("NULL\n");
    }
}

int main() {
    Graph* graph = createGraph(5);

    addEdge(graph, 0, 1);
    addEdge(graph, 0, 4);
    addEdge(graph, 1, 2);
    addEdge(graph, 1, 3);
    addEdge(graph, 1, 4);
    addEdge(graph, 2, 3);
    addEdge(graph, 3, 4);

    printGraph(graph);

    return 0;
}

動作解説

1. グラフの作成：createGraph()で指定された頂点数のグラフを作成します。
2. エッジの追加：addEdge()で頂点間の接続を追加します。
3. グラフの表示：printGraph()で隣接リスト形式でグラフを表示します。

3. 探索アルゴリズムの実装

3.1 深さ優先探索（DFS）の実装

void DFS(Graph* graph, int vertex, int* visited) {
    visited[vertex] = 1;
    printf("%d ", vertex);

    Node* temp = graph->adjLists[vertex];
    while (temp) {
        int adjVertex = temp->vertex;
        if (!visited[adjVertex]) {
            DFS(graph, adjVertex, visited);
        }
        temp = temp->next;
    }
}

int main() {
    Graph* graph = createGraph(5);
    int visited[5] = {0};

    addEdge(graph, 0, 1);
    addEdge(graph, 0, 4);
    addEdge(graph, 1, 2);
    addEdge(graph, 1, 3);
    addEdge(graph, 1, 4);
    addEdge(graph, 2, 3);
    addEdge(graph, 3, 4);

    printf("Depth First Search starting from vertex 0: ");
    DFS(graph, 0, visited);

    return 0;
}

動作解説

1. 初期化：訪問状況を記録する配列を用意します。
2. 再帰的な探索：訪問していない隣接頂点を再帰的に探索します。
3. 結果の出力：訪問した頂点を順番に表示します。

4. 練習問題

以下の課題に挑戦して、グラフ構造の理解を深めましょう。

1. 幅優先探索（BFS）を実装してください。
2. グラフのサイクルを検出する関数を作成してください。
3. 隣接行列を用いたグラフの実装を試してみてください。

5. 練習問題の解答と解説

問1の解答

#include <stdio.h>
#include <stdlib.h>

void BFS(Graph* graph, int startVertex) {
    int visited[5] = {0};
    int queue[5];
    int front = 0, rear = 0;

    visited[startVertex] = 1;
    queue[rear++] = startVertex;

    while (front != rear) {
        int currentVertex = queue[front++];
        printf("%d ", currentVertex);

        Node* temp = graph->adjLists[currentVertex];
        while (temp) {
            int adjVertex = temp->vertex;
            if (!visited[adjVertex]) {
                visited[adjVertex] = 1;
                queue[rear++] = adjVertex;
            }
            temp = temp->next;
        }
    }
}

int main() {
    Graph* graph = createGraph(5);

    addEdge(graph, 0, 1);
    addEdge(graph, 0, 4);
    addEdge(graph, 1, 2);
    addEdge(graph, 1, 3);
    addEdge(graph, 1, 4);
    addEdge(graph, 2, 3);
    addEdge(graph, 3, 4);

    printf("Breadth First Search starting from vertex 0: ");
    BFS(graph, 0);

    return 0;
}

このプログラムでは、キューを使用して幅優先探索を実装しています。

6. まとめ

本記事では、グラフ構造の基本と操作方法について学びました。次回は、グラフアルゴリズムの応用例をさらに詳しく掘り下げます。