AI 助理
备案控制台
开发者社区 人工智能 文章 正文

数据结构学习笔记——图的存储结构（邻接矩阵和邻接表）

2022-11-01 4295
版权
版权声明：
本文内容由阿里云实名注册用户自发贡献，版权归原作者所有，阿里云开发者社区不拥有其著作权，亦不承担相应法律责任。具体规则请查看《 阿里云开发者社区用户服务协议》和 《阿里云开发者社区知识产权保护指引》。如果您发现本社区中有涉嫌抄袭的内容，填写 侵权投诉表单进行举报，一经查实，本社区将立刻删除涉嫌侵权内容。
简介： 数据结构学习笔记——图的存储结构（邻接矩阵和邻接表）

前言


图的常用存储结构有邻接矩阵和邻接表，另外还有十字链表、邻接多重表等等。


一、邻接矩阵


图的邻接矩阵存储结构用于表示顶点之间的相邻关系，其中通过一个一维数组存储顶点，一个二维数组存储顶点之间的相邻关系，一个顶点数为n的图的邻接矩阵是n×n（n行n列），即一个方阵，用邻接矩阵方法来表示一个图需要n2个存储空间，它只与图中的顶点数有关，其空间复杂度为O(n2)。


（一）图的邻接矩阵表示


设图G=(V，E)，若顶点是E(G)中的边，则用1标记，记为A[i][j]=1；若顶点不是E(G)中的边，则用0标记，记为A[i][j]=0。


✨通过邻接矩阵存储图时，其邻接矩阵是唯一的。

例如，下面是一个无向图：

1667295039603.jpg

该无向图的邻接矩阵为：

1667295054765.jpg


✨对于一个无向图，其邻接矩阵的主对角线一定为零，另外无向完全图中，其邻接矩阵的主对角线为0，其余元素都为1，其任意两个顶点之间都有边连接。

例如，下面是一个无向完全图：

1667295062226.jpg

其邻接矩阵表示如下：

1667295071184.jpg

下面是一个有向图：

1667295078856.jpg

其邻接矩阵表示如下：

1667295087349.jpg


（二）图的邻接矩阵性质


✨由于邻接矩阵是方阵，所以图的顶点数等于邻接矩阵的行或列的数目。

例如以下是一个图的邻接矩阵，由于该邻接矩阵是4×4，即该图的顶点数为4。


1667295097681.jpg


✨对于一个含有n个顶点，e条边的无向图，其邻接矩阵中元素为零的个数为n2-2e。

例如，如下这个邻接矩阵，若它是无向图，求其共有多少条边。

1667295109782.jpg



可知该邻接矩阵是3×3，即该图的顶点数为3，n=3，又由于是无向图，其邻接矩阵中元素为零的个数为5，由n2-2e，即5=9-2e，解得e=2，故无向图中共有2条边。


✨无向图的邻接矩阵一定是对称矩阵，关于对角线对称，且主对角线一定为零（只针对简单图），而有向图的邻接矩阵不一定是对称矩阵；另外，0若一个图的邻接矩阵是对称的，则它可以是无向图或有向图。

1667295118264.jpg

由于无向图的邻接矩阵存在对称关系，其上三角和下三角的相同的，所以当在存储邻接矩阵时，除了对角线都为0以外，其实只需要存储上三角或下三角的数据，故只需要n(n-1)/2个存储空间。


只存储上三角或下三角的数据，即1+2+3+……+(n-1)=n(n-1)/2。


✨对于无向图，顶点vi的度为其邻接矩阵中第i行（或第i列）的非零元素的个数；而有向图中，对于顶点i，邻接矩阵中第i行非零元素的个数和第i列非零元素的个数对应该顶点的出度OD(vi)和入度ID(vi)，又由于有向图中度等于出度和入度之和，即顶点vi的度为其邻接矩阵中第i行和第i列的非零元素的个数之和。

image.png


若对于带权的图，即网，在有关度的运算时，只需将非零元素的个数替换成非∞元素的个数即可，例如对于无向图中，顶点vi的度为其邻接矩阵中第i行（或第i列）的非∞元素的个数。


例、设图的邻接矩阵A如下所示，求各顶点的度依次是_______。


1667295143979.jpg

首先，可知该邻接矩阵不对称，所以图为有向图，有向图的度为入度和出度之和，

