隣接行列と有向グラフの隣接リスト

Question

練習として、私は場所から場所までの最短かつ最速のルートを計画するsatnavシステムを構築しなければなりません。あまりにも多くのメモリを使わなくても、できるだけ速くする必要があります。

グラフを表すために使用する構造を決定するのに問題があります。私は、密度の高いグラフの方がマトリックスが優れていることと、疎なグラフの方がリストが良いことを理解しています。私は頂点を追加することがこのプログラムの最も課税的な部分であると仮定しているので、リストを使用する方にもっと傾いています。

あなたの意見を聞きたいだけです。典型的なロードマップを、さまざまな場所がノードであり、道路がエッジであるグラフとして見るべきかどうか。あなたはそれが疎であるとか濃密であると考えますか？このシナリオでは、どの構造が良いと思われますか？

Answer 1

私はリストのために行くのはその1回だけの投資だからです。それについての良いことは、が隣接するすべての頂点を反復できることです。は、最短経路アルゴリズムの大部分で重要で最も頻繁な手順である行列よりも高速です。

ここで、行列はO（N）であり、隣接リストはO（k）のみになります。ここでkは隣接する頂点の数です。