有向和无向

边分不分方向，是图的第一个大分类。无向图的边没方向，$u$ 和 $v$ 连着就是互相连着，比如微信好友——你是他好友，他也是你好友。有向图的边有方向，$u\to v$ 不代表 $v\to u$，比如微博关注——你关注他，他未必关注你。作业依赖、网页链接、水流管道也都是有向的。

编程上的区别就一句话：存无向图时，一条边要正反各存一次。

// 无向图：u-v 双向都加
addEdge(u, v);
addEdge(v, u);

// 有向图：只加 u->v
addEdge(u, v);

坑最多的地方就在这里：把无向图当成有向图、只存了一个方向，搜索时半张图走不到，答案全错；反过来给有向图多加了反向边，也会走出题目不允许的路。另外，无向图存双向后边数会翻倍，链式前向星等结构开数组时要按 $2m$ 来开，不然越界。