0

「隣接行列」表現を使用してグラフを表現することにした場合、行列のサイズをどのように知ることができますか?

私が見たすべてのコード例は、マトリックスを初期化するためにオブジェクトにサイズが与えられていることを前提としていGraphますが、このサイズがどこから来たのかは明確ではありません。
つまり、グラフを作成するには、グラフのデータがファイルなどからロードされ、ファイルを読みながらグラフを作成するのが最善の方法であると想定しています (これまでのところ正しいですか?)。
これは、リストである代替表現を使用すると非常に簡単です。
ただしmatrix、ファイルが実際にロードされるまで、頂点の数はわかりません。最初にファイル (何百万もの頂点を含む可能性があります) を読み取ってからグラフ作成するとは思いません。私には二重処理のように思えます。

では、通常の/最良の方法は何ですか?

注:matrix代わりにリストを使用することの利点は認識していますが、ほとんどのドキュメントでは、密なグラフでは行列の使用が許容されると述べられているため (ただし、疎ではありません)、表現を使用するプログラムが適切に実装されている方法を理解しようとしています。

4

3 に答える 3

1

そもそも頂点の数がない場合は、マトリックスを定型的な番号でしか初期化できないと思います。入力ファイルに次の形式の行のみが含まれているとします。これは、(オプションの) cost を持つx y zエッジ from xtoがあることを意味します。ファイルに他に何も含まれていないと仮定すると、入力ファイルの行数はグラフのエッジ数であることに注意してください。すでに密グラフであると想定しているため、頂点の数と等しい数のエッジを持つ完全なグラフであると仮定します。この情報を使用して、頂点の数を十分に近似することができます。たとえば、入力ファイルからのエッジ数が、到達した方程式を解いている場合 yzn(n-1)/2n1000000n*(n-1)/2 = 1000000nにほぼ等しい1415。行列を1415*1415配列に初期化すると、うまくカバーされるはずです。

もちろん、これはすべて、入力ファイルの行数を読み取る十分な速さがあるという事実に基づいています。

于 2012-05-17T21:45:54.937 に答える
1

通常/最良の方法はコメントに記載されています。再割り当てしてコピーします。私が覚えている限り、毎回サイズをスケーリングすると(たとえば2倍)、償却された(平均)コストはO(n)になります。これは、たとえば、python が必要なサイズに成長するリストを持っている方法です。それは完全に標準/共通です。

[私は実際にここにポイントを投稿しているわけではありません; コメントの回答が必要なものであることに不満を感じていますが、それらに注意を払っていないか、理解していない可能性があります]

于 2012-05-18T21:37:34.940 に答える
1

入力形式が制御下にある場合は、サイズを適切に見積もることができます。以下の例では、すべての値が固定長 (6 文字) で、左側のパディングは 0 です。これは、各行のサイズが 22 バイトになることを意味します。ファイルのサイズを 22 で割ると、行列サイズの概算が得られます。グラフが完成した場合、ファイル サイズは に等しくなりますnxn。ここで、n は頂点の数です。

例:

000001 000020 000030
000800 000001 000040
      etc...

もう 1 つの解決策は、サイズを超えるたびに行列のサイズを 2 倍にすることです。償却された計算コストは​​小さくなります。一方で、メモリが問題になる可能性があります。

于 2012-05-18T18:18:36.350 に答える