图的存储结构

1．图的邻接矩阵

1）定义：

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

　① 用邻接矩阵表示顶点间的相邻关系

　② 用一个顺序表来存储顶点信息

设G=(V，E)是具有n个顶点的图，则G的邻接矩阵是具有如下性质的n阶方阵：A[i,j]=1,if (vi,vj)是E（G）中的边

  A[i,j]=0,if (vi,vj)不是E（G）中的边

      

2）从图的邻接矩阵表示法中可以得到如下结论：

（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（vi）。

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

 

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

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

  A[I,j]=Wij           if (Vi,Vj)是E(G)中的边

  A[I,j]=0或是无穷大  if (Vi,Vj)不是E(G)中的边

  其中：

      wij表示边上的权值；

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

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(n2)。

2.图的邻接链表
     邻接链表（Adjacency List）是图的一种链式存储结构，与树型结构中的孩子链表相似。通常邻接链表也称邻接表。
1） 邻接表的结点结构
边结点结构

data   adjvex

邻接表中每个表结点均有两个域:
　① 邻接点域adjvex
　　存放与vi相邻接的顶点v_j的序号j。
　② 链域next
　　将邻接表的所有表结点链在一起。
  注意：

　    如果带权图，则在表结点中还应增加一个保存权值等相关信息info。

dest  weight   next

2) 邻接表的表示

    　对于无向图，v_i的邻接表中每个表结点都对应于与v_i相关联的一条边。因此，将邻接表的表头向量称为顶点表。将无向图的邻接表称为边表。
  注意：

    n个顶点e条边的无向图的邻接表表示中有n个顶点表结点和2e个边表结点。
    对于有向图，v_i的邻接表中每个表结点都对应于以v_i为始点射出的一条边。因此，将有向图的邻接表称为出边表。
  注意：

    n个顶点e条边的有向图，它的邻接表表示中有n个顶点表结点和e个边表结点。

3) 有向图的逆邻接表
        在有向图中，为图中每个顶点v_i建立一个入边表的方法称逆邻接表表示法。入边表中的每个表结点均对应一条以v_i为终点(即射入v_i)的边。