邻接矩阵

一、基本概念

邻接矩阵(Adjacency Matrix)的存储结构,就是用一维数组存储图中顶点的信息,用一个二维数组表示图中各顶点之间的邻接关系信息。这个二维数组称为邻接矩阵。假设图G = (V, E)有 n 个确定的顶点,即 V = {v0,v1,…,vn−1},则表示 G 中各顶点相邻关系为一个 n×n 的矩阵,矩阵的元素为:

邻接矩阵中的元素

若G是带权图,则邻接矩阵可定义为:

邻接矩阵的定义

其中,wij 表示边(vi,vj)或弧 <vi,vj> 上的权值;∞ 表示一个计算机允许的、大于所有边上权值的数。

用邻接矩阵表示法表示无向图:
无向图的邻接矩阵表示法

用邻接矩阵表示法表示带权图:
带权图的邻接矩阵表示法

二、邻接矩阵存储的特点

  1. 无向图的邻接矩阵一定是一个对称矩阵。因此,在具体存放邻接矩阵时,只需存放上(或下)三角矩阵的元素即可。有向图的邻接矩阵不一定是对称矩阵。

  2. 对于无向图,邻接矩阵的第 i 行(或第 i 列)非零元素(或非 ∞ 元素)的个数正好是第 i 个顶点的度 D(vi)。

  3. 对于有向图,邻接矩阵的第 i 行(或第 i 列)非零元素(或非 ∞ 元素)的个数正好是第 i 个顶点的出度 OD(vi)(或入度 ID(vi))。

  4. 用邻接矩阵方法存储图,很容易确定图中任意两个顶点之间是否有边相连。但是,要确定图中有多少条边,则必须按行、列对每个元素进行检测,所花费的时间代价很大。这是用邻接矩阵存储图的局限性。

  5. 在邻接矩阵表示法中,如果是顶点很多而边很少的图,将会表示成一个稀疏矩阵。这不仅浪费空间,而且使一些算法变得很慢。

三、图的邻接矩阵存储表示

在用邻接矩阵存储图时,除了用一个二维数组存储用于表示顶点间相邻关系的邻接矩阵外,还需用一个一维数组存储顶点信息,另外还有图的顶点数和边数。故可将其形式描述如下:

typedef int VertexType;

typedef int Edgetype;

#define MaxVertexNum 30

class MGraph {
  public:
    MGraph();       //默认构造函数

    MGraph::~MGraph();     //默认析构函数

    void CreatGraph();     //建立图的存储矩阵成员函数

    void Visit(int v);

    void MGraph::BFStraverse();  //广度遍历图

    void MGraph::BFS(int v);   //从顶点 v 开始广度遍历图

    int MGraph::MaxOutdegree();
    
    //以邻接矩阵为存储结构,判断 vi 和 vj 之间是否有路径,
    //若有,返回 1,否则返回 0
    int MGraph::IsPath_DFS(int i, int j); 

    //以邻接矩阵为存储结构,判断 vi 和 vj 之间是否有路径,
    //若有,返回 1,否则返回 0
    int MGraph::IsPath_BFS(int i, int j); 

    void Init_Visit_Flag();   //初始化访问数组标志

  private:
    VertexType vertexs[MaxVertexNum];   //顶点表

    Edgetype arcs[MaxVertexNum][MaxVertexNum]; //邻接矩阵,即边表

    int vertexNum, edgeNum;    //顶点数和边数

    int visited[MaxVertexNum];    //访问标志数组
};

其中,建立一个图的邻接矩阵存储的算法如下:

//建立有向图 G 的邻接矩阵存储
void MGraph::CreatGraph() {
  int i, j, k;

  cin >> vertexNum >> edgeNum;  //输入顶点数和边数

  for(i=0; i < vertexNum; i++)
    cin >> vertexs[i];   //输入顶点信息, 建立顶点表

  for(i = 0; i < vertexNum; i++)
    for(j = 0; j < vertexNum; j++)
      arcs[i][j]=0;   //初始化邻接矩阵

  for(k=0; k < edgeNum; k++) {
    cin >> i >> j;   //输入 e 条边, 建立邻接矩阵
    arcs[i][j] = 1;  //若加入arcs[j][i]=1, 则为无向图的邻接矩阵存储建立
  }
}

对于带权图邻接矩阵的建立方法是:首先将矩阵的每个元素都初始化。如果 i = j,则使 arcs[i][j] = 0,否则为 ∞(若图的权值为整数,则定义为最大整数;若为实数,则定义为最大实数)。然后读入边及权值(i,j,wij),将矩阵的相应元素置为 wij

用户头像
登录后发表评论