图的存储结构

图的逻辑结构：多对多

图没有顺序存储结构，但可以借助二维数组来表示元素之间的关系，即数组表示法（邻接矩阵）

链式存储结构：多重链表（邻接表、邻接多重表、十字链表）

一、数组（邻接矩阵）表示法

• 建立一个顶点表（记录各个顶点信息）和邻接矩阵（表示各个顶点之间的关系）。

  • 设图 A = (V, E) 有 n 个顶点，则

    

  • 图的邻接矩阵是一个二维数组 A.arcs [n] [n]，定义为：

    

• 无向图的邻接矩阵表示法

  

  分析1：无向图的邻接矩阵是对称的；

  分析2：顶点 i 的度 = 第 i 行（列）中的 1 的个数；

  特别：完全图的邻接矩阵中，对角元素为0，其余1。

• 有向图的邻接矩阵表示法

  

  注：在有向图的邻接矩阵中，

  ​ 第 i 行含义：以结点 v_i 为尾的弧（即出度边）；

  ​ 第 i 列含义：以结点 v_i 为头的弧（即入度边）。

  分析1：有向图的邻接矩阵可能是不对称的。

  分析2：顶点的出度 = 第 i 行元素之和

  ​ 顶点的入度 = 第 i 列元素之和

  ​ 顶点的度 = 第 i 行元素之和 + 第 i 列元素之和

• 网（即有权图）的邻接矩阵表示法

  定义为：

  

• 邻接矩阵的存储表示：用两个数组分别存储顶点表和邻接矩阵

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

  • 采用邻接矩阵表示法创建无向网

    据此也可以推出无向图、有向图、有向网

    算法思想：

    1. 输入总顶点数和总边数
    2. 依次输入点的信息存入顶点表中。
    3. 初始化邻接矩阵，使每个权值初始化为极大值。
    4. 构造邻接矩阵。

    Status CreateUDN(AMGraph &G){
        //采用邻接矩阵表示法，创建无向网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中的位置
            G.arcs[i][j] = w;		//边<v1, v2>的权值置为w
            G.arcs[i][j] = G.arcs[j][i];//置<v1, v2>的对称边<v2, v1>的权值为w
        }
        return OK;
    }
    
    //在图中查找顶点
    int LocateVex(AMGraph G, VertexType u){
        //在图G中查找顶点u，存在则返回顶点表中的下标，否则返回-1
        int i;
        for(i = 0; i < G.vexnum; ++i){
            if(u == G.vexs[i]) return i;
            return -1;
        }
    }
    

• 邻接矩阵的优缺点

  • 优点：

    1. 直观、简单、好理解

    2. 方便检查任意一对顶点间是否存在边

    3. 方便找任一顶点的所有 “邻接点” （有边直接相连的顶点）

    4. 方便即使任一顶点的 “度” （从该点发出的边数为 “出度” ，指向该点的边数为 “入度”）

       • 无向图：对应行（或列）非0元素的个数；

       • 有向图：对应行非0元素的个数是 “出度”；

         ​ 对应列非0元素的个数是 “入度”。

  • 缺点：

    1. 不便于增加和删除顶点
    2. 浪费空间，存稀疏图（点很多而边很少）有大量无效元素，但对稠密图（特别是完全图）还是很合算的
    3. 浪费时间，统计稀疏图中一共有多少边

二、邻接表表示法

• 邻接表表示法（链式）

  

  顶点：按编号顺序将顶点数据存储在一维数组中；

  关联同一顶点的边（以顶点为尾的弧）：用线性链表存储；

  

  

  adjvex：邻接点域，存放与v_i 邻接的顶点在表头数组中的位置。

  nextarc：链域，指向下一条边或弧。

• 无向图

  

  特点：

  1. 邻接表不唯一
  2. 若无向图中有 n 个顶点、e 条边，则其邻接表需 n 个头结点和 2e 个表结点。适宜存储稀疏图。
  3. 无向图中顶点 v_i 的度为第 i 个单链表中的结点数。

• 有向图

  

  特点：

  1. 顶点 v_i 的出度（入度）为第 i 个单链表中的结点个数。
  2. 顶点 v_i 的入度（出度） 为整个单链表中邻接点域值是 i - 1 的结点个数。

