今天我们学习了图论的一些基础内容

图论的存储

邻接矩阵

可以利用二维数组存储
若用mp来表示该矩阵，u为起点，v为中点，w为边权，edge（u,v）表示从u到v的边，则mp[u][v]=|edge（u,v）|=w

有向图mp[u][v]=w
无向图mp[u][v]=mp[v][u]=w
但是此方法在存储稀疏图时会造成较大的空间浪费

邻接表

用一个数组head来存储以i为起点的边序号，再以另一个数组next存储head[i]，next[j]=head[i]
并令head[i]=next[j] (编号为j的边同样为以i为起点的边)

遍历

DFS与BFS

Floyd

松弛操作dp[u][v]=min(dp[u][v],dp[u][P]+dp[P][v])
注：P表示中转点编号

代码模板

时间复杂度O（n^3）