图的拓扑排序问题

很久没写算法题了。。

遇到一个”求图中存在环的问题“的时候,磕磕绊绊了好久。。

邻接表和邻接矩阵

就是两个两种用来存储图数据结构的方法。

  • 邻接表。一个数组,每个 index 是一个链表,每个链表就是连接着的 node
  • 邻接矩阵。用一个矩阵来存储 edge,在图比较稀疏的时候比较浪费空间

求图的时候存在环

因为在这个问题里,有向图和无向图没什么卵区别,所以也不做区分了。

DFS

直接上 dfs,遇到遍历过的,直接判定存在环。

因为担心环的重复计算

graph-cycle-dfs

就像这样,如果 1->2->3 遍历了,发现 3->1,于是判定了一波环,继续 1->3,又发现了一波环,重复计算了一波 (但是我感觉对判断是否存在环这个问题里没有问题的,拓展开来可能存在一些问题) 。

所以不仅设置一个 visited[],还要设置一个 onpath[] 来标记,已经遍历完这个 node,还是正在遍历中。一个很形象的比喻就是,初始化白色结点,遍历中灰色,遍历完了黑色。

BFS

把入度为 0 的点 (无向图就是入度为 1) 加入队列,然后取出,把该点删去,同时删去以该点为起始点的边,如此写一个 BFS。

缺点是不能输出环。因为并不是剩余的所有点都是环的顶点。

graph-cycle-bfs

图中 4 就不是环的顶点。


输入环,想拓扑排序一波,就用 DFS。加一个 pre[] 就可以了。

最短路

因为最短路是顺便写到的。所以随便记一下。

最简单朴素的最短路。

思路反正就是起始点入队列,然后不断更新 dis[]

References