C言語で重み付きグラフを表現する方法について、その基本概念から具体的なコード例までを詳しく解説します。本記事では、隣接行列と隣接リストという2つの主要な表現方法を取り上げ、それぞれの利点・欠点や使用例を比較しながら、重み付きグラフを操作する方法やアルゴリズムの実装についても説明します。
重み付きグラフとは
重み付きグラフとは、グラフの各辺（エッジ）に重み（ウェイト）と呼ばれる数値が割り当てられたグラフのことです。これらの重みは、一般的にコストや距離、時間などを表し、様々な分野で重要な役割を果たします。例えば、交通ネットワークにおける道路の距離や通信ネットワークにおける遅延時間などが該当します。重み付きグラフは、最短経路問題や最大フロー問題など、複雑なアルゴリズムの基礎となるため、その表現方法を理解することは非常に重要です。
重み付きグラフの表現方法
重み付きグラフをC言語で表現する方法には、主に隣接行列と隣接リストの2つの方法があります。隣接行列は、グラフの全ての頂点の組み合わせに対して重みを持つ2次元配列を使用する方法で、アクセスが容易ですがメモリ消費が大きいです。一方、隣接リストは、各頂点ごとに接続されている頂点とその重みをリストで保持する方法で、メモリ効率が良いですがアクセスにはやや手間がかかります。これらの方法を使って、重み付きグラフを効果的に表現することができます。
隣接行列による表現
隣接行列は、グラフの頂点間の接続とその重みを2次元配列で表現する方法です。この方法では、頂点の数を( n )としたとき、( n \times n )の行列を用います。行列の各要素 ( \text{matrix}[i][j] ) は、頂点 ( i ) と頂点 ( j ) の間のエッジの重みを表します。エッジが存在しない場合は通常、無限大（または特殊な値）を用いて表現します。
隣接行列の利点
- エッジの重みの確認が簡単で、高速（O(1)）。
- 実装が比較的簡単で直感的。
隣接行列の欠点
- メモリ使用量が多い（特にスパースグラフでは効率が悪い）。
- エッジの数が少ない場合でもメモリを多く消費する。
隣接行列の例
以下は、C言語で隣接行列を用いた重み付きグラフの例です。
#include <stdio.h>
#define INF 99999 // エッジが存在しない場合の値
void printGraph(int graph[][3], int vertices) {
for (int i = 0; i < vertices; i++) {
for (int j = 0; j < vertices; j++) {
if (graph[i][j] == INF) {
printf("INF ");
} else {
printf("%d ", graph[i][j]);
}
}
printf("\n");
}
}
int main() {
int vertices = 3;
int graph[3][3] = {
{0, 1, 4},
{1, 0, 2},
{4, 2, 0}
};
printGraph(graph, vertices);
return 0;
}このコードは、3つの頂点を持つグラフを隣接行列で表現し、各エッジの重みを表示します。エッジが存在しない場合は、INFで表現しています。
隣接リストによる表現
隣接リストは、各頂点に接続されている頂点とそのエッジの重みをリストで保持する方法です。この方法では、各頂点ごとに接続されている頂点とその重みを保持するリストを用意します。隣接リストは、特にエッジの数が少ないスパースグラフに対してメモリ効率が高いです。
隣接リストの利点
- メモリ使用量が少ない（特にスパースグラフの場合）。
- エッジの追加や削除が比較的簡単。
隣接リストの欠点
- 特定のエッジの重みの確認がやや遅い（リストを探索する必要がある）。
- 実装がやや複雑。
隣接リストの例
以下は、C言語で隣接リストを用いた重み付きグラフの例です。
#include <stdio.h>
#include <stdlib.h>
// 辺を表す構造体
struct Edge {
int dest;
int weight;
struct Edge* next;
};
// 各頂点の隣接リストを表す構造体
struct Graph {
int numVertices;
struct Edge** adjLists;
};
// 新しい辺を作成する関数
struct Edge* createEdge(int dest, int weight) {
struct Edge* newEdge = (struct Edge*)malloc(sizeof(struct Edge));
newEdge->dest = dest;
newEdge->weight = weight;
newEdge->next = NULL;
return newEdge;
}
// グラフを作成する関数
struct Graph* createGraph(int vertices) {
struct Graph* graph = (struct Graph*)malloc(sizeof(struct Graph));
graph->numVertices = vertices;
graph->adjLists = (struct Edge**)malloc(vertices * sizeof(struct Edge*));
for (int i = 0; i < vertices; i++)
graph->adjLists[i] = NULL;
return graph;
}
// 辺をグラフに追加する関数
void addEdge(struct Graph* graph, int src, int dest, int weight) {
// ソースからデスティネーションへのエッジを追加
struct Edge* newEdge = createEdge(dest, weight);
newEdge->next = graph->adjLists[src];
graph->adjLists[src] = newEdge;
// デスティネーションからソースへのエッジを追加（無向グラフの場合）
newEdge = createEdge(src, weight);
newEdge->next = graph->adjLists[dest];
graph->adjLists[dest] = newEdge;
}
// グラフを表示する関数
void printGraph(struct Graph* graph) {
for (int i = 0; i < graph->numVertices; i++) {
struct Edge* temp = graph->adjLists[i];
printf("Vertex %d:\n", i);
while (temp) {
printf(" -> %d (Weight %d)", temp->dest, temp->weight);
temp = temp->next;
}
printf("\n");
}
}
int main() {
int vertices = 3;
struct Graph* graph = createGraph(vertices);
addEdge(graph, 0, 1, 1);
addEdge(graph, 0, 2, 4);
addEdge(graph, 1, 2, 2);
printGraph(graph);
return 0;
}このコードは、3つの頂点を持つグラフを隣接リストで表現し、各エッジの重みを表示します。各頂点の隣接リストを出力し、エッジの接続と重みを確認できます。
隣接行列と隣接リストの比較
隣接行列と隣接リストは、重み付きグラフを表現する2つの主要な方法です。それぞれに利点と欠点があり、用途によって使い分けることが重要です。ここでは、両者の特徴を比較します。
隣接行列の特徴
- 利点:
- エッジの有無や重みの確認がO(1)の時間で可能。
- 実装が簡単で直感的。
- 欠点:
- メモリ使用量が多い（特に頂点数が多い場合）。
- スパースグラフ（エッジが少ないグラフ）には不向き。
隣接リストの特徴
- 利点:
- メモリ使用量が少ない（エッジが少ない場合に特に有効）。
- エッジの追加や削除が容易。
- 欠点:
- エッジの有無や重みの確認がO(V)の時間を要する（Vは頂点数）。
- 実装がやや複雑。
用途に応じた使い分け
- 隣接行列: 頂点数が少なく、エッジが多い場合に適しています。全てのエッジを頻繁にアクセスする場合や、エッジの有無を高速に確認する必要がある場合に有効です。
- 隣接リスト: 頂点数が多く、エッジが少ないスパースグラフに適しています。メモリ効率が重要な場合や、エッジの追加・削除が頻繁に行われる場合に適しています。
このように、隣接行列と隣接リストはそれぞれの利点と欠点を理解し、適切に使い分けることが重要です。
重み付きグラフの操作
重み付きグラフに対する基本的な操作として、エッジの追加、削除、および探索があります。これらの操作を実装することで、グラフを動的に変更し、必要な情報を取得することが可能になります。ここでは、隣接行列と隣接リストの両方でこれらの操作を実装する方法を説明します。
隣接行列での操作
- エッジの追加:
void addEdge(int graph[][3], int src, int dest, int weight) {
graph[src][dest] = weight;
graph[dest][src] = weight; // 無向グラフの場合
}- エッジの削除:
void removeEdge(int graph[][3], int src, int dest) {
graph[src][dest] = INF;
graph[dest][src] = INF; // 無向グラフの場合
}- エッジの探索:
int getEdgeWeight(int graph[][3], int src, int dest) {
return graph[src][dest];
}隣接リストでの操作
- エッジの追加:
void addEdge(struct Graph* graph, int src, int dest, int weight) {
struct Edge* newEdge = createEdge(dest, weight);
newEdge->next = graph->adjLists[src];
graph->adjLists[src] = newEdge;
newEdge = createEdge(src, weight);
newEdge->next = graph->adjLists[dest];
graph->adjLists[dest] = newEdge;
}- エッジの削除:
void removeEdge(struct Graph* graph, int src, int dest) {
struct Edge* temp = graph->adjLists[src];
struct Edge* prev = NULL;
while (temp != NULL && temp->dest != dest) {
prev = temp;
temp = temp->next;
}
if (temp == NULL) return;
if (prev != NULL)
prev->next = temp->next;
else
graph->adjLists[src] = temp->next;
free(temp);
// 無向グラフの場合、逆方向のエッジも削除
temp = graph->adjLists[dest];
prev = NULL;
while (temp != NULL && temp->dest != src) {
prev = temp;
temp = temp->next;
}
if (temp == NULL) return;
if (prev != NULL)
prev->next = temp->next;
else
graph->adjLists[dest] = temp->next;
free(temp);
}- エッジの探索:
int getEdgeWeight(struct Graph* graph, int src, int dest) {
struct Edge* temp = graph->adjLists[src];
while (temp != NULL) {
if (temp->dest == dest)
return temp->weight;
temp = temp->next;
}
return INF; // エッジが存在しない場合
}これらの操作を実装することで、重み付きグラフを動的に扱うことができます。
実践例：最短経路アルゴリズム
重み付きグラフの代表的なアルゴリズムとして、ダイクストラ法があります。これは、単一始点から他の全ての頂点までの最短経路を見つけるためのアルゴリズムです。ここでは、ダイクストラ法を用いた実践例を示します。
ダイクストラ法の概要
ダイクストラ法は、次のステップで動作します。
- 始点の距離を0に設定し、他の頂点の距離を無限大に設定します。
- 未処理の頂点の中から、距離が最も小さい頂点を選択します。
- 選択した頂点を経由して他の頂点への距離を更新します。
- 全ての頂点が処理されるまで、ステップ2と3を繰り返します。
ダイクストラ法の実装（隣接行列を使用）
以下は、隣接行列を用いたダイクストラ法の実装例です。
#include <stdio.h>
#include <limits.h>
#include <stdbool.h>
#define V 5
#define INF INT_MAX
int minDistance(int dist[], bool sptSet[]) {
int min = INF, min_index;
for (int v = 0; v < V; v++)
if (sptSet[v] == false && dist[v] <= min)
min = dist[v], min_index = v;
return min_index;
}
void printSolution(int dist[]) {
printf("Vertex \t Distance from Source\n");
for (int i = 0; i < V; i++)
printf("%d \t\t %d\n", i, dist[i]);
}
void dijkstra(int graph[V][V], int src) {
int dist[V];
bool sptSet[V];
for (int i = 0; i < V; i++)
dist[i] = INF, sptSet[i] = false;
dist[src] = 0;
for (int count = 0; count < V - 1; count++) {
int u = minDistance(dist, sptSet);
sptSet[u] = true;
for (int v = 0; v < V; v++)
if (!sptSet[v] && graph[u][v] && dist[u] != INF
&& dist[u] + graph[u][v] < dist[v])
dist[v] = dist[u] + graph[u][v];
}
printSolution(dist);
}
int main() {
int graph[V][V] = {
{0, 10, 0, 0, 5},
{0, 0, 1, 0, 2},
{0, 0, 0, 4, 0},
{7, 0, 6, 0, 0},
{0, 3, 9, 2, 0}
};
dijkstra(graph, 0);
return 0;
}このコードは、5つの頂点を持つ重み付きグラフに対して、頂点0から他の全ての頂点への最短経路を求めます。各頂点への距離が表示されます。
応用例：ネットワークの最適化
重み付きグラフは、ネットワークの最適化問題にも広く応用されます。例えば、通信ネットワークにおける遅延の最小化や、物流ネットワークにおけるコストの削減などが考えられます。ここでは、重み付きグラフを用いたネットワークの最適化の具体例として、最小全域木（Minimum Spanning Tree, MST）アルゴリズムを紹介します。
最小全域木の概要
最小全域木とは、グラフの全ての頂点を含み、エッジの重みの合計が最小になる部分グラフのことです。MSTを求めるアルゴリズムとして、クラスカル法とプリム法があります。ここでは、プリム法を用いた実装例を紹介します。
プリム法の実装（隣接行列を使用）
以下は、隣接行列を用いたプリム法の実装例です。
#include <stdio.h>
#include <limits.h>
#include <stdbool.h>
#define V 5
int minKey(int key[], bool mstSet[]) {
int min = INT_MAX, min_index;
for (int v = 0; v < V; v++)
if (mstSet[v] == false && key[v] < min)
min = key[v], min_index = v;
return min_index;
}
void printMST(int parent[], int graph[V][V]) {
printf("Edge \tWeight\n");
for (int i = 1; i < V; i++)
printf("%d - %d \t%d \n", parent[i], i, graph[i][parent[i]]);
}
void primMST(int graph[V][V]) {
int parent[V];
int key[V];
bool mstSet[V];
for (int i = 0; i < V; i++)
key[i] = INT_MAX, mstSet[i] = false;
key[0] = 0;
parent[0] = -1;
for (int count = 0; count < V - 1; count++) {
int u = minKey(key, mstSet);
mstSet[u] = true;
for (int v = 0; v < V; v++)
if (graph[u][v] && mstSet[v] == false && graph[u][v] < key[v])
parent[v] = u, key[v] = graph[u][v];
}
printMST(parent, graph);
}
int main() {
int graph[V][V] = {
{0, 2, 0, 6, 0},
{2, 0, 3, 8, 5},
{0, 3, 0, 0, 7},
{6, 8, 0, 0, 9},
{0, 5, 7, 9, 0},
};
primMST(graph);
return 0;
}このコードは、5つの頂点を持つ重み付きグラフに対して最小全域木を求め、各エッジとその重みを表示します。プリム法を用いることで、全ての頂点を含む最小コストのネットワークを構築できます。
練習問題
重み付きグラフの理解を深めるために、以下の練習問題に挑戦してみてください。これらの問題を通じて、重み付きグラフの基本操作やアルゴリズムの実装力を強化できます。
問題1: 隣接行列の作成と表示
C言語で隣接行列を使用して、以下のグラフを表現し、表示するプログラムを作成してください。
0
/ \
/ \
1-----2重み: 0-1: 4, 0-2: 3, 1-2: 5
問題2: 隣接リストの作成と表示
C言語で隣接リストを使用して、以下のグラフを表現し、表示するプログラムを作成してください。
0
/|\
/ | \
1--3--2重み: 0-1: 2, 0-2: 3, 0-3: 6, 1-3: 5, 2-3: 7
問題3: ダイクストラ法の実装
以下の隣接行列を持つグラフに対して、頂点0から他の全ての頂点への最短経路を求めるダイクストラ法を実装してください。
0 1 2 3
0 [0, 1, 4, 0]
1 [1, 0, 2, 6]
2 [4, 2, 0, 3]
3 [0, 6, 3, 0]問題4: プリム法による最小全域木の作成
以下の隣接行列を持つグラフに対して、最小全域木を求めるプリム法を実装してください。
0 1 2 3 4
0 [0, 2, 0, 6, 0]
1 [2, 0, 3, 8, 5]
2 [0, 3, 0, 0, 7]
3 [6, 8, 0, 0, 9]
4 [0, 5, 7, 9, 0]これらの練習問題に取り組むことで、重み付きグラフの基本的な操作やアルゴリズムの実装方法を理解し、実践力を高めることができます。
まとめ
本記事では、C言語を用いた重み付きグラフの表現方法について、基本概念から具体的な実装例、そして応用例までを詳しく解説しました。重み付きグラフは、様々なアルゴリズムやネットワークの最適化問題で重要な役割を果たします。隣接行列と隣接リストという2つの主要な表現方法を理解し、適切に使い分けることで、効率的なプログラムを作成することが可能です。また、ダイクストラ法やプリム法といったアルゴリズムを実装することで、より複雑な問題に対応できるようになります。
今後の学習の指針としては、これらの基本をさらに深め、他のアルゴリズムや応用例に挑戦することが重要です。実際のプロジェクトや問題解決に取り組む中で、今回学んだ内容を活用し、さらに知識を広げていってください。
コメント