エッジでのグラフのクエリ

Question

アトリビュートグラフは、隣接行列またはノードがファーストクラスの市民とみなされるリストとして最も一般的に表されます。近傍、最短経路、ページ・ランク、これらのマトリックス上で動作する接続コンポーネント、およびノー​​ド上のリスト構造など、多くのグラフ照会が存在する。ノード/エッジの属性は、接続とは別に格納することもできます。

グラフの別の表現は、incidence matrixです。ここで、ノードの入射エッジはマトリックスに記録されます。私は以前のノードベースのメソッドとまったく同じ情報を表すことを理解しています。

私の質問は、ノードベースの構造、すなわちエッジベースの構造を使用するのではなく、入射行列構造の恩恵を受けることができるグラフのクエリ/ワークロード/アルゴリズムですか？入射行列が正確に使用されるのはいつですか？

Iは入射マトリックスが速くなるかもしれない唯一の場合を考えることができる

Answer 1

：隣接行列及びOを使用する場合

ノードの次数を見つけるか、隣接ノードを発見は（複雑性O（V）での動作であり、E ）である。

通常、E> Vですが、グラフに0度ノードが多い場合はそうではありません。隣接するノードを見つけることは基本的な操作であるので、多くのアルゴリズムはこのようなグラフ上でより高速であることが判明するかもしれない。