数据结构【DS】图的应用

图的连通性问题

	最少边数	最多边数
无向图非连通	𝒎=𝟎	𝒎=𝒏−𝟐∗(𝒏−𝟏)/𝟐
无向图连通	𝒎=𝒏−𝟏	𝒎=𝒏∗(𝒏−𝟏)/𝟐
有向图非强连通	𝒎=𝟎	𝒎=𝒏−𝟐∗𝒏−𝟏+𝟏
有向图强连通	𝒎=𝒏	𝒎=𝒏∗(𝒏−𝟏)

最小生成树

Prim

• 选点（point）
• 时间复杂度：𝑶𝑽𝟐
• 适合边稠密

Kruskal

• 选边
• 时间复杂度：𝑶𝑬𝒍𝒐𝒈𝟐𝑬
• 适合边稀疏

回忆一下是如何通过这两个算法构造最小生成树的？

 最短路径问题

	BFS	Dijkstra	Floyd
无权图	⭕	⭕	⭕
带权图	❌	⭕	⭕
带负权值的图	❌	❌	⭕
带负权回路的图	❌	❌	❌
时间复杂度	𝑂𝑉2|𝑂(𝑉+|𝐸|)	𝑂(|𝑉2|)	𝑂(|𝑉3|)
通常用于	求无权图的单源最短路径	求带权图的单源最短路径 也可以求带权图的各个顶点间的最短路径 适合有回路的带权图的最短路径	求带权图的各个顶点间的最短路径

回忆如何通过这三种算法求最短路径？

拓扑序列

• 对于任一有向图，如果它的邻接矩阵为三角矩阵，则一定存在拓扑序列（可能不唯一），反之不一定成立。
• 若图存在拓扑序列，却不一定能满足邻接矩阵中主对角线以下的元素均为0，但是可以通过适当地调整结点的编号，使其邻接矩阵能够满足主对角线以下的元素均为0。
• 拓扑序列唯一，也不能唯一确定该图
• 若一个有向图具有有序的拓扑序列，则它的邻解矩阵一定为：三角矩阵
• 若基于邻接表，则拓扑排序时间复杂度为：𝑶(|𝑽|+|𝑬|)
• 
• BFS和DFS都可以用于实现拓扑排序

• 顶点：事件
• 边：活动

 关键路径

详细步骤做法：

节点	最早开始时间	正着找，相加，取大值
节点	最晚开始时间	反着找，相减，取小值
边	最早开始时间	从谁发出的最早开始时间
边	最晚开始时间	被指向的最晚开始时间 减去 权值

 

 

 

 

• 如何延长工程的工期？
  • 在AOE图中，关键路径上活动的时间延长多少，整个工程的时间也就随之延长多少【增加任一关键活动的时间将会增加工程的工期】
• 关键活动是什么？
  • 关键路径上的所有活动都是关键活动
• 关键路径是什么？
  • 关键路径是源点到终点的最长路径
  • 求关键路径的快速方法：找起点到终点的最长路径
• 如何缩短关键路径？
  • 只有缩短所有关键路径的长度时，整个图的关键路径才能有效缩短。
• 能任意缩短关键路径吗？
  • 不能任意缩短，一旦缩短到一定程度，该关键活动就可能变成非关键活动。
• 只有一条关键路径的时候，减少关键活动的时间会缩短工程的工期吗？
  • 会缩短工程的工期
• 有多条关键路径的时候，减少关键活动的时间会缩短工程的工期吗？
  • 不一定会缩短工程的工期
• 关键路径是唯一的吗？
  • 并不唯一。