邻接矩阵的储存表示

使用两个数组分别储存顶点表和邻接矩阵

  1. #define MaxInt 32767    //表示极大值，及∞
  2. #define MVNum 100    //最大顶点数
  3. typedef char VerTexType;    //顶点数据类型为字符型
  4. typedef int ArcType;    //假设边的权值类型为整型
  6. typedef struct{
  7.     VerTexType vexs[MVNum];    //顶点表
  8.     ArcType arcs[MVNum][MVNum];    //邻接矩阵
  9.     int vexnum,arcnum;    //图的当前点数和边数
  10. }AMGraph;    //Adjacency Matrix Graph

无向图：

  1. 初始化邻接矩阵时，w均为0；
  2. 构造邻接矩阵时，w为1；

有向网：
邻接矩阵是非对称矩阵，仅为G.arcs[i][j]赋值而无需为G.arc[j][i]赋值

优点

  • 直观、简单、好理解
  • 方便检查任意一对顶点间是否存在边
  • 方便找任一顶点的所有“邻接点”（有边直接相连的顶点）

  • 方便计算度数

    缺点

  • 浪费空间——村稀疏图（点多边少），存在大量无效元素，空间复杂度O(n²)

  • 不便于增加删除顶点
  • 浪费时间——统计稀疏图中有多少边O(n²)

算法6.1 邻接矩阵表示法创建无向网（有权值）

【算法思想】

  1. 输入总顶点数和总边数
  2. 依次输入点的信息存于顶点表中
  3. 初始化邻接矩阵，使每个权值初始化为极大值
  4. 构造邻接矩阵
    Status CreateUDN(AMGraph &G){
 cin>>G.vexnum>>G.arcnum;    //输入总顶点数，总边数
 for(i = 0;i<G.vexnum;i++){
     cin>>G.vexs[i]}    //依次输入点的信息
 for(i = 0;i<G.vexnum;i++){    //初始化邻接矩阵
     for(j = 0;j<G.vexnum;j++){
         G.arcs[i][j] = MaxInt;}    //边的权值均置为极大值
 }
 for(k = 0;k<G.arcnum;k++){    //构造邻接矩阵
     cin>>v1>>v2>>w;    //输入一条边所依附的顶点及边的权值
     i = LocateVex(G,v1);
     j = LocateVex(G,v2);    //确定v1和v2在顶点表中的位置（下标）
     G.arcs[i][j] = w;    //边<v1,v2>的权值设置为w
     G.arcs[j][i] = G.arcs[i][j];    //置<v1,v2>的对称边<v2,v1>的权值为w
 }    //for
 return ok
}    //CreateUDN

补充算法：LocateVex(G,u) 在图中查找顶点

int LocateVex(AMGraph G,VertexType u){
//图G中查找顶点u，存在则返回顶点表中的下标
    int i;
    for(i = 0;i<G.vexnum;i++){
        if(u==G.vex[i]) return i;
    }
    return -1;
}