前言

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

一、邻接矩阵

图的邻接矩阵存储结构用于表示顶点之间的相邻关系，其中通过一个一维数组存储顶点，一个二维数组存储顶点之间的相邻关系，一个顶点数为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。

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

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

该无向图的邻接矩阵为：

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

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

其邻接矩阵表示如下：

下面是一个有向图：

其邻接矩阵表示如下：

（二）图的邻接矩阵性质

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

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

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

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

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

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

由于无向图的邻接矩阵存在对称关系，其上三角和下三角的相同的，所以当在存储邻接矩阵时，除了对角线都为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列的非零元素的个数之和。

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

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

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

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

即，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]=∞，这里的∞是一个大于所有边的权值。

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

其邻接矩阵表示如下：

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

其邻接矩阵表示如下：

邻接矩阵存储图代码

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

（一）图的邻接矩阵定义

可自行定义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");
  }
}

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

可知该图有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);      //输出邻接矩阵 
}

运行结果如下：

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

可知该图有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);      //输出邻接矩阵 
}

运行结果如下：

二、邻接表

（一）邻接表表示

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

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

#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;

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

为其编号如下：

其邻接表表示如下：

例如，下面这个有向图：

为其编号如下：

其邻接表表示如下：

（二）逆邻接表表示

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

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

（三）邻接表的性质

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

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

✨在一个有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

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

前言

一、邻接矩阵

（一）图的邻接矩阵表示

（二）图的邻接矩阵性质

（三）网的邻接矩阵表示

邻接矩阵存储图代码

（一）图的邻接矩阵定义

（二）初始化邻接矩阵

（三）图的邻接矩阵建立

（四）输出邻接矩阵

二、邻接表

（一）邻接表表示

（二）逆邻接表表示

（三）邻接表的性质

三、邻接多重表

四、十字链表

热门文章

最新文章

相关课程

相关电子书

热门

活动广场

任务中心

开发者评测

高校计划

乘风者计划

训练营

阿里云MVP

话题

直播

下载

镜像站

技术资料

插件

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

前言

一、邻接矩阵

（一）图的邻接矩阵表示

（二）图的邻接矩阵性质

（三）网的邻接矩阵表示

邻接矩阵存储图代码

（一）图的邻接矩阵定义

（二）初始化邻接矩阵

（三）图的邻接矩阵建立

（四）输出邻接矩阵

二、邻接表

（一）邻接表表示

（二）逆邻接表表示

（三）邻接表的性质

三、邻接多重表

四、十字链表

热门文章

最新文章

相关课程

相关电子书