Tim的资源站

一、基本概念

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

若G是带权图，则邻接矩阵可定义为：

其中，w_ij 表示边（v_i，v_j）或弧 <v_i，v_j> 上的权值；∞ 表示一个计算机允许的、大于所有边上权值的数。

用邻接矩阵表示法表示无向图：

用邻接矩阵表示法表示带权图：

二、邻接矩阵存储的特点

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

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

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

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，w_ij），将矩阵的相应元素置为 w_ij。