gzr_csdn的博客

存图方式一共有三种：邻接矩阵、邻接表、前向星纯前向星还需要再加上排序的时间复杂度（当排序不是主要复杂度时适用），如果快排，时间复杂度是O(n log n)，可以用别的排序方式优化，即基数排序（不写纯前向星了，事实上，不用排序也能模仿出来前向星的核心思路，即，链式前向星也是最常用的存图方式邻接矩阵邻接表（链式前向星）邻接表（vector存边）

拓扑排序用于有向无环图（DAG），作用是给出一个序列，使得任何一条边总是起点比终点在序列中出现的位置靠前拓扑排序原理是每次找到入度为0的点，把它放进拓扑排序的序列中，然后把这个点和这个点引出的边全部删掉（当然，一个图的拓扑序不是唯一的，只要起到功效就可以了）这个排序在没碰见它的题之前就会觉得这毫无用处，举个例子，拓扑排序可以用于动态规划动态规划需要满足些什么条件？无后效性而拓扑排序像什么？过关斩将，“给出一个序列，使得任何一条边总是起点比终点在序列中出现的位置靠前”这句话恰好是无后效性的体现。