远方的岛第四章 图结构及其应用算法
type
status
date
slug
summary
tags
category
icon
password
4.1图的基本概念
图G(V,E)、无向图、有向图、简单图、无向完全图、有向完全图
相邻（无向图：互为邻接点/有向图：点邻接到点、边/弧依附于点）、网（带权图）、无向图：度/有向图：入度、出度，度=入度+出度、路径、简单路径、简单回路
（无向图）连通、连通图、连通分量：非连通图的极大连通子图
（有向图）强连通图、强连通分量
生成树：包含全部顶点的一个极小连通子图
A
A
A
C 21 - 6
C A是路径不是弧
C
A
B 画画得了
B
A
4.2图的存储结构
1.邻接矩阵
2.邻接表
有向图：正/逆邻接表
3.有向图的十字链表
4.无向图的邻接多重表
C
D
B
A
B
C
D
A
B
4.3图的搜索（遍历）
深度优先搜索DFS：栈
广度优先搜索BFS：队列
无向图（的搜索）及其应用
A
C
CACA
AA
D 34
B
AB
D
D
A
D
4.4最小生成树算法
Prim算法（从点出发）：LOWCOST[ ] CLOSSET[ ]
时间复杂度O(V²)
Kruskal算法（从边出发）：edges[ ] parent[ ] 并查集
时间复杂度O(ElogE) 适用于边稀疏顶点较多的图
B
C
A
C
4.7最短路径算法
Dijkstra算法（贪心算法）：从某个点出发的最短路径
D[ ] P[ ] S[ ] 时间复杂度O(n²) 边上权值非负情形的单源最短路径
Floyd-Warshall算法（动态规划算法）：任意两个顶点之间
D[ ][ ] P[ ][ ] 时间复杂度O(n³) 边上权值为任意值的单源最短路径
【图-最短路径-Floyd(弗洛伊德)算法】 https://www.bilibili.com/video/BV19k4y1Q7Gj/
A
C
B
4.8拓扑排序算法
有向无环图DAG、AOV网、拓扑排序、拓扑排序算法（队列、栈）
D
D
D
D
C
C
C
D
A
A
4.9关键路径算法
AOE网：源点、汇点
路径长度、关键路径、关键活动
（顶点：事件vk）最早ve/最迟发生时间vl、（弧：活动ai）最早e/最迟开始时间l
时间余量d
C
C
C
期末真题
2021
A
C
2020
2019
2017
C
B
2016
C
O(m+e)
极大连通子图
从源点到汇点路径长度最长的路径
2015
A
Kruskal
10 38 完全图 生成树
2020
Loading...