[トイレに座ってアルゴリズムを読む] アルゴリズム 8: 賢い隣接リスト (配列の実装)

前回は、空間と時間の複雑さがともにN 2であるグラフの隣接行列保存方法を紹介しました。今回は、グラフを保存するための別の方法である、空間と時間の複雑さが M である隣接リストを紹介します。疎グラフの場合、M はN 2 よりもはるかに小さくなります。まず、データは以下のとおりです。

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

最初の行には 2 つの整数 nm が含まれています。 n は頂点の数（頂点には 1 から n までの番号が付けられます）を表し、m は辺の数を表します。次の m 行は、各行に 3 つの数値 xyz があり、頂点 x から頂点 y への辺の重みが z であることを示しています。下の図は、リンク リストを使用して隣接リストを実装する方法を示しています。

上記の実装では、グラフ内の各頂点 (左側) に対して単一リンク リスト (右側) が作成されます。このようにして、各頂点のリンク リストをトラバースすることで、各頂点のすべてのエッジを取得できます。リンク リストを使用して隣接リストを実装することは、ポインターを嫌う人にとっては悪夢です。ここでは、配列を使用して隣接リストを実装する別の方法を紹介します。これは、実際のアプリケーションで実装するのが非常に簡単な方法です。このメソッドは、各頂点 i (i の範囲は 1 から n) に対して「リンク リスト」のようなものも保存します。このリストには、次のように、頂点 i から始まるすべてのエッジが格納されます。

まず、各エッジに読み取られる順序 (1 から m) で番号を付けます。たとえば、最初のエッジ「1 4 9」には番号 1 が付けられ、エッジ「1 3 7」には番号 5 が付けられます。

ここで、3つの配列u、v、wは各エッジの特定の情報を記録するために使用されます。つまり、u[i]、v[i]、w[i]は、i番目のエッジが頂点u[i]から頂点v[i]（u[i]àv[i]）までのものであり、その重みがw[i]であることを示します。

最初の配列を使用して、各頂点の 1 つの辺の番号を格納します。そうすれば、後で各頂点のすべての辺を列挙できます (1 つの辺の番号を保存するだけで十分かと疑問に思うかもしれません。それは不可能です。各頂点は、そのすべての辺の番号を保存する必要があります。心配しないでください。読み続けてください)。たとえば、頂点 1 にエッジ "1 4 9" (このエッジの番号は 1) がある場合、first[1] の値は 1 に設定されます。頂点iにその頂点から始まる辺がない場合、first[i]の値は-1に設定されます。では、操作方法を見てみましょう。初期状態は以下のとおりです。

はぁ？上の図に次の配列が追加されているのはなぜですか? その機能は何ですか?心配しないでください。後で説明します。最初のエッジ「1 4 9」を読んでください。

最初のエッジ(1 4 9)を読み取り、このエッジの情報をu[1]、v[1]、w[1]に格納します。同時に、このエッジに番号が割り当てられます。このエッジは最初に読み込まれ、u、v、w 配列のインデックス 1 のセルに格納されるため、番号は 1 になります。このエッジの開始点は頂点1なので、first[1]の値を1に設定します。

さらに、この「番号1のエッジ」は、頂点番号1（つまりu[1]）を開始点とする最初のエッジなので、next[1]の値は-1に設定する必要があります。つまり、現在の「番号 i のエッジ」が u[i] を開始点として最初に見つかったエッジである場合、 next[i] の値は -1 に設定されます (この next 配列は非常に神秘的であるようです⊙_⊙)。

2番目のエッジ(4 3 8)を読み取り、このエッジの情報をu[2]、v[2]、w[2]に格納します。このエッジの番号は2です。このエッジの開始頂点は頂点4なので、first[4]の値を2に設定します。さらに、この「番号2のエッジ」は頂点4を開始点として見つかった最初のエッジなので、next[2]の値は-1に設定されます。

3番目のエッジ(1 2 5)を読み取り、このエッジの情報をu[3]、v[3]、w[3]に格納します。このエッジの番号は3で、開始頂点は頂点1です。頂点 1 にはすでに「番号 1 の辺」があることがわかります。first[1] の値を 3 に設定すると、「番号 1 の辺」は失われませんか?解決策はあります。next[3]の値を1に設定するだけです。これで、次の配列が何に使用されるかがわかりました。 next[i]には、「番号iのエッジ」の「前のエッジ」の番号が格納されます。

