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

好消息来啦！

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

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

>知识点汇总

考点1：Definition

考点2：Graph ADT

考点3：DFS/BFS

>Definition

考点1：一般来说：V（sparse）< E < V^2 (dense)，E和V的比例是选取合适数据结构的一个标准

考点2：Degree：与该点相连的边的数量

i.           无向图：Σdeg(v) = 2 · e(G)

ii.           有向图：Σin-deg(v) = Σout-deg(v)=  e(G)

考点3：simple path：path中的vertex和edge各不相同

考点4：tree：V=E + 1

i.           spanning tree：包含了图中所有vertex的tree

ii.           forest：一组tree，各个tree之间不相连

iii.           任意两点之间路径唯一

考点5：  Clique（completegraph）

i.           clique中任意个vertices都可以构成clique

ii.           adjacent matrix中除了对角线全为1

考点6：

Hamilton path/circuit： 遍历所有vertex一次

考点7：Euler path/circuit（一笔画）

i.           遍历所有edge一次

ii.           Euler path中最多两个vertex的degree为偶数，而在circuit中有所有的degree都需要为偶数

>Graph ADT

考点1： 

Array of edges / adjacent matrix/ adjacent list三者各有利弊

例如：adjacent matrix利用寻址的方式插入和删除元素，所以复杂度为常量。

考点2：

图中的复杂度隐去了具体的系数

考点3：需要注意在编程中：ADT应用了封装，意味着外部的文件是不能直接访问adt.c的（包括结构），只能使用header file中的方法

>DFS/BFS

考点1：DFS通俗来说是沿着一条路径走到尽头再返回，所以采用的是stack结构

考点2：BFS则是优先访问较近的那些vertex，采用的是queue结构

考点3：两者遍历的时间复杂度要基于具体的graph ADT来分析

考点4：两者遍历最终都会得到一个spanning tree只是结构会不同

考点5：DFS可以用来检查cycle，比如Eulerian Cycle Algorithm等

考点6：实际运行中一般BFS相比DFS更快，空间换时间

Tutor成绩单