图的邻接矩阵 Feel之家 ITeye技术网站

图的邻接矩阵

博客分类：
数据结构
网络应用 J#
1．图的邻接矩阵表示法

    　在图的邻接矩阵表示法中：

① 用邻接矩阵表示顶点间的相邻关系
② 用一个顺序表来存储顶点信息

2．图的邻接矩阵(Adacency Matrix)

    　设G=(V，E)是具有n个顶点的图，则G的邻接矩阵是具有如下性质的n阶方阵：


【例】下图中无向图G₅
和有向图G₆
的邻接矩阵分别为A_l
和A₂
。

    从图的邻接矩阵表示法中可以得到如下结论：
（1）对于n个顶点的无向图，有A（i，i）=0，1≤i≤n。

（2）无向图的邻接矩阵是对称的，即A（i，j）=A（j，i），1≤i≤n，1≤j≤n。

（3）有向图的邻接矩阵不一定对称的。因此用邻接矩阵来表示一个具有n个顶点的有向图时需要n²
个单位来存储邻接矩阵；对有n个顶点的无向图则需存入上（下）三角形，故只需n（n+1）/2个单位。

（4）无向图的邻接矩阵的第i行（或第i列）非零元素的个数正好是第i个顶点的度TD（v_i
）。

（5）有向图的邻接矩阵的第i行（或第i列）非零元素的个数正好是第i个顶点的出度OD（v_i

）[或入度ID（v_i
）]。

3．网（带权值的图）的邻接矩阵

    　若G是网络，则邻接矩阵可定义为：







其中：

      w_ij
表示边上的权值；

      ∞表示一个计算机允许的、大于所有边上权值的数。

【例】下面(a)是一个带权图，（b）是对应的邻接矩阵的存储结构

       （a）带权图
                       （b）邻接矩阵

4．邻接矩阵的图类

const int MaxVertices=10;

const int MaxWeight=32767;

class AdjMWGraph

{ private:

   int Vertices[10];    //顶点信息的数组

   int Edge[MaxVertices][MaxVertices];
//边的权值信息的矩阵

int numE; //当前的边数

int numV; //当前的顶点数

public: ………; //公有函数

private: ………; //私有函数

}

注意：

    ① 在简单应用中，可直接用二维数组作为图的邻接矩阵（顶点表及顶点数等均可省略）。

    　② 当邻接矩阵中的元素仅表示相应的边是否存在时，EdgeTyPe可定义为值为0和1的枚举类型。

    　③ 无向图的邻接矩阵是对称矩阵，对规模特大的邻接矩阵可压缩存储。

    　④ 邻接矩阵表示法的空间复杂度S(n)=0(n²
)。