第六章图

第六章图的思维导图，图(graph)G由两个集合V(vertex)和E(edge)组成，记为G=(V,E)，其中V是顶点的有限集合，记为V(G),E是连接V中两个不同顶点(顶点对)的边的有限集合，记为E(G)

第六章图

• 概述
  • 图形结构术语复杂的非线性数据结构，在实际应用中很多问题可以用图来描述。在图形结构中，每个元素可以有零个或多个前驱元素，也可以有零个或多个后继元素，也就是说元素之间的关系是多对多的。
• 基本概念
  • 图的定义
    • 图(graph)G由两个集合V(vertex)和E(edge)组成，记为G=(V,E)，其中V是顶点的有限集合，记为V(G),E是连接V中两个不同顶点(顶点对)的边的有限集合，记为E(G)
    • 有向图
      • 在图G中，如果表示边的顶点对是有序的，则称G为有向图。在有向图中代表边的顶点用尖括号括起来,<j,i>和<ij>是两条不同的边。
    • 无向图
      • 在无向图中(j，i)(i，j)代表的是同一条边无向图
  • 图的基本术语
    • 端点和邻接点
      • 在一个无向图中，若存在一条边(ij)，则称顶点i和顶点j为该边的两个端点，并称它们互为邻接点。
      • 在一个有向图中，存在有向边<ij>，i为此边的起始端点，j为此边的终止端点，顶点j是顶点i的出边邻接点，顶点i是顶点j的入边邻接点。
    • 顶点的度、入度和出度
      • 在无向图中，一个顶点所关联的边的数目称为该顶点的度
      • 在有向图中，顶点的度又分为入度和出度，以顶点j为终点的边数目，称为该顶点的入度，以顶点i为起点的边数目，称为该顶点的出度。一个顶点的入度与出度的和为该顶点的度。
    • 完全图
      • 若无向图中的每两个顶点之间都存在着—条边，有向图中的每两个顶点之间都存在着方向相反的两条边，则称此图为完全图。无向完全图存在n(n-1)/2条边，有向完全图存在n(n-1)条边
    • 稠密图和稀疏图
      • 当一个图接近完全图时，称为稠密图。相反，当一个图含有较少的边数时，则称为稀疏图
    • 子图
      • 设有两个图G=(V,E)和G'=(V',E')，若V是V的子集，且E'是E的子集，则称G'是G的子图
    • 路径和路径长度
      • 在一个图G=(V,E)中，从顶点i到顶点j的一条路径是―个顶点序列(i,i1,i2……im.ij).路径长度是指—条路径上经过的边的数目
      • 若—条路径上除开始点和结束点可以相同以外，其余顶底啊均不相同，则称此路径为
      • 简单路径。
    • 回路或环
      • 若—条路径上的开始点和结束点为同一个顶点，则此路径被称为回路或环。开始点和结束点相同的简单路径被称为简单回路或简单环。
    • 连通、连通图和连通分量
      • 在无向图G中，若顶点i到顶点j有路径，则称顶点i和顶点j是连通的。若图G中任意两个顶点都是连通的，则称G为连通图，否则称为非连通图
    • 强连通图和连通分量
      • 在有向图中，若图G中任意两个顶点i和j都连通，即从顶点i到顶点j和从顶点j到顶点i都存在路径，则称图G是强连通图。在有向图G中的极大强连通子图称为G的强连通分量。强连通图只有一个强连通分量(即本身)
    • 权和网
      • 图中的每一条边都可以附有一个对应的数值，这种与边相关的数值称为权。权可以表示从一个顶点到另一个顶点的距离或花费的代价。边上带有权的图称为带权图，也称作网
• 存储结构和基本运算算法
  • 邻接矩阵存储方法
    • 图的邻接矩阵是―种采用邻接矩阵数组表示顶点之间关系的存储结构
  • 邻接表存储方法
    • 图的邻接表是—种顺序与链式存储相结合的存储方法
  • 图基本运算算法
    • 创建图
    • 输出图
    • 销毁图
• 图的遍历
  • 从给定图中任意指定的顶点出发，按照某种搜索方法沿着图的边访问图中的所有顶点，使每个顶点仅被访问—次，这个过程称为图的遍历
  • 图的遍历有两种:深度优先遍历、广度优先遍历
• 生成树和最小生成树
  • 一个连通图的生成树是一个极小连通子图，其中含有图中的全部顶点，和构成一棵树的(n-1)条边。
  • 图的所有生成树中具有边上的权值之和最小的树称为图的最小生成树。
  • 普里姆算法
    • 普里姆算法就是通过一个顶点扩散开找权值最小的边，所经过的顶点和边就是这个图的最小生成树
  • 克鲁斯卡尔算法
    • Kruskal算法是一种按权值的递增次序选择合适的边来构造最小生成树的方法。
• 最短路径
  • 由于从一顶点到另一顶点可能存在着多条路径，每条路径上所经过的边数可能不同，即路径长度不同，把路径长度最短的那条路径称为最短路径，其长度称为最短路径长度或最短距离
  • Dijkstra算法:从一个顶点到其余各顶点的最短距离
• 拓扑排序
  • 定义
    • 设G=(V,E)是一个具有n个顶点的有向图，V中的顶点序列v1，v2，…，vn称为一个拓扑排序
    • 在一个有向图中找一个拓扑序列的过程称为拓扑排序
  • 方法
    • 从有向图中选择—个没有前驱的顶点并且输出它
    • 从图中删去该顶点，并且删去从该顶点发出的全部有向边
    • 重复上述两步，直到剩余的图中不再存在没有前驱的顶点为止