逻辑结构分为两部分:V和E集合。因此，用一个一维数组存放图来自中所有顶点数据;用都持传较风体即一个二维数组存放顶点间360百科关系(边或弧)的数据，这个二维数组称为邻接矩阵。邻接矩质开怎业补学神阵又分为有向图邻接矩阵和无向图邻接矩阵
- 中文名 邻接矩阵
- 外文名 Adjacency Matrix
- 简介 表示顶点之间相邻关系的矩阵
- 分为 有向图邻接矩阵和无向图邻接矩阵
- 所属科目 数据结构
定义
邻接矩阵(Adjacen来自cy Matrix):是表示顶点之间相邻关系的矩阵。设G=(V,E)是一个图，其中V={v1,v2,…,vn}。G的邻接矩阵是一个具有下列性质的n阶方阵:
①对无向图而言，邻接矩阵一定是对称的，而且主对角线一定为零(在此仅讨论无向简单图)，副对角线不一定为0，有向图则不一定如此。
②在无向图中，任一顶点i的度为第i列(或第i行)所有非零元素的个数，在有向图中顶点i的出度为第i害酒重级销一行所有非零元素的个数，360百科而入度为第i列所突有非零元素的个数。
③用邻接矩阵法表示图共需要n^2个空间，由于无向图的邻接矩阵一定具有对称关系，所以扣除对角线为零外，仅需要存储上三角形或下三角形的数据即可，因此仅需要n(n-1)/2个空间。
特点
无向图的邻接矩阵一定是另力航亲对称的，而有向图的邻接矩阵不一定对称。因此，用邻接矩阵来表示一个具有n个顶点的有向图时需要n^2个单元来存储邻接矩阵;对有n个顶点的无向图则只存入上(下)三角阵中剔除了左上右下对角线上的0元素后剩余的元素，故只需1+2+...+(n-1)=n(n-1乙技值居很巴省图相县)/2个单元。
无向图邻接矩阵的第i行(或第i列)非零元素的个数正好是第i个顶点的度。
有向图邻接矩阵中第i行非零元素的个数为第i个顶点的出度，第i列非零元素的个数为第i个顶点的入度，第i个顶点的度为第i行与第i列非零元素个数之和。
用邻接矩阵表孔苗先示图，很容易确定图中任意两个顶点是否有边相连。
描述
用一个顺序表来存储顶点信息
表示法
在图的邻接矩阵表示法中:
① 用邻接矩阵表示顶点间的相邻关系
② 用一个顺序表来存储顶点信息
图的矩阵
设G=(V，E)是具有n个顶点的图，则G的邻接矩阵是具有如下性质的n阶方阵:
【例】
下图中无向图G 5 和有向图G 6 的邻接矩阵分别为A1 和A 2 。
网络矩阵
若G是网络，则邻接矩阵可定义为:
其中:
w ij 表示边上的权值;
∞表示一个计算机允许的、大于所有边上权值的数。
【例】下面带权图的两种邻接矩阵分别为A 3 和A 4 。
图的邻接矩阵存储结构形式说明
#define MaxVertexNum l00 //最大顶点数，应由用户定义
typedef char VertexType; //顶点类型应由用户定义
typedef int EdgeType; //边上的权值类型应由用户定义
typedef struct{
VextexType vexs[MaxVertexNum] //顶点表
EdgeType edges[MaxVertexNum][MaxVertexNum];//邻接矩阵，可看作边表
int n，e; //图中当前的顶点数和边数
}MGragh;
注意:
① 在简单应用中，可直接用二维数组作为图的邻接矩阵(顶点表及顶点数等均可省略)。
② 当邻接矩阵中的元素仅表示相应的边是否存在时，EdgeTyPe可定义为值为0和1的枚举类型。
③无向图的邻接矩阵是对称矩阵，对规模特大的邻接矩阵可压缩存储。
④邻接矩阵表示法的空间复杂度S(n)=0(n 2 )。
⑤建立无向网络的算法。
void CreateMGraph(MGraph *G)
{//建立无向网的邻接矩阵表示
int i，j，k，w;
scanf("%d%d"，&G->n，&G->e); //输入顶点数和边数
for(i = 0;i < n;i++) //读入顶点信息，建立顶点表
{
G->vexs=getchar();
}
for(i = 0;i < G->n;i++)
{
for(j = 0;j <G->n;j++)
{
G->edges[j] = 0; //邻接矩阵初始化
}
}
for(k = 0;k < G->e;k++)
{//读入e条边，建立邻接矩阵
scanf("%d%d%d"，&i，&j，&w); //输入边(v i ,v j )上的权w
G->edges[j]=w;
G->edges[j]=w;
}
}//CreateMGraph
该算法的执行时间是0(n+n 2 +e)。由于e
根据图的定义可知，图的逻辑结构分为两部分:V和E的集合。因此，用一个一维数组存放图中所有顶点数据;用一个二维数组存放顶点间关系(边或弧)的数据，称这个二维数组为邻接矩阵。邻接矩阵又分为有向图邻接矩阵和无向图邻接矩阵。
Matlab表达N=4;//图中的节点数目
dag=zeros(N,N);//邻接矩阵初始化，值均为0
C=1;S=2;R=3;
W=4;//制定各节点编号
dag(C,[RS])=1;//有两条有向边:C->R,C->S
dag(R,W)=1;//有向边:R->W
dag(S,W)=1;//有向边:S->W
评论留言