Topological Sorting Related

Leave a comment

December 18, 2016 by oneOokay

拓扑排序以及相关题目:

拓扑排序

  • For each directed edge A -> B in graph, A must before B in the order list.
  • The FIRST node in the order can be any node in the graph with NO nodes direct to it.

在图论中,由一个有向无环图的顶点组成的序列,当且仅当满足下列条件时,称为该图的一个拓扑排序英语:Topological sorting)。

  1. 每个顶点出现且只出现一次;
  2. 若A在序列中排在B的前面,则在图中不存在从B到A的路径。

也可以定义为:拓扑排序是对有向无环图的顶点的一种排序,它使得如果存在一条从顶点A到顶点B的路径,那么在排序中B出现在A的后面。

有两种方法来达成拓扑排序:DFS(Stack)(TODO)和BFS(Queue)

BFS思路:也叫:Kahn’s algorithm for Topological Sorting

  1. 构建一个HashMap<Node, Integer>用来存node和该node的入度(int) 代表该node有x个node依赖于它(在完成该node前,要完成x个node). node的最小入度为1.所以作为head的不存在这个HashMap中(因为head的入度为0)或者单独的一个点也不在这个hashmap中,因为入度也为0.
  2. 先把HashMap中不存在的node放入result中(把入度为0的node放到result中),同时也放入queue里面。
  3. 从queue poll,对于当前Node的所有neighbors(neighbors表示从当前点Node可以抵达的node collection),把neighbor在HashMap中的value减1;同时判断是否已经减到0 了。如果已经减到0的话,(此时也就相当于一个起点了)就把这个neighbor加入到queue和result中。然后继续。

总体的来说

  • hashmap里面存的是在做点a之前,要先完成其他x个点.
  • arraylist的点n和它的neighbours代表从a能够抵达到的点的集合.
  • 处理点n的时候,对于他的每一个neighbor,n是完成它neighbor之前的必须要完成的一个点.这样在hashmap里面代表neighbor的一个前置点已经完成了,于是neighbor在map里面的value要减1.
  • 对于一些题目给出task a 的前置task有x,y,z:要把这一关系先转换为x,y,z的下一个neighbor为a的这样一个映射关系.从而我们能够通过当前的task得到之后的task而不是逆推.

DFS思路:

for loop遍历每一个点, 遇到一个点对它的neighbor进行DFS,直到最后.到了这一条path的最顶点了,把该点加入到stack里面.这样stack里头按pop出来的顺序就是topological sorting的顺序.最顶上的排靠前.

注意以上是建立在这些点中不存在环的情况下的.存在环的情况看Course Schedule II

以及具体的code….也看那里.

 

Advertisements

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s

%d bloggers like this: