隣接行列では、与えられた頂点の隣同士をどのように見つけるか？

Question

のは、我々はこのような4x4の隣接行列があるとしましょう：の私は、頂点1の隣人の隣人を見つけ、リストに追加するにはどうすればよいint v=1

を言わせて、

と与えられた頂点を？たとえば、頂点1から頂点4に移動したい場合は、最初に頂点2に移動し、頂点2から頂点4に移動する必要があります。これは、1から4までの直接パスがないためです。リストに似ています。

が今ここに私が得たものである：

int v=1; 
for(int i=0;i<adjmat.length;i++){ 
      if (i==v){ 
       for(int j=0;j<adjmat[i].length;j++){ 
        if (j!=i){ // self loops do not count 
         // if adjmat[i][j] has a neighbor, add the neighbor to a list 
        } 
       } 
      } 
     } 

Answer 1

あなたが持っているどのような正しいように思えます。

ほんの少しのノート： あなたのグラフィックは、ループが0から始まるときに1から始まるインデックスを持っています。おそらくこれは心配していませんが、いずれの場合でも頂点の名前は1から始まり、あなたの配列は0から始まります。

そして最も唯一の懸念は、最も外側のループです。あなたが唯一の頂点vの隣人の隣人を見つける必要がある場合は（あなたの例を、V = 1）

int v_i = v-1; 
for(int j=0;j<adjmat[v_i].length;j++){ 
    if (v_i!=j){ // self loops do not count 
     // if adjmat[i][j] has a neighbor, add the neighbor to a list 
     //*NOTE maybe only if that neighbor is also not a self loop, one of v's first neighbors, or v 
    } 
} 

Answer 2

Aは隣接行列である場合は、A^2と内積のための行列の掛け算によって構築を検討ORで合計します。部材

A^2(i,j) = OR(k){ A(i,k) AND A(k,j) } 

の値は、これがiはkに接続され、kがjに接続されるようkが存在する場合iがjに接続されていると言います。したがって、この行列は、元のグラフの2つのエッジで接続できるすべての頂点のペアを接続することによって形成されたグラフです。