6.1 图的逻辑结构

6.1.1 图的定义和基本术语

1、图的定义

• 图：是由定点的有穷非空集合和顶点之间边的集合组成，通常表示为G=(V, E)

  • G：表示一个图
  • V：图G中顶点的集合
  • E：图G中边的集合

• 无向图与有向图：如果图的任意两个顶点之间的边都是无向边，则称该图为无向图，否则称该图为有向图

  • 若顶点vi和vj之间的边没有方向，则称这条边为无向边，用无序偶对(vi, vj)来表示

  • 若从顶点vi到vj的边有方向，则称这条边为有向边（也称为弧），用有序偶对<vi, vj>来表示

    • vi称为弧尾
    • vj称为弧头

2、图的基本术语

• 简单图：在图中若不存在顶点到其自身的边（ 不自环 ），且同一条边不重复出现（ 无多重边 ），则称这样的图为简单图

  • 数据结构中只讨论简单图

• 邻接、依附：

  图的类型	邻接	依附
  在 无向图 中	对于任意两个顶点vi和vj，若存在边 (vi, vj)，则称顶点vi和vj互为邻接点	同时称边 (vi, vj) 依附于顶点vi和vj
  在 有向图 中	对于任意两个顶点vi和vj，若存在弧<vi, vj>，则称顶点 vi邻接到vj ，顶点 vj邻接自vi （通常称vj是vi的邻接点）	同时称弧<vi, vj> 依附于顶点vi和vj

• 无向完全图、有向完全图：

  图的类型	定义	边数
  在无向图中	如果 任意 两个顶点之间都存在边，则称该图为无向完全图	含有n个顶点的无向完全图有 n x (n - 1) / 2 条边
  在有向图中	如果 任意 两顶点之间都存在方向互为相反的两条弧，则称该图为有向完全图	含有n个顶点的有向完全图有 n x (n - 1) 条边

  • 在完全图中，边（或弧）的数目达到最多

• 稠密图、稀疏图：称边树很少的图为稀疏图，反之称为稠密图（相对模糊的概念）

• 顶点的度、入度、出度：

  图的类型	顶点的度	入度	出度	度数
  在无向图中	顶点v的度是指依附于该顶点的边的个数，记为TD(v)	/	/	在具有n个顶点e条边的无向图中：∑TD(vi) = 2e（度数的和是边数的两倍）
  在有向图中	/	顶点v的入度是指以该顶点为 弧头 的弧的个数，记为ID(v)	顶点v的出度是指以该顶点为 弧尾 的弧的个数，记为OD(v)	在具有n个顶点e条边的有向图中：∑ID(vi) = ∑OD(vj) = e（入度的和 = 出度的和 = 边数）

• 权、网：

  • 权：在图中，权通常是指对边赋予的有意义的数值量
  • 网/网图：边上带权的图称为网或网图

• 路径、路径长度、回路：

  • 路径：顶点vp到vq之间的路径是一个顶点序列

  • 路径长度：

    • 带权图：路径上各边的权之和
    • 非带权图：路径上边的个数

  • 回路/环：第一个顶点和最后一个顶点相同的路径称为回路/环

• 简单路径、简单回路：

  • 简单路径：在路径序列中，顶点不重复出现的路径称为简单路径
  • 简单回路：除了第一个顶点和最后一个顶点之外，其余顶点不重复出现的回路称为简单回路

• 子图：对于图G=(V, E)和图G' = (V', E')，如果 V'是V的真子集 && E'是E的真子集，则称图G’是图G的子图

• 连通量、连通分量：

  • 连通图：在 无向图 中，若 任意 顶点vi和vj（vi ≠ vj）之间有路径，则称该图是连通图

  • 联通分量：非连通图 的 极大连通子图 称为连通分量

    • “极大”的含义是包括 所有连通的顶点 以及和这些顶点相关联的 所有边

• 强连通图、强连通分量：

  • 强连通图：在 有向图 中，对 任意顶点 vi和vj（vi ≠ vj），若 从顶点vi到vj均有路径（不一定是直接相连） ，则称该有向图是强连通图

  • 强连通分量：非强连通图 的 极大强连通子图 称为强连通分量

    • 孤立的点也是强连通分量

• 生成树、生成森林：

  • 生成树（不唯一）：

    图的类型	定义	根结点	边数
    无向图	具有n个顶点的 连通图 G的的生成树是包含G中 全部顶点 的一个 “极小” 连通子图（极小表示最少的边，即能连起来就行 => 从而导致了不唯一）	连通图的生成树是一个*树，可以在生成树中 任意指定 一个顶点为树的根结点	1⃣ 在生成树中添加任意一条属于原图中的边必定会产生回路（因为新添加的边使其所依附的两个顶点之间有了第二条路径）2⃣ 在生成树中减少任意一条边，则必然成为非连通 3⃣ 一棵具有n个顶点的生成树 有且仅有（n-1）条边
    有向图	具有n个顶点的 有向图（不一定是强连通图） G的生成树是包含G中 全部顶点 的一个子图，且子图中 只有一个入度为0的顶点，其他顶点的入读均为1	入度为0的顶点	一棵具有n个顶点的生成树 有且仅有（n-1）条边

  • 生成森林（不唯一）： 在非连通图中 ，由于每个连通分量都可以得到一棵生成树，这些连通分量的生成树构成了非连通图的生成森林

6.1.3 图的遍历操作

• 定义：图的遍历是指从图中某一顶点出发，对图中所有顶点访问一次且仅访问一次

• 四个关键问题：

  序号	问题	解决方法
  1	在图中，如何选取遍历的起始顶点？	编号，从最小的顶点开始
  2	从某个顶点可能到达不了其他顶点（如非连通图，从一个顶点出发，只能访问它所在的连通分量上的所有顶点），那么，如何才能遍历图中的所有顶点？	多次重复从不同顶点出发
  3	在图中可能存在回路，某些顶点可能会被重复访问，如何避免不会因回路而陷入死循环？	附设访问标志数组
  4	在图中，一个顶点可以和其他多个顶点相邻接，当这样的顶点访问过后，如何选取下一个要访问的顶点？	深度优先遍历和广度优先遍历

  • 问题2：多次重复从某一顶点出发进行遍历

    for (i = 0; i < n; i++)
        如果顶点i没被访问过，则从顶点i出发进行图的遍历
    

  • 问题3：设置访问标志visited[n]的值置0或1判断是否被访问

    将图中所有顶点置未访问标志
    for (i = 0; i < n; i++)
        if (visited[i] == 0) 从顶点i出发进行图的遍历
    

1、深度优先遍历

• 实现结构：栈

• 类比：树的前序遍历

• 基本思想：

  • （1）访问顶点v
  • （2）从v的未被访问的邻接点中选取一个顶点w，从w出发进行深度优先遍历
  • （3）重复上述两步，直至图中所有和v有路径相通的顶点都被访问到

• 伪代码：

  访问顶点v;                                      //第一层
  visited[v] = 1;
  
  w = 顶点v的第一个邻接点;                          //第二层
  
  while (w存在) 
      if (w未被访问)  从顶点w出发递归执行该算法; 
      w = 顶点v的下一个邻接点;                      //第三层
  

• 入栈过程：

  • 无向图：
  • 有向图：

2、广度优先遍历

• 实现结构：队列

• 类比：树的层序遍历

• 基本思想：

  • （1）访问顶点v；
  • （2）依次访问v的各个未被访问的邻接点v1,v2,…,vk；
  • （3）分别从v1,v2,…,vk出发依次访问它们未被访问的邻接点。直至图中所有与（最开始的）顶点v有路径相通的顶点都被访问到
    • 要使 “先被访问顶点的邻接点” 先于 “后被访问顶点的邻接点” 被访问

• 伪代码：两个while循环

  初始化队列Q；
  
  
  访问顶点v；
  visit[v] = 1；
  顶点v进入队列Q；
  
  
  while （队列Q非空）                         //第一个while用于出队
  
      v = 队列Q的队头元素出队；
      w = 顶点v的第一个邻接点；
      
      while （w存在）                        //第二个while用于入队
      
          如果w未被访问，则访问顶点w；
          visited[w] = 1;
          顶点w进入队列；
          
          w = 顶点v的下一个邻接点；
  

• 示意图：（无向图）

6.2 图的存储结构及实现

• 两部分关键信息：
  • （1）顶点的信息
  • （2）描述顶点之间关系（边或弧）的信息

6.2.1 邻接矩阵

• 实现结构：数组

  • （1）一个一维数组：存储图中顶点的信息
  • （2）一个二维数组：存储图中边的信息，即各顶点之间的邻接关系（此二维数组即邻接矩阵）

• 定义：

  • 无向图的邻接矩阵一定是对称矩阵
  • 有向图的邻接矩阵则不一定对称

• 带权的特例：网图

• 优点：

  • （1）顶点的度可快速得出

    图的类别	度	出度	入度
    无向图	顶点i的度 = 邻接矩阵第i行（或第i列）非零元素的个数	/	/
    有向图	/	顶点i的出度 = 邻接矩阵第i行非零元素的个数	顶点i的入度 = 邻接矩阵第i列的非零元素的个数

  • （2）易判断两顶点间的边或邻接关系

    问题	方法
    判断顶点i和j之间是否存在边	邻接矩阵中相应位置元素arc[i][j]的值为1则存在边，否则不存在边
    寻找i的所有邻接点	可依次判断顶点i与其他顶点之间是否有边（无向图）或是否有弧（有向图）

• 成员定义：

  private:
      DataType vertex[MaxSize];               //存放图中顶点的数组
      int arc[MaxSize][MaxSize];              //存放图中边的数组（即邻接矩阵）
      int vertexNum, arcNum;                  //图的顶点数和边数
  

1、构造函数

• 目标：建立一个含有n个顶点e条边的图

• 伪代码：

  1、确定图的顶点个数和边的个数；
  
  2、输入顶点信息，存储在一维数组vertex中；
  
  3、初始化邻接矩阵；
  
  4、依次输入每条边，存储在邻接矩阵arc中：
      输入边依附的两个顶点的编号i，j；
      将邻接矩阵的第i行第j列的元素值置为1；
      将邻接矩阵的第j行第i列的元素置为1；
  

• 代码描述：

  MGraph<DataType>::MGraph(DataType a[], int n, int e)
  {
  
      vertexNum = n; arcnum = e;
      
      //一维数组存储顶点信息
      for (i = 0; i < vertexNum; i++) {
          vertex[i] = a[i];                   
      }
      
      //初始化邻接矩阵
      for (i = 0; i < vertexNum; i++) {
          for (j = 0; j < vertexNum; j++) {
              arc[i][j] = 0;
          }
      }
      
      //依次输入每一条边
      for (k = 0; k < arcNum; k++) {
          cin >> i >> j;                          //输入边依附的两个顶点的编号
          arc[i][j] = 1; arc[j][i] = 1;           //置有边标志
      }
  }