[图](3)邻接矩阵存储结构

在之前讨论的数据结构中,除了广义表和树以外,都可以有两类不同的存储结构,它们是由不同的映像方法(顺序映像和链式映像)得到的,由于图的结构比较复杂,任意两个顶点之间都可能存在联系,因此无法以数据元素在存储区中的物理位置来表示元素之间的关系

即图没有顺序映像的存储结构,但可以借助数组的数据类型表示元素之间的关系,另一方面,用多重链表表示图是自然的事,它是一种最简单的链式映像结构,即以一个由一个数据域和多个指针域组成的结点表示图的一个顶点。

其中数据域存储该顶点的信息,指针域存储指向其邻接点的指针,如下图所示:

image-20210123083540039

但是,由于图中各个结点的度数各不相同,最大度数和最小度数可能相差很多,因此,若按度数最大的顶点设计结点结构,则会浪费很多存储单元,反之,若按每个顶点自己的度数设计不同的结点结构,又会给操作带来不便

因此,和树类似,在实际应用中不宜采用这种结构,而应根据具体的图和需要进行的操作,设计恰当的结点结构和表结构,常用有邻接表、邻接多重表和十字链表,下面分别讨论。

邻接矩阵(数组表示法)

两个数组分别存储数据元素(顶点)的信息和数据元素之间的关系(边或弧)的信息

  • 建立一个顶点表(记录各个顶点信息)和一个邻接矩阵(表示各个顶点之间的关系)
  • 设图 A = (V,E)有n个顶点,则:

    • 顶点表Vexs[n]:
    • image-20210123054031410
  • 图的邻接矩阵是一个二维数组 A.arcsn,定义为:
  • image-20210123054645109

无向图的邻接矩阵表示法

两个顶点之间是邻接关系,则记为1,若没有邻接关系,则记为0,以二维数组表示有n个顶点的图时,需存放n个顶点信息和n²个弧信息的存储量,若考虑无向图的邻接矩阵的对称性则可采用压缩存储方式只存入矩阵的下三角(或上三角的元素)压缩矩阵笔记
image-20210123083441271

  • 无向图的邻接矩阵是对称的
  • 顶点 i 的度=第 i 行(列)中 1 的个数
  • 特别:无向完全图的邻接矩阵中,对角元素为0,其余为1

有向图的邻接矩阵表示法

在有向图当中,两个顶点之间的关系是有向的,我们称作弧(从一个顶点发出到另外一个顶点的),在有向图的邻接矩阵中。

  • 从当前顶点发出(以当前顶点作为起点)的弧,称作弧尾
  • 从其他顶点联结当前顶的弧,称作弧头
  • image-20210123061951221

以行表示弧头,以列表示弧尾,如下所示

image-20210123062111198

  • 在有向图的邻接矩阵中:

    • 第 i 行的含义:以结点Vi为尾的弧(即出度边)
    • 第 j 列的含义:以结点vi为头的弧(即入度边)
  • 有向图的邻接矩阵可能不对称的(有向完全图对称)
  • 顶点的出度=第 i 行元素之和
  • 顶点的入度=第 j 列的元素之和
  • 顶点的度=第i行元素之和+第j列元素之和

网(即赋权图)的邻接矩阵表示法

定义为:

image-20210123070712204

  • 若两顶点之间没有弧(边)则记录一个无穷大
  • 若两顶点之间有弧(边)则记录这条弧的权值

构造邻接矩阵

其形式描述如下所示:

//----------------图的数组(邻接矩阵)存储表示------------//
#define INFINITY INT_MAX//最大值∞
#define MAX_VERTEX_NUM 20//最大顶点个数

typedef enum{DG,DN,UDG,UDN}GraphKind; //{有向图,无向图,有向网,无向网}
typedef char VerTexType;//设顶点的数据类型为字符型

typedef struct ArcCell {
    VRType adj;//VRType是顶点关系类型,对无权图,用1或0表示相邻否;对带权图,则为权值类型
    InfoType* info;//该弧相关信息的指针
}ArcCell, AdjMatrix[MAX_VERTEX_NUM][MAX_VERTEX_NUM];

typedef struct {
    VertexType vexs[MAX_VERTEX_NUM];//顶点向量,VertexType表示顶点的数据类型
    AdjMatrix arcs;//邻接矩阵
    int vexnum, arcnum;//图的当前顶点数和弧(边)数
    GraphKind kind;//图的种类标志
}MGraph;

从上述可以看到,我们需要:

  • 一个一维数组表示顶点信息
  • 一个二维数组表示邻接矩阵

    • 这个二维数组是一个n×n的矩阵(n是顶点数量)
