graph - 無向グラフ隣接 (コンピュータ サイエンス)

Question

1、2、3、...、n というラベルの付いたノードと V の特定のノード k を持つ無向グラフ G=(V,E) があります。

このグラフには、Adjacency-MatrixとAdjacency-Listの 2 つの表現があります。

ノード k がグラフ内の他のすべてのノードに隣接しているかどうかを調べるにはどうすればよいですか? これは、私が抱えているより大きな問題の一部です。

具体的な疑似コードやソリューションは必要ありません。データ構造で何をスキャンし、これをどのように判断するかを平易な英語で説明します。(複雑さはできるだけ抑えてください)

ありがとう

Answer 1

adj 行列を使用して、 -thk以外のすべてのコンポーネントで行が 1 であることを確認します。k

adj リストを使用して (マルチグラフがなく、nがグラフの頂点の数であると仮定して)、n-1O(1) である list size を確認します。

よろしく、カルテン

Answer 2

おそらく、すべてのノードをチェックして、それらのいずれかが k に隣接していない場合は false を返すことができます。すべての頂点をチェックすることを避けることはできないと思うので、ショート サーキット フェイルを実行することをお勧めします。