隣接行列表現,グラフの



  • V個のノードを持つグラフにおいて、V行V列の行列によってエッジのありなしを表現する方法。エッジに重み(距離など)がない場合にはブール値。無向グラフの場合はa¥[x¥]¥[y¥] = a¥[y¥]¥[x¥]、有向グラフの場合は、a¥[x¥]¥[y¥] ¥not= a¥[y¥]¥[x¥]。対角成分は、trueで統一するかfalseで統一するか、用途により使い分ける。
  • V^2のメモリを要求し、エッジの読み込み→隣接行列化にV^2ステップを必要とするので、疎グラフでは非効率である。出来上がる行列は、エッジ情報の入力順序に依存しない