【学习笔记】数据结构与算法：图

【学习笔记】数据结构与算法：图

1 概念

1. 图
2. 图的类型
   • 图分为无向图和有向图。无向图由顶点和边构成，有向图由顶点和弧构成。弧有弧尾和弧头之分。
   • 如果任意两个顶点之间都存在边叫完全图，有向的叫有向完全图。若无重复的边或顶点到自身的边则叫简单图。
3. 顶点与边的关系
   • 图中顶点之间有邻接点、依附的概念。无向图顶点的边数叫做度，有向图顶点分为入度和出度。
   • 图上的边或弧上带权则称为网。
4. 连通图
   • 图中顶点间存在路径，两顶点存在路径则说明是连通的，如果路径最终回到起始点则称为环，当中不重复叫简单路径。
   • 若任意两顶点都是连通的，则图就是连通图，有向则称强连通图。图中有子图，若子图极大连通则就是连通分量，有向的则称强连通分量。
   • 无向图中连通且 n 个顶点 n-1 条边叫生成树。有向图中一顶点入度为0其余顶点入度为1的叫有向树。一个有向图由若干有向树构成生成森林。

2 图的存储结构

1. 邻接矩阵 Adjacency Matrix
   组成：顶点数组（一维，存储顶点信息）+边数组（二维）
   无向图的边数组是一个对称矩阵
   

2. 邻接表 Adjacency List
   

   邻接表（链表是出边） vs 逆邻接表（链表是入边）

3. 十字****链表 Orthogonal List（针对有向图）

   • 本质：同一条边只用一个结点表示；结合邻接表和逆邻接表，方便同时访问出边和入边
   • 组成

     • 顶点表 data | firstin | firstout

     • 边表

       1. tailvex	headvex	headlink	taillink（headlink/taillink指向一个边结点整体）
          该边的弧尾	该边的弧头	终点相同的下一条边	起点相同的下一条边

   • 找入边：顶点表的顶点→firstin→headlink
   • 找出边：顶点表的顶点→firstout→taillink
     

4. 邻接多重表（针对无向图）

   • 查找一个顶点的所有邻边：data→firstedge→ivex：ilink / jvex：jlink
   • 注意：ilink/jlink指向一个边结点的ivex或jvex而非整体
     

5. 边集数组

3 图的遍历

深度优先遍历 DFS

1. 逻辑：树的前序遍历；递归实现
2. 伪代码

     def DFSTraverse():visited = [全部未访问]for 每一个顶点: if 未访问过这个顶点: DFS(从这个顶点开始) #连通图只会有一次def DFS():更新visited对该顶点操作for/while 每个与该顶点邻接的顶点: #矩阵可用for，链表可用whileif 未访问过这个顶点: DFS(这个邻接顶点)
   

广度优先遍历 BFS

1. 逻辑：树的层序遍历；用队列实现

   • 队列存放的是待处理的顶点11.12 11.13
   • 每次循环处理一个元素时做三件事：该元素出队列→操作该元素→探测其孩子顶点并入队列（它们是下一层的，还没轮到它们）
     

2. 伪代码

      def BFSTraverse():queue = 一个队列for 每一个顶点:if 未访问过这个顶点: #连通图只会有一次enqueue(当前顶点) # 若为连通图，只针对第一个元素while 队列非空: # 这个循环不断在队列中拿元素出来处理一个顶点 = dequeue()对顶点操作for/while 每个与该顶点邻接的顶点: #矩阵可用for，链表可用whileif 未访问过这个顶点: enqueue(这个邻接顶点)
   

4 最小生成树 Minimum Cost Spanning Tree

目标：以最小的权值和构造一个图的连通网

Prim 算法

1. 基于邻接矩阵或邻接表
2. 逻辑：
   • 从任意一个顶点出发
   • 每轮选一个新的顶点纳入生成树，这个顶点是目前到当前整棵生成树（到生成树上的任意顶点）的距离最小的
   • 直到所有顶点都被纳入生成树
