1、图论基础

一、图的逻辑结构

图是由边和节点组成的。

本质上就是个高级点的多叉树而已，适用于树的 DFS/BFS 遍历算法，全部适用于图。

实际上我们表示一个图一般使用邻接表或者邻接矩阵来实现。

1、并查集

一、基础概念

什么叫做并查集。并查集是一种用于管理元素所属集合的数据结构，实现为一个森林，其中每棵树表示一个集合，树中的节点表示对应集合中的元素。

主要是解决图论中「动态连通性」问题的

简单说，动态连通性其实可以抽象成给一幅图连线。比如下面这幅图，总共有 10 个节点，他们互不相连，分别用 0~9 标记：

2、二分图

一、二分图的定义

官方定义比较绕口，二分图的顶点集可分割为两个互不相交的子集，图中每条边依附的两个顶点都分属于这两个子集，且两个子集内的顶点不相邻。但是通俗理解就是能不能将一个边的两个节点分别属于不同颜色的集合中

3、环检测和拓扑排序

图这种数据结构有一些比较特殊的算法，比如二分图判断，有环图无环图的判断，拓扑排序等。

而对于拓扑排序首先就是要判断图中是不是有环，如果有环就没有必要进行排序了。

而什么叫做拓扑排序呢就是

直观地说就是，让你把一幅图「拉平」，而且这个「拉平」的图里面，所有箭头方向都是一致的，比如上图所有箭头都是朝右的。

如果一幅有向图中存在环，是无法进行拓扑排序的，因为肯定做不到所有箭头方向一致；反过来，如果一幅图是「有向无环图」，那么一定可以进行拓扑排序。

一、环检测——207. 课程表