假设节点为[a,b,c,d],在邻接矩阵中,

  • 无向图:如果v1到v2有边,则邻接矩阵M[v_1][v_2]=M[v_2][v_1]=1,否则=0.

    M[0]中的值为1的元素的个数为a(节点0)的度,M[i][0]中的值为1的元素的个数也为a(节点0)的度,因为在无向图中,邻接矩阵是以对角线对称的。

  • 有向图:M[0]中的值为1的元素的个数为a(节点0)的出度,M[i][0]中的值为1的元素的个数也为a(节点0)的入度

  • 带权图:如果v1到v2有边,则邻接矩阵M[v_1][v_2]=W_1_2, 否则为正无穷

优点:

  • 快速判断两顶点是否有边
  • 方便计算各顶点的度

缺点

  • 不便于增删节点
  • 不便于访问所有邻接点
  • 空间复杂度高,如果图比较稀疏,会造成空间浪费

评论