• 图的邻接表存储表示：

  无向图演示：

  

  弧（边）的结点结构：

  

  #define MVNum 100			//最大顶点数
  typedef struct ArcNode{		//边结点
      int adjvex;				//该边所指向的顶点的位置
      struct ArcNode *nextarc; //指向下一条边的指针
      OtherInfo info;			//和边相关的信息
  }ArcNode;
  

  顶点的结点结构：

  

  typedef struct VNode{
      VerTexType data; 	//顶点信息
    ArcNode *firstarc;	//指向第一条依附该顶点的边的指针
  }VNode,AdjList[MVNum];	//AdjList表示邻接表类型
  //说明：例如：AdjList v; 相当于 VNode v[MVNum]; 
  

  图的结构定义：

  typedef struct{
      AdjList vertices;//vertices —— vertex 的复数
      int vexnum,arcnum;//图的当前顶点数和弧数
  }ALGraph;
  

  采用邻接表表示法创建无向：

  算法思想：

  1. 输入 总顶点数 和 总边数

  2. 建立 顶点表

     依次输入顶点的信息 存入顶点表 中

     使每个表头结点的 指针域初始化为NULL

  3. 创建邻接表

     依次输入每条边依附的两个顶点

     确定两个顶点的序号 i 和 j，建立边结点

     将此边结点分别插入到 v_i 和 v_j 对应的两个边链表的头部

  Status CreateUDG(ALGraph &G){//采用邻接表表示法，创建无向图G
      cin>>G.vexnum>>G.arcnum;	//输入总顶点数，总边数
  	for(i = 0; i < G.vexnum; ++i){//输入各点，构造表头结点表		
          cin>>G.vertices[i].data;//输入顶点值
          G.vertices[i].firstarc = NULL;//初始化表头结点的指针域
      }//for
      for(k = 0; k < G.arcnum; ++k){//输入各边，构造邻接表
          cin>>v1>>v2;			//输入一条边依附的两个顶点
          i = LocateVex(G,v1);
          j = LocateVex(G,v2);
          p1 = new ArcNode;		//生成一个新的边结点 *p1
          p1->adjvex = j;			//邻接点序号为j
          p1->nextarc = G.vertices[i].firstarc;
          G.vertices[i].firstarc = p1;//将新结点 *p1 插入顶点vi的边表头部
          p2 = new ArcNode;			//生成另外一个对称的新的边结点 *p2
          p2->adjvex = i;				//邻接点序号为i
          p2->nextarc = G.vertices[j].firstarc;
          G.vertices[j].firstarc = p2;	//将新结点 *p2 插入顶点 vj的边表头部
      }//for
      return OK;
  }//CreateUDG
  

• 邻接表特点

  • 方便找任一顶点的所有 “邻接点”

  • 节约稀疏图的空间

    • 需要N个头指针 + 2E个结点（每个结点至少两个域）

  • 方便计算任一顶点的 “度” ？

    • 对无向图：是的
    • 对有向图：只能计算 “出度” ；需要构造 “逆邻接表”（纯指向自己的边）来方便计算“入度”

  • 不方便检查任一对顶点间是否存在边

三、 邻接矩阵和邻接表的关系

​

1. 联系：邻接表中每一个链表对应于邻接矩阵中的一行，邻接表中结点个数等于一行中非零元素的个数。
2. 区别：
   1. 对于任一确定的无向图，邻接矩阵是唯一的（行列顶点编号一致），但邻接表不唯一（链接次序与顶点编号无关）。
   2. 邻接矩阵的空间复杂度为 O(n²)，而邻接表的空间复杂度为 O(n+e)。
3. 用途： 邻接矩阵多用于稠密图；而邻接表多用于稀疏图。

四、 十字链表和邻接多重表

Ⅰ 十字链表(Orthogonal List)

十字链表是有向图的另一种链式存储结构。我们也可以把它看成是将有向图的邻接表和逆邻接表结合起来形成的一种链表。

有向图中的每一个弧对应十字链表中的一个弧结点，同时有向图中的每个顶点在十字链表中对应有一个结点，叫做顶点结点。

十字链表的结构图：

Ⅱ 邻接多重表

无向图的另一种链式存储结构。

回顾：

邻接表优点：容易求得顶点和边的信息。

​ 缺点：某些操作不方便（如：删除一条边需找表示此边的两个结点），任何一 条边都会出现两次。

邻接多重表的结构图：