所以各顶点的度为邻接矩阵中每行和每列之和，出度对应行，入度对应列，

即，V1=1+1+1=3，V2=1+1+1+1=4，V3=1+1=2，V4=1+1+1=3

即3，4，2，3。


✨若邻接矩阵为对称矩阵，当图为有向图时，图的弧的数目等于邻接矩阵中非零元素的个数；当为无向图，则图的边数等于邻接矩阵中非零元素的一半。


（三）网的邻接矩阵表示


带权的图称为网，设图G=(V，E)，若顶点vi与顶点vj之间有边，则记为A[i][j]=Wij，即对应邻接矩阵对应项中存放边的权值；若顶点vi与顶点vj不相连，两个顶点间不存在边，则用∞标记，记为A[i][j]=∞，这里的∞是一个大于所有边的权值。

例如，下面是一个无向网，带有权值：

1667295199343.jpg

其邻接矩阵表示如下：

1667295207928.jpg

例如，下面是一个有向网，带有权值：

1667295214966.jpg

其邻接矩阵表示如下：

1667295222855.jpg


邻接矩阵存储图代码


以下代码可用于求有向图或无向图的邻接矩阵，只需修改其中一句代码（详细见图的邻接矩阵建立）。


（一）图的邻接矩阵定义


可自行定义MAXSIZE，即顶点数目的最大值，顶点的数据类型为char类型，边的数据类型为int类型，如下代码：

#define MAXSIZE 100
typedef struct {
  int n,e;      //图的顶点数目、图的边数目
  char V[MAXSIZE];    //一维数组，存储顶点
  int E[MAXSIZE][MAXSIZE];  //二维数组，边的邻接矩阵
} Graph;


（二）初始化邻接矩阵


初始化邻接矩阵，将邻接矩阵中的所有元素都置为0，通过for循环嵌套完成，如下代码：

/*初始化邻接矩阵*/
void InitGraph(Graph *G) {
  int i,j;
  for(i=0; i<G->n; i++)
  for(j=0; j<G->n; j++)
    G->E[i][j]=0;
}


（三）图的邻接矩阵建立


针对无向图和有向图，由于无向图中边连接边的两个顶点与有向图中不同，所以只需对if条件语句进行修改。

对于无向图时：

for(k=0; k<G->e; k++) {
  scanf("%c",&X); 
  printf("建立第%d条边（以逗号隔开）：",k+1);
  scanf("%c,%c",&ch1,&ch2);
  for(i=0; i<G->n; i++)
  for(j=0; j<G->n; j++)
    if(ch1==G->V[i]&&ch2==G->V[j]) {
    G->E[i][j]=1;
    G->E[j][i]=1;  /*对于有向图，可以去掉这行代码，而无向图需加上*/
    }
}


对于有向图时，加上G->E[j][i]=1：

for(k=0; k<G->e; k++) {
  scanf("%c",&X); 
  printf("建立第%d条边（以逗号隔开）：",k+1);
  scanf("%c,%c",&ch1,&ch2);
  for(i=0; i<G->n; i++)
  for(j=0; j<G->n; j++)
    if(ch1==G->V[i]&&ch2==G->V[j])
    G->E[i][j]=1;
}


完整代码如下：

/*图的邻接矩阵建立*/
void CreateGraph(Graph *G) {
  int i,j,k;
  char ch1,ch2,X;
  printf("请输入图的顶点数目：");
  scanf("%d",&G->n);
  printf("请输入图的边的数目：");
  scanf("%d",&G->e);
  printf("请输入各顶点的信息：\n");
  for(i=0; i<G->n; i++) {
  scanf("%c",&X); 
  printf("输入第%d个顶点：",i+1);
  scanf("%c",&(G->V[i]));
  }
  for(k=0; k<G->e; k++) {
  scanf("%c",&X); 
  printf("建立第%d条边（以逗号隔开）：",k+1);
  scanf("%c,%c",&ch1,&ch2);
  for(i=0; i<G->n; i++)
    for(j=0; j<G->n; j++)
    if(ch1==G->V[i]&&ch2==G->V[j]) {
      G->E[i][j]=1;
      G->E[j][i]=1;  /*对于有向图，可以去掉这行代码，而无向图需加上*/
    }
  }
}


