Hello,I'm Proking.

今天，跟着昨天晚上的图的相关知识，他又讲了图的遍历，也就是求最短路径。 求最短路径先讲了floyd算法。最大的收获就是明白了为什么中转点k要放在外里面。 可以用反证法。意思就是：如果当前中转点放在外面或i,j循环的中间时，就会使得如果当前第k个点都大于i,j的话，第i个点到第k个点或第j个点到k点就会还没算好，如果还没算好再去更新i到j的最短路径就没有意义了，也就会使得答案错误。而放在里面则不

首先，那个师兄跟我们讲了讲图的一些基础，例如邻接矩阵可以用邻接表代替之类什么的（然而在没听过邻接表这个东西的时候就一般都这样储存了，原因是我们拥有智商）。 接下来统一记录我们以前不知道的一些知识： 无向图有向图：其实顾名思义，无向图就是没有方向，只要与其相连的边都可以互相到达。而有向图就是指只能按照一条边边的方向到达一条边。 阶：图中顶点的个数为阶。 完全图：每一条边都与其余的每条边相连（