下面给出建立无向网的算法
步骤如下:
  1. 确定图的顶点个数和边的个数
  2. 输入顶点信息存储在一维数组vertex中
  3. 初始化邻接矩阵arc
  4. 依次输入每条边存储在邻接矩阵arc中

    1. 输入边依附的两个顶点的序号i,j,以及该边附加的权值
    2. 将邻接矩阵的第 i 行 第 j 列 的元素值置为权值
    3. 由于无向图的邻接矩阵是对称的,将第 j 行 第 i 列的元素值置为权值
Status CreateGraph(MGraph* G) {
    scanf("%d", &G->kind);//输入图的类型
    switch (G->kind) {
    //case DG:return CreateDG(G);
    //case DN:return CreateDN(G);
    //case UDG:return CreateUDG(G);
    case UDN:return CreateUDN(G);
    default: return ERROR;
    }
}
//定位函数
int LocateVex(MGraph G, char e) {
    int i = 0;
    while (i < G.vexnum) {
        if (G.vexs[i] == e) return i;
        i++;
    }
    return -1;
}

Status CreateUDN(MGraph* G) {
    char tem;//过滤换行符
    scanf("%d,%d%c", &G->vexnum, &G->arcnum,&tem);
    for (int k = 0; k < G->vexnum; k++) scanf("%c%c", &G->vexs[k],&tem);//构造顶点表

    //初始化邻接矩阵
    for (int i = 0; i < G->vexnum; i++)
        for (int j = 0; j < G->vexnum; j++) 
            G->arcs[i][j].adj = INFINITY;

    char v1, v2;
    int i, j, weight;
    for (int k = 0; k < G->arcnum; k++) {
        //通过边的信息构造矩阵
        i = j = 0;
        printf("输入边信息:");
        scanf("%c,%c,%d%c", &v1, &v2, &weight, &tem);
        i = LocateVex(*G, v1);//在顶点表中定位
        j = LocateVex(*G, v2);
        G->arcs[i][j].adj = weight;//输入权值
        G->arcs[j][i].adj = weight;    //置<v1,v2>的对称边<v2,v1>
    }
    PrintUDN_AdjMatrix(*G);
    return OK;
}
Status PrintUDN_AdjMatrix(MGraph G) {
    for (int i = 0; i < G.vexnum; i++) {
        for (int j = 0; j < G.vexnum; j++) {
            if (G.arcs[i][j].adj == INFINITY) printf("∞ ");
            else printf("%d ", G.arcs[i][j]);
        }
        printf("\n");
    }
    return OK;
}

由上述可以很简单的创建出 [无向图,有向图,有向网] 的邻接矩阵,简单来说:

  • 有向图:弧(i,j)在图中由于是有向的,所以只需要在第 i 行 第 j 列 标记为1(代表从 第 i 个 结点出发到第 j 个 结点)
  • 无向图:边<i,j>在图中是无向的,需要在 第 i 行 第 j 列 和第 j 行 第 i 列 标记为 1(表示该边两端点为i 和 j)
  • 有向网:弧(i,j)在图中是有向的,并且附加权值,需要在 第 i 行 第 j 列标记为其权值(代表从 第 i 个 结点出发到 第 j 个 结点)

[完整代码点击此处下载]

在这个存储结构上也易于实现一些基本操作,比如:FIRST_ADJ(G,v)找v的第一个邻接点,首先,由LOC_VERTEX(G,v)找到v在图G中的位置,即v在一维数组vexs中的序号i,则二维数组arcs中第i行上第一个adj域的值为"1"的分量所在的列号j ,便为 v 的第一个邻接点在图G中的位置,同理,下一个邻接点在图G中的位置便为 j 列之后第一个adj域的值为"1"的分量所在列号

邻接矩阵的优点
  • 直观、简单、好理解

    • 方便检查任意一对顶点间是否存在边
    • 方便找任一顶点的所有"邻接点"(有边直接相连的当的)
    • 方便计算任一顶点的”度“(从该点发出的边数为”出度“,指向该点的边数为”入度“)

      • 无向图:对应行(或列)非0元素的个数
      • 有向图:对应行非0元素的个数是”出度“,对应列非0元素的个数是”入度“
邻接矩阵的缺点
  • 不便于增加和删除结点
  • 浪费空间——存稀疏图(点很多而边很少)有大量无效元素

    • 对稠密图(特别是完全图)还是很合算的
  • 浪费时间——统计稀疏图中一共有多少条边,在稀疏图当中,边很少,顶点相对来说很多,一一也要遍历整个矩阵来求得

本文链接:

https://nullcode.fun/124.html
1 + 6 =
快来做第一个评论的人吧~