グラフはバイナリツリーとして隣接リストとして表現できますか？

Question

お詫び申し上げます、英語は私の母国語ではありません。

これは私の理解で、補助リストとして表されています。これは通常、大部分のグラフでは疎なグラフに使用され、V（頂点数）リストを使用します。したがって、Vヘッドポインタ+ 2e（辺の数）ノードは、無向グラフ用です。したがって、空間複雑度= O（E + V） 任意のノードはV-1エッジ（それ自身を除く）を持つことができるので、ノードの隣接性をチェックするのにO（V）の時間複雑さがある。

O（v + e） これは主にスパースグラフに使用されているため、隣接関係を確認することはめったにありませんが、 V-1が可能な最大値なので、最悪の場合はO（V）です。

私は、リスト（エッジノード）をバイナリツリーにすることができますか？ ？ノードAがノードBに隣接しているかどうかを調べるために、時間複雑度はO（logn）であり、線形O（n）ではない。 可能であれば、実際にはかなり頻繁に行われていますか？また、そのようなデータ構造とは何ですか？私はそのような組み合わせは可能だが何も見つけることができなかった場合、グーグルで行ってきた。私がデータ構造を初めて知ったので、誰かが私にこのことを詳しく説明できるのであれば、とても感謝しています。ありがとうございました。

編集：私はバイナリ検索が配列に対して実行できることを知っています。私はリンクリストの表現について話していますが、私はリストに頭を付けるとわかりましたが、わかりました。

Answer 1

各頂点の隣接リストはバイナリツリーとして保存できませんでしたが、 tradoffs。

あなたが言うように、この隣接リストの表現は、スパースグラフでよく使用されます。しばしば、「疎グラフ」は、特定の頂点が他のいくつかの頂点に隣接していることを意味します。したがって、特定の頂点の "隣接リスト"は非常に小さくなります。バイナリ検索がO（log n）であり、逐次検索がO（n）であるのは真ですが、nが非常に小さい場合、逐次検索は高速です。私は、シーケンシャル検索がnが16より小さい場合にバイナリ検索を行うケースを見てきました。もちろん、実装にもよりますが、小さなリストではバイナリ検索が高速になるとは限りません。

もう1つはメモリです。リンクされたリストオーバーヘッドは、ノードごとに1つのポインタです。もちろん、二重リンクリストを使用している場合を除きます。バイナリツリーのオーバーヘッドはノードあたり2つのポインタです。多分大したことではないかもしれませんが、非常に大きなグラフを表現しようとすると、その余分なポインタが重要になります。

グラフが実行時に頻繁に更新される場合は、そのことも考慮する必要があります。リンクされたエッジリストに新しいエッジを追加することは、O（1）操作です。しかし、バイナリツリーにエッジを追加するには、O（log n）が必要です。そしてあなたは、あなたがその木のバランスを保つことを確認したいと思います。不均衡なツリーがリンクリストのように動作し始めます。

はい、隣接リストをバイナリツリーにすることができます。アプリケーションの速度要件とデータの性質に基づいて、余計な努力をする価値があるかどうかを判断する必要があります。