🔑【数据结构】之查找

图

图的基本概念

• 图由结点的有穷集合V和边的集合E组成，将结点称为顶点
• 图分为有向图、无向图
• 弧指有向图的边，记为<v1，v2>，弧头指向弧尾
• 无向图的度指边的个数，有向图分为入度和出度，入度指弧头的个数，出度指弧尾的个数
• 有向图最多有$n(n-1)$条边，无向图最多有$n(n-1)/2$条边，满边即是完全
• 顶点不重复出现的路径称为简单路径
• 有向图的正反相连为强连通图

图的存储结构

主要分为邻接矩阵和邻接表

• 邻接矩阵
  • 无权： 1 0
  • 有权： ∞ 权值
• 邻接表
• 邻接多重表
• （十字链表）

图的遍历（算法回看）

• 深度优先遍历
  • 类似二叉树的先序遍历
• 广度优先遍历
  • 类似树的层次遍历

时间复杂度

• 邻接矩阵：$O(n^2)$
• 邻接表：$O(n+e)$

最小（代价）生成树

• 指所有生成树的集合权值之和最小的那颗生成树

普里姆算法和克鲁斯卡尔算法

• 普里姆算法：记V是连通网的顶点集，U是求得生成树的顶点集，TE是求得生成树的边集
• 克鲁斯卡尔算法：不构成环的情况下，每次选取最小边

最短路径

• 带权路径长度最短的那条路径称作最短路径

• Dijkstra算法：每次选取路径，小的替换大的，选出最短的后该行不在参与

  终点	从A到各定点的最短路径
  B
  C
  D
  最短路径

• Floyed算法：矩阵对角线不变，当第k行，第k列有∞时该行、该列不变

拓扑排序

• 有向无环图：一个有向图中不存在环，则称为有向无环图，简称DAG图
• DAG表示一个工程，其定点表示活动。用有向边<Vi，Vj>表示Vi先于Vj进行的一种关系，
• 拓扑排序：在图论中，由一个有向无环图满足以下条件：
  • 每个顶点出现一次
  • 若A顶点排在B顶点之前，则图中不存在从B到A的路径

关键路径

• AOE网，边表示活动或者任务，顶点表示事件，AOE网中仅有一个入度为0的顶点，称为源点，表示整个工程的开始：网中也仅有一个出度为0的顶点，称为汇点表示整个工程的结束

• 关键路径算法：

  • 问题：整个工程完工需要多长时间；那些活动影响工作进度，或求关键路径

  • 解析：事件（顶点）i：最早发生的事件ve（i），最晚发生时间vl（i）；活动（边）：最早开始时间e（i，j），最晚开始时间l（i，j）；工程完工时间为终点的最早发生时间；关键路径就是路径长度最长的路径

  • 算法：

    • 按拓扑排序排列顶点

    • 计算ve（j）

    • 计算vl（i）

    • 计算e（i，j）和l（i，j）

      事件	最早发生ve	最晚发生vl	活动	最早发生e	最晚发生l
      v1	0		a(1,2)
      v2	6		a(1,3)
      v3	4
      v4	5
      v5	7
      v6	7
      v7	12