無向グラフとは

無向グラフのデータ構造のクローンは簡単そうに見えて意外と簡単にはできません。下手に実装すると大変効率の悪いプログラムになってしまいます。

本記事ではクローンしたいグラフのノードの一つを入力にとって、それと同じグラフを持つ入力されたノードのコピーを返す関数を作ります。

有向グラフ/無向グラフ

グラフには有向グラフと無向グラフがあり、無向グラフはノードとノードの間の辺が対面通行のグラフです。有向グラフはノード間の辺が一方通行のグラフです。

出典: e-education.psu.edu

ノードの定義

まず、ノードを以下のように定義します。

# Python

class Node:
    def __init__(self, val: int, neighbors: list):
        self.val = val
        self.neighbors = neighbors

使用するアルゴリズムとデータ構造

データ構造をクローンするにはまずそのデータ構造を走査する必要があります。例えば二次元配列のクローンをするには必ず全ての要素を走査します。グラフのようなデータ構造を走査するアルゴリズムにはBFS(幅優先探索)とDFS(深さ優先探索)というのがあります。グラフのデータ構造は深さより幅が大きいことを想定して、ここではBFSを使います。しかし、BFSでグラフを探索しただけではノード間の辺の関係を記録することは難しいです。そこで、ハッシュテーブルを使います。

BFS

  1. 根ノードを空のキューに加える。
  2. ノードをキューの先頭から取り出し、以下の処理を行う。
    • ノードが探索対象であれば、探索をやめ結果を返す。
    • そうでない場合、ノードの子で未探索のものを全てキューに追加する。
  3. もしキューが空ならば、グラフ内の全てのノードに対して処理が行われたので、探索をやめ”not found”と結果を返す。
  4. 2に戻る。

出典: wikipedia

ハッシュテーブル

皆大好きな万能データ構造のハッシュテーブルです。とりあえずハッシュテーブルを使おうとするのはやめたほうがいいと思います。この問題ではハッシュテーブルはオリジナルのノードをキー、コピーを値として保存します。

アルゴリズム

  1. 入力されたノードをキューに追加し、ノードをキー、ノードのコピーを値としてハッシュテーブルに保存する。このクローニングはキューが空になるまで続けます。
  2. ノードをキューから取得する。
  3. 取得したノードに隣接したノード(node.neighbors)をイテレートする。
  4. 隣接しているノードがハッシュテーブルにない場合は、そのノードのコピーをハッシュテーブルに追加し、そのノードをキューに追加する。
  5. クローンされた隣接のノードを取得したノードのneighborsとして追加する。

Pythonコード

from collections import deque

def cloneGraph(node: Node) -> Node:
        # 入力されたノードのクローン
        copy_node = Node(node.val, [])

        # キューとハッシュテーブルの作成
        hash_ = dict()
        queue = deque()

        queue.append(node)
        hash_[node] = copy_node

        while queue:
            node = queue.popleft()
            
            for neighbor in node.neighbors:
                if neighbor not in hash_:
                    queue.append(neighbor)
                    hash_[neighbor] = Node(neighbor.val, [])

                hash_[node].neighbors.append(hash_[neighbor])
                
        return copy_node

時間計算量/空間計算量

時間計算量 = O(ノードの数 + 辺の数)

空間計算量 = O(ノードの数 + 辺の数)