邻接矩阵 邻接矩阵 （adjacency matrix）是表示图形中顶点之间相邻关系的矩阵。设G=(V,E)是具有n个顶点的图，顶点序号依次为0、1、2、…、n-1，则G的邻接矩阵是具有如下定义的n阶方阵。 例如，对于图7-1中的G1和G2，它们的邻接矩阵分别为下面的A1和A2所示。由A1可以看出，无向图的邻接矩阵是按主对角线对称的。 若图G是一个带权图，则用邻接矩阵表示也很方便，只要把对应元素值1换为相应边上的权值，把非对角线上的0换为某一个很大的特定实数即可，这个特定实数通常用∞或MaxValue表示，它要大于图G中所有边上的权值之和，表示此边不存在。 例如，对于图7-5中的带权图G5和G6，它们的邻接矩阵分别为下面的A3和A4所示。 采用邻接矩阵表示图，便于查找图中任一条边或边上的权。如要查找边(i,j)或<i,j>，则只要查找邻接矩阵中第i行与第j列上的元素A[i,j]是否为一个有效值（即非零值和非MaxValue值）即可；若该元素为一个有效值，则表明此边存在，否则此边不存在。因邻接矩阵中的元素可以随机存取，所以查找一条边的时间复杂度为O(1)。 这种存储表示也便于查找图中任一顶点的度，对于无向图，顶点vi的度就是对应第i行或第i列上有效元素的个数；对于有向图，顶点vi的出度就是对应第i行上有效元素的个数，顶点vi的入度就是对应第i列上有效元素的个数。由于求任一顶点的度需访问对应一行或一列中的所有元素，所以其时间复杂度为O(n)，n表示图中的顶点数，亦即邻接矩阵的阶数。 从图的邻接矩阵中查任一顶点的一个邻接点或所有邻接点同样也很方便。如要查找vi的一个邻接点（对于无向图）或出边邻接点（对于有向图），则只要在第i行上查找出一个有效元素，以该元素所在的列号j为序号的顶点vj就是所求的一个邻接点或出边邻接点。一般算法要求是依次查找出一个顶点vi的所有邻接点（对于有向图则为出边邻接点或入边邻接点），此时需访问对应第i行或第i列上的所有元素，所以其时间复杂度为O(n)。 图的邻接矩阵的存储需要占用n×n个整数存储位置（因顶点的序号为整数），所以其空间复杂度为O(n2)。这种存储结构用于表示稠密图能够充分利用存储空间，但若用于表示稀疏图，则将使邻接矩阵变为稀疏矩阵，从而造成存储空间的很大浪费。 图的邻接矩阵表示，除了需要用一个二维数组存储顶点之间相邻关系的邻接矩阵外，通常还需要使用一个具有n个元素的一维数组存储顶点信息，其中下标为i的元素存储顶点vi的信息。这两种数组的类型可定义为： /*定义图的最大顶点数，它要大于等于具体图的顶点数n*/ #define MaxVertexNum 8 /*定义图的最大边数，它要大于等于具体图的边数e*/ #define MaxEdgeNum 20 /*定义MaxValue为一个符号常量，其值要大于邻接矩阵中所有有效值之和*/ #define MaxValue 1000 /*定义图中顶点数据的类型VertexType为整型*/ typedef int VertexType; /*定义vexlist为存储顶点信息的数组类型*/ typedef VertexType vexlist[MaxVertexNum]; /*定义adjmatrix为存储邻接矩阵的数组类型*/ typedef int adjmatrix[MaxVertexNum][MaxVertexNum]; 对于图的邻接矩阵表示，很容易写出相应的生成算法，下面给出生成一个无向带权图的顶点数组和邻接矩阵的算法描述： 生成一个无向带权图顶点数组和邻接矩阵算法 void Create1(vexlist GV, adjmatrix GA, int n, int e) /*通过从键盘上输入 的n个顶点信息和e条无向带权边的信息建立顶点数组GV和邻接矩阵GA*/ { int i,j,k,w; /*建立顶点数组*/ printf('输入%d个顶点数据\n',n); for(i=0; i<n; i ) scanf(' %d',&GV[i]); /*初始化邻接矩阵数组*/ for(i=0; i<n; i ) for(j=0; j<n; j ) { if(i==j) GA[i][j]=0; else GA[i][j]=MaxValue; } /*建立邻接矩阵数组*/ printf('输入%d条无向带权边\n',e); for(k=1; k<=e; k ) { /*输入一条边的两端点序号i和j及边上的权w*/ scanf(' %d %d %d',&i,&j,&w); /*置数组中相应对称元素的值为w*/ GA[i][j]=GA[j][i]=w; } }
|
|
|
来自： 山峰云绕 > 《C语言数据结构描述Windows程序设计》
