無向グラフと有向グラフの違い

グラフは、ノード（頂点）とそれらを結ぶエッジ（辺）から構成されるデータ構造です。グラフには、主に無向グラフと有向グラフの2つのタイプがあります。それぞれの特徴と違いを理解することは、グラフ理論の基礎を学ぶ上で重要です。

無向グラフ

無向グラフでは、エッジに方向がありません。すなわち、エッジは2つのノードの間で双方向に接続されていると考えることができます。無向グラフの例として、友人関係のネットワークを挙げることができます。もしAとBが友人であれば、AはBの友人であり、BもAの友人です。

無向グラフの特徴

• エッジに方向がない
• 同じエッジを使って両方向に移動可能
• 通常、エッジは {u, v} の形で表現される（uとvはノード）

有向グラフ

有向グラフでは、エッジには方向があります。エッジは始点と終点を持ち、特定の方向にのみ移動することができます。有向グラフの例として、ウェブページのリンク構造を挙げることができます。ページAからページBへのリンクがある場合、AからBに移動できますが、BからAには直接移動できません。

有向グラフの特徴

• エッジに方向がある
• 始点から終点への一方向の移動のみ
• 通常、エッジは (u, v) の形で表現される（uは始点、vは終点）

無向グラフと有向グラフの比較

以下の表に、無向グラフと有向グラフの違いをまとめます。

Pythonによる無向グラフと有向グラフの実装

次に、無向グラフと有向グラフをPythonで実装してみます。それぞれのグラフをクラスとして定義し、エッジを追加するメソッドを作成します。

無向グラフの実装

以下は、無向グラフを表現するためのPythonコードです。

class UndirectedGraph:
    def __init__(self):
        self.graph = {}

    def add_edge(self, u, v):
        # エッジを追加する
        if u not in self.graph:
            self.graph[u] = []
        if v not in self.graph:
            self.graph[v] = []

        self.graph[u].append(v)
        self.graph[v].append(u)

    def display(self):
        for node in self.graph:
            print(f"{node}: {', '.join(map(str, self.graph[node]))}")

# 無向グラフを作成
undirected_graph = UndirectedGraph()
undirected_graph.add_edge(1, 2)
undirected_graph.add_edge(1, 3)
undirected_graph.add_edge(2, 4)

# グラフを表示
undirected_graph.display()

コード解説

1. クラスの定義: UndirectedGraphクラスを定義し、グラフを辞書で表現します。
2. エッジの追加: add_edgeメソッドでエッジを追加します。ノードが存在しない場合は、空のリストを作成してからエッジを追加します。
3. グラフの表示: displayメソッドで、各ノードとその接続先を表示します。

このコードを実行すると、無向グラフの構造がわかります。

有向グラフの実装

次に、有向グラフを表現するためのPythonコードを示します。

class DirectedGraph:
    def __init__(self):
        self.graph = {}

    def add_edge(self, u, v):
        # エッジを追加する
        if u not in self.graph:
            self.graph[u] = []
        if v not in self.graph:
            self.graph[v] = []

        self.graph[u].append(v)

    def display(self):
        for node in self.graph:
            print(f"{node}: {', '.join(map(str, self.graph[node]))}")

# 有向グラフを作成
directed_graph = DirectedGraph()
directed_graph.add_edge(1, 2)
directed_graph.add_edge(1, 3)
directed_graph.add_edge(3, 2)

# グラフを表示
directed_graph.display()

コード解説

1. クラスの定義: DirectedGraphクラスを定義し、グラフを辞書で表現します。
2. エッジの追加: add_edgeメソッドでエッジを追加します。無向グラフとは異なり、始点から終点へのエッジのみを追加します。
3. グラフの表示: displayメソッドで、各ノードとその接続先を表示します。

このコードを実行すると、有向グラフの構造がわかります。

まとめ

無向グラフと有向グラフは、エッジの方向性の有無によって異なる特性を持っています。無向グラフは双方向の関係を示し、有向グラフは一方向の関係を示します。Pythonを使って、これらのグラフを実装することで、グラフの基本的な操作を理解することができます。