時間計算量/グラフ理論

Question

宿題の問題で、グラフが隣接リストで表されるn個のノードとm個のエッジのセットが与えられた場合、insertVertexがO（1）を取り、deleteVertexがO（m）をとる理由について質問されました。

私の答えは完全にはわかりませんが、insertVertexはO（1）であると言います。これは、最初に挿入するときに、配列に追加するのは1つのノードと隣接する頂点のセット（新しい頂点を意味する）だけだからです。ノードが指す）。したがって、この時間計算量は一定です。ただし、ノードを削除するときは、ノードとノードに付属する隣接するエッジを削除する必要があるだけでなく、残りのm個のエッジを通過して、を指すエッジを確実に削除する必要があります。削除しようとしているノード（何も指さないエッジを持つことができないため。

私はグラフ理論に慣れていないので、私の考え方が正しいかどうかわかりません。いくつかのアドバイスは素晴らしいでしょう。

ありがとう

Answer 1

O（m）の説明は正しいです。

リンクリストの操作の観点からアクションを説明すると、説明がより適切になります。リンクリストにノードを追加するには、O（1）の時間がかかります。また、アイテムの削除にはO（n）時間がかかります。

a）insertVertexがO（1）である理由

頂点の挿入は、リンクリスト（O（1））にノードを追加するだけです。グラフが無向の場合は2です。

b）deleteVertexがO（m）である理由

頂点を削除するとは、次のことを意味します。

1）リンクリストを削除する（O（1））

2）最悪の場合、すべてのリンクリストから頂点を削除する必要があります：O（m）。すべてのリンクリストのノード数がmであるため、O（m）であり、グラフが無向の場合は2 * mです。

Answer 2

insertVertexは、データ構造の最後に新しい要素を追加するだけなので、O（1）を取ります。

deleteVertexはO（m）を取ります。これは、すべてのエッジについて、エッジが頂点を指しているか、頂点から離れているか（Gが向けられている場合）を確認する必要があるためです。

OPを読んで、アイデアが浮かんだようです。