邻接矩阵的存储方式，也称数组存储方式。 核心思想：利用两个数组来存储一个图

两个数组

第一个数组：VERTEX[n]

将图中的n个顶点的数据信息分别存入VERTEX[0,…,n-1] 这里的数据信息可以有很多种类。 若该数据信息仅表示人为给定的序号，则该一维数组可以省略

第二个数组：A[n][n]

将邻接矩阵存入该数组 A[i][j]={1 顶点i与之间有边 0 顶点i与之间无边 若为网络，则 A[i][j]={ wij(表示边的权值) 顶点i与j有边 { 0 顶点i与j无边

特点

1.无向图是对称矩阵 2.不带权的有向图一般是稀疏矩阵，可以采用三元组表或十字链表（下节内容） 3.无向图每行，表示该顶点的度TD 4.有向图每行，表示该顶点的出度OD或入度ID 5.虽然便于表示点间关系，但是不便于知道具体有几条边，遍历时间代价大 6.对于稀疏图，造成存储空间浪费

算法

输入：带权无向图的n个顶点（假设以序号表示），和e个表示边的顶点偶对

#define MaxValue Int_Max //定义最大值（∞） #define MaxNum 100 void ADJMATRIX(int A[][Maxnum], int n, int e) { int i, j, k, weight; for(i = 0; i< n;i ++) for(j = 0;j < n; j ++) A[i][j]= MaxValue; //赋值 for(k = 0;k < e;k ++) { scanf("i = %d ,j = %d, weight = %d ",&i, &j ,&weight); //输入 A[i][j]=weight; A[j][i]=weight; } }

该算法复杂度为O（n^2+e）