转眼，第一学期已经开课到Week 7 ,  OMG !! 很多小伙伴都已经开始反应说课程太多！内容复杂！英文不好！并且IT专业是众所周知的高难度专业，课业压力非常繁重。

好消息来啦！

匠人和新南IT 专业的小哥哥，注意是全科HD学霸小哥哥哦！！

联合整理知识点，对大学课程内容进行每周回顾与讲解，总结开学两周知识点，紧跟学校课程节奏，帮助同学们以最快的时间答疑解惑，缓解课业压力。

>知识点汇总

考点1： Transitive closure

考点2： MST

考点3：  shortest path

考点4：  Linked List

考点5：   Maximum flow

> Transitive Closure

考点1：简而言之就是检查两点之间是否存在路径

考点2：暴力搜索的时间复杂度为O(V^3)

>Minimum Spanning Tree

考点1： 同一图中可能存在多个MST

考点2： Kruskal's Algorithm

i.           将edge排序，插入v-1个可行的edge（不构成cycle）

ii.           此处初始MST可以看成是所有的顶点集合

iii.           检查cycle时使用Union-Find 的数据结构会比DFS更快

考点3：Prim's algorithm

i.           随机选一个顶点，也可以看做是初始的Tree，之后选出最小且不构成cycle的edge加入Tree，此处edge要和Tree相邻

ii.           这一算法本质是贪心算法

iii.           能够保证optimal，但是结果得到的MST不唯一，这取决于起点和排序方式

>Shortest path

考点1：Single-source Shortest Path(SSSP)：Dijkstra's Algorithm

i.           每次从vSet（所有未访问过的顶点，也就是没有作为起点使用过）中选取一个存在最短路径、且在所有可选顶点中路径最短的顶点，并将其作为新起点，更新该点的所有out-going edge（使用relaxation 更新）

ii.           结果是optimal的

iii.         最简单版本的时间复杂度为O(V^2)

可以通过优先队列加速选取新顶点的这一步，新的时间复杂度有多种写法，比如：O(Elog(V))

考点2：All-pair Shortest Path (APSP)：Floyd's Algorithm

i.           其实和transitive closure没差，别搞混for loop顺序就行

ii.           同理，复杂度也极高

> Network Flow：Edmonds-Karp

考点1：注意每次选取最短的可通行的路径

考点2：时间复杂度为O(V·E^2)，因为最多有O(V·E)条路径，书中有详细证明

Tutor成绩单