（四）输出邻接矩阵

/*输出邻接矩阵*/
void PrintGraph(Graph G) {
  int i,j;
  for(i=0; i<G.n; i++) {
  for(j=0; j<G.n; j++)
    printf("%d  ",G.E[i][j]);
  printf("\n");
  }
}


例如，下面是个无向完全图，求其邻接矩阵。

1667295307450.jpg

可知该图有4个顶点，6条边，顶点信息分别为A、B、C、D，边分别为A,B、A,C、A,D、B,C、B,D、C,D。

代码如下：

#include <stdio.h>
#define MAXSIZE 100
typedef struct {
  int n,e;      //图的顶点、图的边
  char V[MAXSIZE];    //一维数组，存储顶点
  int E[MAXSIZE][MAXSIZE];  //二维数组，存储顶点之间关系
} Graph;
/*初始化邻接矩阵*/
void InitGraph(Graph *G) {
  int i,j;
  for(i=0; i<G->n; i++)
  for(j=0; j<G->n; j++)
    G->E[i][j]=0;
}
/*图的邻接矩阵建立*/
void CreateGraph(Graph *G) {
  int i,j,k;
  char ch1,ch2,X;
  printf("请输入图的顶点数目：");
  scanf("%d",&G->n);
  printf("请输入图的边的数目：");
  scanf("%d",&G->e);
  printf("请输入各顶点的信息：\n");
  for(i=0; i<G->n; i++) {
  scanf("%c",&X); 
  printf("输入第%d个顶点：",i+1);
  scanf("%c",&(G->V[i]));
  }
  for(k=0; k<G->e; k++) {
  scanf("%c",&X); 
  printf("建立第%d条边（以逗号隔开）：",k+1);
  scanf("%c,%c",&ch1,&ch2);
  for(i=0; i<G->n; i++)
    for(j=0; j<G->n; j++)
    if(ch1==G->V[i]&&ch2==G->V[j]) {
      G->E[i][j]=1;
      G->E[j][i]=1;
    }
  }
}
/*输出邻接矩阵*/
void PrintGraph(Graph G) {
  int i,j;
  for(i=0; i<G.n; i++) {
  for(j=0; j<G.n; j++)
    printf("%d  ",G.E[i][j]);
  printf("\n");
  }
}
/*主函数*/
int main() {
  Graph G;
  InitGraph(&G);      //初始化邻接矩阵 
  CreateGraph(&G);    //建立邻接矩阵 
  printf("图的邻接矩阵为：\n");
  PrintGraph(G);      //输出邻接矩阵 
}


运行结果如下：

1667295334548.jpg

例如，下面是个有向图，求其邻接矩阵。

1667295345057.jpg

可知该图有4个顶点，5条边，顶点信息分别为A、B、C、D，边分别为B,A、B,C、B,D、C,A、D,C。

代码如下：

#include <stdio.h>
#define MAXSIZE 100
typedef struct {
  int n,e;      //图的顶点、图的边
  char V[MAXSIZE];    //一维数组，存储顶点
  int E[MAXSIZE][MAXSIZE];  //二维数组，存储顶点之间关系
} Graph;
/*初始化邻接矩阵*/
void InitGraph(Graph *G) {
  int i,j;
  for(i=0; i<G->n; i++)
  for(j=0; j<G->n; j++)
    G->E[i][j]=0;
}
/*图的邻接矩阵建立*/
void CreateGraph(Graph *G) {
  int i,j,k;
  char ch1,ch2,X;
  printf("请输入图的顶点数目：");
  scanf("%d",&G->n);
  printf("请输入图的边的数目：");
  scanf("%d",&G->e);
  printf("请输入各顶点的信息：\n");
  for(i=0; i<G->n; i++) {
  scanf("%c",&X); 
  printf("输入第%d个顶点：",i+1);
  scanf("%c",&(G->V[i]));
  }
  for(k=0; k<G->e; k++) {
  scanf("%c",&X); 
  printf("建立第%d条边（以逗号隔开）：",k+1);
  scanf("%c,%c",&ch1,&ch2);
  for(i=0; i<G->n; i++)
    for(j=0; j<G->n; j++)
    if(ch1==G->V[i]&&ch2==G->V[j]) {
      G->E[i][j]=1;
      //G->E[j][i]=1;
    }
  }
}
/*输出邻接矩阵*/
void PrintGraph(Graph G) {
  int i,j;
  for(i=0; i<G.n; i++) {
  for(j=0; j<G.n; j++)
    printf("%d  ",G.E[i][j]);
  printf("\n");
  }
}
/*主函数*/
int main() {
  Graph G;
  InitGraph(&G);      //初始化邻接矩阵 
  CreateGraph(&G);    //建立邻接矩阵 
  printf("图的邻接矩阵为：\n");
  PrintGraph(G);      //输出邻接矩阵 
}


