ルートと呼ばれる単一の指定ノードを持つ有向グラフがあり、そこから他のすべてのノードに到達できます。各ターミナル ノード (発信エッジなし) は文字列値を取ります。中間ノードには 1 つ以上の出力エッジがありますが、それらに関連付けられた値はありません。ノードを隣接ノードに接続するエッジには、文字列ラベルがあります。単一のノードから発生するエッジのラベルは一意です。グラフにはサイクルが存在する可能性があります!
そのような 2 つの有向 (おそらくサイクルを持つ) グラフ (上記のように) が等しいかどうかをチェックするための最適なグラフ アルゴリズムは何ですか?
グラフ同型問題は、TCS の興味深い問題の 1 つです。wikiに専用のページ全体があります。
特定のケースでは、ソースとシンクを持つ 2 つの根付き有向グラフがあります。
2 つの BFS を並行して開始し、レベルごとに同形性をチェックできます。つまり、グラフを平準化して、各レベルのノードのサブセットが 2 つのグラフ間で同形であるかどうかを確認します。
有向、根付きグラフがあるので、同形性を見つける目的でそれを平準化できるはずであることに注意してください。BFS 中にすでにアクセスしたノードをキューに入れません。つまり、グループ化するレベルを決定するときに、ルートからノードへの最短パスを使用してレベル化します。
セット内での比較は比較的簡単です。同じレベル (次数、ラベル) でノードを区別するための多くのプロパティがあり、それらを並べ替えるための適切なシグネチャを作成できるはずです。完全な同型を探しているので、完全に一致する必要があります。