第五章：图

图的基本概念

• 定义：
  树是N（N≥0）个结点的有限集合，N=0时，称为空树，这是一种特殊情况。在任意一棵非空树中应满足：
  1）有且仅有一个特定的称为根的结点。
  2）当N>1时，其余结点可分为m（m>0）个互不相交的有限集合T1，T2，…，Tm，其中每一个集合本身又是一棵树，并且称为根结点的子树。
  • 图G由顶点集V和边集E组成，记为G=(V，E)
    • V(G)表示图G中顶点的有限非空集。
      用|V|表示图G中顶点的个数，也称为图G的阶
    • E(G)表示图G中顶点之间的关系（边）集合。
      用|E|表示图G中边的条数。
• 分类
  • 有向图
    • 有向边（弧）的有限集合
      • 弧是顶点的有序对
      • <v,w>
      • v是弧尾，w是弧头
      • v邻接到w或w邻接自v
  • 无向图
    • 无向边的有限集合
      • 边是顶点的无序对
      • （v,w）
      • （v,w）=(w,v)
      • w，v互为邻接点
• 简单图
  • 1.不存在顶点到自身的边
  • 2.同一条边不重复出现
• 多重图
  • 若图G中某两个结点之间的边数多于一条，又允许顶点通过通过同一个边和自己关联
• 完全图
  • 无向完全图
    • 如果任意两个顶点之间都存在边
  • 有向完全图
    • 如果任意两个顶点之间都存在方向相反的两条弧
• 子图
• 连通图：图中任意两个顶点都是连通的
• 连通分量：无向图中的极大连通子图
  • 连通
    • 顶点A到顶点B有路径
  • 极大
    • 1.顶点足够多
    • 2.极大连通子图包含这些依附这些顶点的所有边
  • 结论1:如果一个图有n个顶点，并且有小于n-1条边，则此图必是非连通图。
  • 概要: 找连通分量的方法：
    从选取一个顶点开始，以这个顶点作为一个子图，然后逐个添加与这个子图相连的顶点和边直到所有相连的顶点都加入该子图
• 强连通：顶点V到顶点W和顶点W到顶点V都有路径
• 强连通图：图中任一对顶点都是强连通的
• 连通图的生成树：包含图中全部n个顶点，但是只有n-1条边的极小连通子图
  • 结论2:生成树去掉一条边则变成非连通图，加上一条边就会形成回路。
• 度：以该顶点为一个端点的边数目
  • 无向图中顶点V的度是指依附于该顶点的边的条数，记为TD(v)
  • 有向图中顶点V的度分为出度和入度
    • 入度（ID）是以顶点v为终点的有向边的数目
    • 出度（OD）是以顶点V为起点的有向边的数目
• 简单路径和简单回路：顶点不重复出现的路径称为简单路径。对于回路，除了第一个和最后一个顶点其余顶点不重复出现的回路称为简单回路
• 权和网：图中每条边考研赋予一定意义的数值，这个数值叫做这条边的权，有权值得图称为带权图，也叫做网
• 路径和路径长度：顶点p到q之间的路径是指顶点序列怕保存的，p,a,b,c,d,……q。路径上边的数目就是路径长度
• 回路（环）：第一个和最后一个顶点相同的路径称为回路或者环
• 距离：从顶点u到v的最短路径长度。不存在路径则为无穷

第一章：数据结构

基本概念

定义

• 在任何问题中，数据元素都不是孤立存在的，而是在它们之间存在着某种关系，这种数据元素相互之间的关系称为结构（Structure）。数据结构是相互之间存在一种或多种特定关系的数据元素的集合。数据结构包括三方面的内容：逻辑结构、存储结构和数据的运算。数据的逻辑结构和存储结构是密不可分的两个方面，一个算法的设计取决于所选定的逻辑结构，而算法的实现依赖于所采用的存储结构。

逻辑结构

• 逻辑结构是指数据元素之间的逻辑关系，即从逻辑关系上描述数据。它与数据的存储无关，是独立于计算机的
• 数据的逻辑结构分为线性结构和非线性结构
  • 集合 结构中的数据元素之间除了“同属于一个集合”的关系外，别无其他关系。 类似于数学上的集合
  • 线性结构 结构中的数据元素之间只存在一对一的关系。比如排队
  • 树形结构 结构中的数据元素之间存在一对多的关系。比如家族族谱
  • 图状结构或网状结构 结构中的数据元素之间存在多对多的关系。 比如地图