3. 伪代码

     def miniSpanTree_prim(图):lowcost = [第i个元素存放当前生成树和第i顶点之间已知的最小距离的列表]# 为0表示该顶点已在生成树里，为无限大表示该顶点与生成树还没有边相连adjvex = [第i个元素存放使其有上述所说的最小距离的边的邻接顶点]# 这个邻接顶点是已经在生成树里的#每轮将一个新的顶点纳入生成树for i = 1:n-1（n-1次循环，因为初始已经有一个顶点算在树里了）:k = index(min(lowcost)) #找到与当前生成树距离最小的顶点，k是其序号将该路径加入最小生成树，并标注已加入 #（输出这条路径OR存放到某个地方）for j = 1:n:修正lowcost和adjvex# 因为这个被纳入生成树的顶点k又“开发了一小片新大陆”
   

4. 时间复杂度：O(n^2)，n为顶点数

Kruskal 算法

1. 基于排好序的边集数组
2. 逻辑
   • 每次选取列表内权值最小&不会使得生成树形成环路的边 加入生成树
   • 关键：排除形成环路的情况 - 对待检验的边的两个顶点分别给它们“溯源”：
     • 如果某两个点本身还没被连起来，则它们的“源顶点”不会相同，可以相连
     • 如果本身已经有一条路径连起这两个点，则它们会溯源到同一个顶点，不能再相连
3. 伪代码

      def miniSpanTree_kruskal():for i = 1:n: （循环每一条边）n = find_parent(边[i].begin)m = find_parent(边[i].end)if n != m: # n==m意味着这条边连起来会形成环路将该边加入最小生成树def find_parent()return parent
   

4. 时间复杂度：O(eloge)，e为边数

5 最短路径 Shortest Path

Dijsktra 算法

1. 逻辑

   • 很重要的一个逻辑是：Q 为什么只要在每一轮循环开始时，在还没确定最短路径的那些顶点中选一个已发现的到它的路径比到其他顶点的路径都短的，那个到它的路径就一定是到它的最短路径？明明这些值还在不断被修正？
   • A 要注意在最短路径列表shortpathtable中，对那些最短路径未确定的顶点，表格对应位置存放的是已发现的最短路径，而这个已发现的最短路径 = {v0到某个已确定最短路径的顶点v1的路径长度（下图的m）}+ {v1到该v的一条直接相连的边长（下图的a）}；
   • 要用最短路径走到v，肯定是要从v1开始的：要么从v1直接走到v，长度{m+a}；要么从v1先走到另外一个点vi，再有某种方式走到v。后者的长度为{m+b+c}，虽然c未知，但我们已经知道{m+a}<{m+bi}（对任何i），所以必有{m+b+c}>{m+a}，所以{m+a}无论如何都是最佳选择

2. 伪代码

      def shortesetPath_Dijsktra():adjvex = []shortpathtable = []#每轮算出v0到某一个顶点的最短路径for i = 1:n-1 （n-1次循环）:k = index(min(shortpathtable))（此时shortpathtable在k处的值就已经是最短路径）for j = 1:n:修正shortpathtable和adjvex
   

   • 选顶点
     

   • 修正
     

3. 时间复杂度：O(n^2) （算出一个顶点和其余所有顶点间的最短距离）

Floyd 算法

1. 核心：如果经过下标为k的顶点的路径比原两点v,w间路径更短，则将当前两点间权值设为更小的一个（抛开传统的点到点的思维）
2. 伪代码

     def shortesetPath_Floyd():for k:for a:for b:if 路径[a→k]+路径[k→b] < 路径[a→b]:修正a→b的最短路径
   

3. 时间复杂度：O(n^3)（一次过算出了所有顶点两两之间的最短距离）

6 有向无环图的应用

拓扑排序 Topological Sorting

1. AOV网：用顶点表示活动，边表示活动之间的制约关系
2. 目标：对一个有向（无环）AOV网构造拓扑序列
   拓扑序列是一个顶点序列，若存在从vi到vj的路径，则序列中vi要在vj之前（描述顶点间的先后发生的关系）；拓扑序列不唯一
3. 核心：不断从图中选取并删除入度为0的顶点及以这个顶点为弧尾的弧
4. 逻辑：使用队列/栈（类似广度优先搜索中的方式）

关键路径 Critical Path

1. AOE网：用顶点表示事件，边表示活动