4番目のエッジ（2 4 6）を読み取り、このエッジの情報をu[4]、v[4]、w[4]に格納します。このエッジの番号は4で、開始頂点は頂点2なので、first[2]の値を4に設定します。さらに、この「番号4のエッジ」は頂点2を開始点として見つかった最初のエッジなので、next[4]の値は-1に設定されます。

5番目のエッジ(1 3 7)を読み取り、このエッジの情報をu[5]、v[5]、w[5]に格納します。このエッジの番号は5で、開始頂点は再び頂点1です。このとき、first[1]の値を5に、next[5]の値を3に設定する必要があります。

この時点で、頂点 1 のすべての辺をトラバースするのは非常に簡単です。頂点1の辺の1つの番号がfirst[1]に格納されます。残りのエッジは次の配列を通じて見つけることができます。下の写真をご覧ください。

注意深い生徒は、頂点エッジをトラバースするときのトラバース順序が、読み取り時の順序とまったく逆であることに気付くでしょう。各頂点にエッジを挿入する場合、そのエッジは「リンク リスト」の末尾ではなく先頭に直接挿入されるためです。しかし、これによって問題が発生することはありません。それがこの方法の優れた点です。

隣接リストを作成するコードは次のとおりです。

整数n、m、i;
 //u、v、wの配列サイズは実際の状況に応じて設定する必要があり、mの最大値より1大きくする必要があります。  
 int u[ 6 ],v[ 6 ],w[ 6 ];
 //firstとnextの配列サイズは実際の状況に応じて設定する必要があり、nの最大値より1大きくする必要があります。  
 int最初[ 5 ]、次[ 5 ];
 scanf( "%d %d" ,&n,&m);
 // 最初の配列の添え字 1～n の値を -1 に初期化します。これは、頂点 1～n には今のところ辺がないことを示します。  
 (i= 1 ;i<=n;i++)の場合
    最初[i]=- 1 ;
 (i= 1 ;i<=m;i++)の場合
{
    scanf( "%d %d %d" ,&u[i],&v[i],&w[i]); //各エッジを読み取ります 
     //次の2つの文が鍵となる 
    次[i] = 最初[u[i]];
    最初[u[i]]=i;
 }

次に各エッジをどのようにトラバースするのでしょうか?前に述べたように、最初の配列には実際には各頂点i ( i の範囲は1からn )の最初の辺が格納されます。たとえば、頂点1の最初のエッジはエッジ番号5 ( 1 3 7 ) であり、頂点 2 の最初のエッジはエッジ番号4 ( 2 4 6 ) であり、頂点3 には出力エッジがなく、頂点4の最初のエッジはエッジ番号2 ( 2 4 6 ) です。では、頂点1のすべての辺をどのように走査するのでしょうか?非常にシンプルです。次の図をご覧ください。

頂点1のすべてのエッジをトラバースするコードは次のとおりです。

 k=first[ 1 ]; // 頂点1の辺の1つの番号（実際には***によって読み込まれた辺）  
 while (k!=- 1 ) //残りのエッジは次の配列で順番に見つかります 
 {
    printf( "%d %d %d\n" ,u[k],v[k],w[k]);
    k = 次[k];
 }

各頂点のすべての辺を走査するコードは次のとおりです。

 (i= 1 ;i<=n;i++)の場合
{
    k=最初[i]; 
    一方(k!=- 1 )
    {
        printf( "%d %d %d\n" ,u[k],v[k],w[k]);
        k = 次[k];
    }
 }

隣接リストを使用してグラフを格納する場合の時間と空間の計算量は O( M ) であり、各エッジを走査する場合の時間の計算量もO( M ) であることがわかります。グラフが疎な場合、 M はN 2よりもはるかに小さくなります。したがって、スパース グラフを格納するには、隣接行列よりも隣接リストを使用する方がはるかに適切です。

オリジナルリンク: http://ahalei.blog..com/4767671/1391988