用邻接矩阵表示法表示的无向图和网图如下图所示 ( vO v3 A 1011 v1 100 一个无向图的邻接矩阵表示 0o963o 963 8 78 网图的邻接矩阵表示 2021年1月21日 数据结构讲义
2021年1月21日 数据结构讲义 16 • 用邻接矩阵表示法表示的无向图和网图如下图所示
从图的邻接矩阵存储方法容易看出这种表示具有以下特 ①无向图的邻接矩阵一定是一个对称矩阵。因此,在具 体存放邻接矩阵时只需存放上(或下)三角矩阵的元素即 可 ②对于无向图,邻接矩阵的第i行(或第i列)非零元素 (或非∞元素)的个数正好是第个顶点的度TD(1)元务 ③对于有向图,邻接矩阵的第i行(或第i列)非零」 (或非∞元素)的个数正好是第i个顶点的出度OD(vi)(或 入度ID(vi))。 ④用邻接矩阵方法存储图,很容易确定图中任意两个顶 点之间是否有边相连;但是,要确定图中有多少条边,则 必须按行、按列对每个元素进行检测,所花费的时间代价 很大。这是用邻接矩阵存储图的局限性。 2021年1月21日 数据结构讲义
2021年1月21日 数据结构讲义 17 • 从图的邻接矩阵存储方法容易看出这种表示具有以下特 点： ①无向图的邻接矩阵一定是一个对称矩阵。因此，在具 体存放邻接矩阵时只需存放上（或下）三角矩阵的元素即 可。 ②对于无向图，邻接矩阵的第i行（或第i列）非零元素 （或非∞元素）的个数正好是第i个顶点的度TD(vi)。 ③对于有向图，邻接矩阵的第i行（或第i列）非零元素 （或非∞元素）的个数正好是第i个顶点的出度OD(vi)（或 入度ID(vi)）。 ④用邻接矩阵方法存储图，很容易确定图中任意两个顶 点之间是否有边相连；但是，要确定图中有多少条边，则 必须按行、按列对每个元素进行检测，所花费的时间代价 很大。这是用邻接矩阵存储图的局限性
在用邻接矩阵存储图时,除了用一个二维数组存储用于 表示顶点间相邻关系的邻接矩阵外,还需用一个一维数组 来存储顶点信息,另外还有图的顶点数和边数。故可将其 式描述如下: # define max VertexNum100/最大顶点数设为100 typedef char Vertexlype *顶点类型设为字符型* typedef int Edge Type 、, /*边的权值设为整型* typedef struct Vertexlype vex[ Max Vertexnum],/顶点表* EdeType edges[Max VertexNum [Max VertexNum *邻接矩阵,即边表* Int n,e: /*顶点数和边数* gRagh / Maragh是以邻接矩阵存储的图类型* 2021年1月21日 数据结构讲义
2021年1月21日 数据结构讲义 18 • 在用邻接矩阵存储图时，除了用一个二维数组存储用于 表示顶点间相邻关系的邻接矩阵外，还需用一个一维数组 来存储顶点信息，另外还有图的顶点数和边数。故可将其 形式描述如下： #define MaxVertexNum 100 /*最大顶点数设为100*/ typedef char VertexType; /*顶点类型设为字符型*/ typedef int EdgeType; /*边的权值设为整型*/ typedef struct { VertexType vexs[MaxVertexNum]; /*顶点表*/ EdeType edges[MaxVertexNum][MaxVertexNum]; /*邻接矩阵，即边表*/ int n,e; /*顶点数和边数*/ }Mgragh; /*Maragh是以邻接矩阵存储的图类型*/
建立一个图的邻接矩阵存储的算法如下: void CreateMGraph( MGraph*G)/*建立有向图G的邻接矩阵存储* f int i,j, k,w; char ch; printf(“请输入顶点数和边数(输入格式为顶点数边数m") scanf("od,9%d"&(G->n),&(G->e);/*输入顶点数和边数*/ printf"请输入顶点信息输入格式为顶点号<CR>)n") for(i=0;i<G->n;i++)/输入顶点信息,建立顶点表 scanf("n%c", &(G->vexsiD) for(i=0;i<G->n;i++)/*初始化邻接矩阵* for (=0 <G->n; j++) G->edges[10=0 printf请输入每条边对应的两个顶点的序号输入格式为ij)n") for(k=0 K<G->e; k++) I scanf("n%d, %d", &i, &j) *输入e条边,建立邻接矩阵* G->edges 1ll=l /若加入G> edges.=1,则为无向图的邻接矩阵存储建立 2021年1月21日 数据结构讲义
2021年1月21日 数据结构讲义 19 • 建立一个图的邻接矩阵存储的算法如下： void CreateMGraph(MGraph *G) /*建立有向图G的邻接矩阵存储*/ { int i,j,k,w; char ch; printf("请输入顶点数和边数(输入格式为:顶点数,边数):\n"); scanf("%d,%d",&(G->n),&(G->e)); /*输入顶点数和边数*/ printf("请输入顶点信息(输入格式为:顶点号<CR>):\n"); for (i=0;i<G->n;i++) /*输入顶点信息，建立顶点表*/ scanf("\n%c",&(G->vexs[i])); for (i=0;i<G->n;i++) /*初始化邻接矩阵*/ for (j=0;j<G->n;j++) G->edges[i][j]=0; printf("请输入每条边对应的两个顶点的序号(输入格式为:i,j):\n"); for (k=0;k<G->e;k++) { scanf("\n%d,%d",&i,&j); /*输入e条边，建立邻接矩阵*/ G->edges[i][j]=1; /*若加入G->edges[j][i]=1;，则为无向图的邻接矩阵存储建立*/} }
8.2.2邻接表 ◆邻接表( Adjacency List)是图的一种顺序存储与链 式存储结合的存储方法。邻接表表示法类似于树的孩 子链表表示法。就是对于图G中的每个顶点ⅵ,将所有 邻接于ⅵ的顶点ⅵ链成一个单链表,这个单链表就称 为顶点v的邻接表,再将所有点的邻接表表头放到数 组中,就构成了图的邻接表。 2021年1月21日 数据结构讲义
2021年1月21日 数据结构讲义 20 8.2.2 邻接表 邻接表(Adjacency List)是图的一种顺序存储与链 式存储结合的存储方法。邻接表表示法类似于树的孩 子链表表示法。就是对于图G中的每个顶点vi，将所有 邻接于vi的顶点vj链成一个单链表，这个单链表就称 为顶点vi的邻接表，再将所有点的邻接表表头放到数 组中，就构成了图的邻接表