运行结果如下：

1667295372601.jpg


二、邻接表


（一）邻接表表示


邻接表方法采用顺序存储结构和链式存储结构来存储图，对于图中每个顶点vi，将所有邻接于vi的顶点连成一个单链表，即这个单链表就称为顶点vi的邻接表，另外还需将所有顶点的邻接表放进数组中，通过邻接表存储图所用的空间大小取决于图的顶点数和边的个数，顶点数n决定了顶点表的空间大小，边的个数决定了边表结点的空间大小。


由于图G=(V，E)，即需要在邻接表中定义两种结点结构，即顶点表和边表，另外若边上带有权值，则还需中边表上添加一个信息代表权值。顶点表中除了数据域用于存储顶点信息，还有指向第一条与其邻接顶点的指针域；边表中由邻接点域和指向下一条邻接边的指针域组成。


1667295392591.jpg

#define MAXSZIE 100
/*边表结点定义（不带权值的图的边表）*/
typedef struct Node {
  int adjvex;   //邻接点域
  struct Node *next;  //指向下一条邻接边的指针域
} EdgeNode;
/*顶点表结点定义*/
typedef struct VexNode {
  int data;    //数据域
  EdgeNode *firstedge;  //指向第一条邻接该顶点的指针域
} VHeadNode;
typedef struct {
  VHeadNode list[MAXSZIE];  //邻接表头结点数组
  int n,e;      //顶点数和边数
} List;


例如，下面这个无向完全图：

1667295413114.jpg

为其编号如下：

1667295421106.jpg

其邻接表表示如下：

1667295428186.jpg

例如，下面这个有向图：

1667295435469.jpg

为其编号如下：

1667295442323.jpg

其邻接表表示如下：

1667295449901.jpg


（二）逆邻接表表示


与邻接表相反，逆邻接表表示的是顶点的入度邻接情况，即为每个顶点vi建立一个以vi为弧头的单链表，如下：

1667295460461.jpg

该有向图的邻接表和逆邻接表表示如下：

1667295468507.jpg


（三）邻接表的性质


✨通过邻接表存储图时，其邻接表并不唯一，这与邻接矩阵相反，是由于单链表中各边结点的连接顺序是任意的。

在邻接表表示中，对于无向图，由于同一条边连着两个顶点，所以相当于每条边在邻接表存储中被存储了两遍，而对于有向图则没有，所以：


✨在一个有n个顶点、e条边的无向图或有向图中，采用邻接表存储，无向图需要n个单链表表头指针和2e个边结点；而有向图需要n个单链表表头指针和e个边结点。

可以通过邻接表看出图中顶点的度，但无向图和有向图的度不一样，如下：


✨对于无向图，顶点vi的度为第i个单链表的结点数；而对于有向图，顶点vi的出度为第i个单链表的结点数，其入度为邻接表中所有单链表的邻接点域值为i的边结点个数。

对于要频繁计算有向图中顶点入度和出度的情况，可以另外建立一个逆邻接表，与有向图的邻接表相比，邻接表表示的是顶点的出度邻接情况，而相反，其逆邻接表表示的是顶点的入度邻接情况。


三、邻接多重表


邻接多重表是一种链式存储结构，用于表示无向图，邻接多重表也是由顶点表和边表组成，每个顶点由两个域组成，data域用于存储顶点的信息，firstedge域用于指向第一条与其邻接的边，顶点表的结构如下：

data firstedge


由于无向图的特点，一条边两个结点，所以每个边结点同时连接在两个链表中，相对于邻接表，邻接多重表同一条边只需一个结点表示，边表的结构如下：

mark ivex ilink jvex jlink info


