1

エッジのリストから隣接リストを作成できるアルゴリズムを作成しています。

たとえば、データ入力が次の場合:

1 2
1 8
2 8
3 5
3 1
4 5
4 6
5 2
5 9
6 4
6 8
7 4
7 10
8 4
8 6
9 4
9 5
10 7
10 3

出力は次のようになります。

1: 8 4 6
2: 4 6
3: 9 2 8
4: 2 9 8
5: 8 4
6: 5 4
7: 5 6 3
8: 5 6 4
9: 5 6 2
10: 4 5 1

アルゴリズムは明らかに頂点とエッジの数によって制限されるため、当初は O(v + e) になると考えていました。しかし、2 次元配列を使用して for ループ内に for ループを実装することによってのみ、プログラムを機能させることができました。これは、O(N^2) の複雑さを引き起こすと考えられます。

誰でも理解を深めることができますか？

4

1 に答える 1

2

これは、頂点から隣接する頂点のリストへのマップを格納するために使用しているデータ構造の種類にかなり依存します。もちろん、エッジのリストを反復処理すると、時間計算量O（e）が発生します。より大きな時間計算量は、マップ内の頂点を見つけるのに必要な時間と、頂点の隣接する頂点のリストに新しいアイテムを挿入するのに必要な時間から生じます。フラット配列を使用している場合は、O（v * e）の複雑さを持つ可能性があります（各エッジについて、頂点リストをループして目的の頂点を見つけます）が、ハッシュテーブルまたはツリーを使用することでこれを大幅に改善できます。ルックアップパフォーマンスを向上させるデータ構造。

于 2012-09-17T06:18:28.820 に答える