图论基础

存图=

（邻接矩阵只适用于没有重边（或重边可以忽略）的情况，一般情况下不用考虑）

• 邻接矩阵

空间复杂度高：O(n^2)
查询一条边的存在情况快： O(1)
遍历一个点的所有出边 ：O(n)
遍历整个图 ：O(n^2)

• 邻接表

  空间复杂度低 ：为O(m) m为边数
  查询某条边 ： O(d+(u))即这个点的边数 ，如果边有排序，则通过二分就是O(log d+(u)) log边数的事件。
  遍历一个点的所有出边 ：O(d+(u))即该点的边数
  遍历整个图 ：O(n+m) 事件为点的个数加边数。

• 链式前向星
  与邻接表基本一致。
  优点是边有编号（在更厉害点的算法中有用）