首先，mark域为标识域，用于表示该边是否被访问过；ivex和jvex为该边邻接的两个顶点在图中的位置；ilink和jlink用于指向下一个邻接顶点ivex和jvex的边；info用于指向和边相关的各种信息的指针域。


四、十字链表


十字链表也是一种链式存储结构，用于表示有向图，data域用于存储顶点的信息，firstin和firstout域分别指向以该顶点弧头或弧尾的第一个弧结点，顶点表的结构如下：

data firstin firstout


十字链表中在表示弧时将其视为一个结点，tailvex和headvex域，分别表示弧的弧尾和弧头在图中的位置，hlink指向弧尾相同的下一条弧，tlink 指向弧头相同的下一条弧，info用于指向该弧的信息，从而使相同的弧尾和弧头分别在不同的一个链表上，弧结点表的结构如下：

tailvex headvex hlink tlink info


文章标签：
机器学习/深度学习
人工智能
存储
关键词：
数据结构学习笔记
数据结构存储
数据结构结构
数据结构邻接矩阵
数据结构邻接表
游客5pa3gelrqbo2g
目录
相关文章
小徐在进步
|
26天前
|
存储 算法 C语言
数据结构基础详解(C语言): 二叉树的遍历_线索二叉树_树的存储结构_树与森林详解
本文从二叉树遍历入手，详细介绍了先序、中序和后序遍历方法，并探讨了如何构建二叉树及线索二叉树的概念。接着，文章讲解了树和森林的存储结构，特别是如何将树与森林转换为二叉树形式，以便利用二叉树的遍历方法。最后，讨论了树和森林的遍历算法，包括先根、后根和层次遍历。通过这些内容，读者可以全面了解二叉树及其相关概念。
小徐在进步
31 6
小徐在进步
|
26天前
|
存储 机器学习/深度学习 C语言
数据结构基础详解(C语言): 树与二叉树的基本类型与存储结构详解
本文介绍了树和二叉树的基本概念及性质。树是由节点组成的层次结构，其中节点的度为其分支数量，树的度为树中最大节点度数。二叉树是一种特殊的树，其节点最多有两个子节点，具有多种性质，如叶子节点数与度为2的节点数之间的关系。此外，还介绍了二叉树的不同形态，包括满二叉树、完全二叉树、二叉排序树和平衡二叉树，并探讨了二叉树的顺序存储和链式存储结构。
小徐在进步
19 3
aliyun6365824167
|
2月前
|
存储 算法 测试技术
【初阶数据结构篇】实现顺序结构二叉树（堆的实现方法）
注意传过去的参数是插入的位置，即插入前的size，在调整完后再将size++
aliyun6365824167
20 0
大数据文摘
|
5天前
|
算法 安全 测试技术
golang 栈数据结构的实现和应用
本文详细介绍了“栈”这一数据结构的特点，并用Golang实现栈。栈是一种FILO（First In Last Out，即先进后出或后进先出）的数据结构。文章展示了如何用slice和链表来实现栈，并通过golang benchmark测试了二者的性能差异。此外，还提供了几个使用栈结构解决的实际算法问题示例，如有效的括号匹配等。
大数据文摘
15 1
golang 栈数据结构的实现和应用
游客rcxtdbgrolahs
|
5天前
01_设计一个有getMin功能的栈
01_设计一个有getMin功能的栈
游客rcxtdbgrolahs
9 3
游客rcxtdbgrolahs
|
5天前
|
前端开发
07_用队列实现栈
07_用队列实现栈
游客rcxtdbgrolahs
7 1
游客rcxtdbgrolahs
|
5天前
06_用栈来求解汉诺塔问题
06_用栈来求解汉诺塔问题
游客rcxtdbgrolahs
6 1
游客rcxtdbgrolahs
|
5天前
05_用一个栈实现另一个栈的排序
05_用一个栈实现另一个栈的排序
游客rcxtdbgrolahs
8 1
游客rcxtdbgrolahs
|
5天前
03_如何仅用递归函数和栈操作逆序一个栈
03_如何仅用递归函数和栈操作逆序一个栈
游客rcxtdbgrolahs
9 1
游客rcxtdbgrolahs
|
5天前
|
测试技术
02_由两个栈组成的队列
02_由两个栈组成的队列
游客rcxtdbgrolahs
8 1