無向グラフのエッジ数

Question

無向グラフの隣接リスト表現が与えられている。無向グラフのエッジ数を数える関数を書く。

無向グラフの辺の数はn（n-1）/ 2であることが分かりますが、そのための関数を書く方法はわかりません。

私はリストを持っていると考え、それを使って私はエッジの数を数えます。どうすればいいですか？

Answer 1

n(n-1)/2は、単純な無向グラフのエッジの最大数であり、すべてのグラフのエッジ数ではありません。

隣接リストの表現があるとすれば、頂点uとvの間に辺がある場合になります。次に、vが隣接リストのuに表示され、uが隣接リストのvに表示されます。これはuとvのいずれにも当てはまります。

したがって、各頂点の隣接リスト内のすべての要素のエントリの総数を数えると、結果はグラフのエッジの数の2倍になります。この値を2で割ると、望ましい結果が得られます。