この質問には多くの変形があり、解答はO(|V|)になります。隣接リストの表現が与えられたときにユニバーサルシンクを見つけるための時間の複雑さは何ですか
しかし、グラフ内にユニバーサルシンクがあり、隣接リストにグラフが表示されている場合、計算したい場合は最悪の場合があります。これは重要です。なぜなら、他のすべてのアルゴリズムが隣接リストの方が優れているように見えます。普遍的なシンクが必要な操作であまり頻繁ではない場合、私は間違いなくマトリックスではなくリストを作成します。
私の意見では、時間の複雑さは、グラフのサイズ、つまりO(|V| + |E|)です。グラフのユニバーサルシンクを求めるアルゴリズムは以下の通りである。隣接リストを仮定すると、グラフのインデックス1から開始します。インデックス1の隣接リストの長さが|V| - 1である場合は、そのリストをトラバースして自己ループが存在するかどうかを調べます。リストに自己ループがない場合and他のすべての頂点はリストの一部です。リストインデックスを格納します。次に、この頂点がリストの一部であるかどうかをチェックするために、他のリストを調べる必要があります。そうであれば、格納された頂点はユニバーサルシンクになることはできません。次のインデックスから検索を続行します。リストがアウトネイバーリストであっても、length = 0のリストを持つ頂点を検索し、他のすべてのリストを検索して、この頂点がそれぞれのリストに存在するかどうかをチェックする必要があります。上記の説明から結論付けることができるように、どのような形式の隣接リストが考慮されても、最悪の場合、ユニバーサルシンクを見つけることは、すべての頂点およびエッジを一度通過しなければならないので、複雑さはグラフのサイズすなわち、O（| V | + | E |）
最近、大学の助教授として参加した私の友人は、O(|V|*|V|)でなければならないと述べました。私は彼が春にコースを教え始める前に彼のメモを見直していますが、修正する前に私は100％確信したいと思います。