隣接行列に複数のノード（サイズは不明です。膨大な場合があります）を持つ無向グラフを保存する必要があります。2D arrayListは、これを格納するための効率的な方法でしょうか？そうでない場合、このデータを保存するためのより良い方法は何ですか？コメントをいただければ幸いです。
1537 次
3 に答える
4
私は間違いなく2dArrayListを選びます。最後に挿入する場合は、O（n）時間（nは行数）で行/列を追加できます（これは理にかなっています）。リストへのアクセスはO（1）であり、任意の行を削除するとO（n 2）になります。
もう1つのオプションは、二重リンクリストを使用することです。この場合、最後への挿入はO（n）時間、アクセスはO（n）、行の削除はO（n 2）になります。
したがって、マトリックスの場合、ArrayListが最適であるように見えますが、これはアクセスがより効率的であるためです。
于 2011-02-16T21:18:30.677 に答える
1
あなたは隣接リストが「広大」である可能性があると言います。それもスパースである場合は、ある種のスパース行列表現を使用したほうがよい場合があります。メモリフットプリントが大幅に削減されているため、2dArrayListよりもパフォーマンスが優れている可能性もあります。
于 2011-02-16T22:13:17.903 に答える
0
グラフのサイズもファイルの最初の行に保存すると簡単だと思います。そうすれば、割り当てとプロセス全体がはるかに効率的になり、他に少しの損失はありません。
マトリックスを増やすときに割り当てを行う必要がある場合は、問題のドメインの適切なサイズから始めて、2の乗数でそれを増やす必要があります。これにより、時間の経過とともに、割り当ての量が安定し、内容を何度も再割り当てして再コピーする必要はありません。
お役に立てば幸いです。
于 2011-02-16T21:18:29.020 に答える