# Topological sort and Connected components in directed graph

Since I’m reading about algorithms, I figured I’d review topological sort and Kosaraju’s algorithm as well.

To sort vertices in a directed graph topologically is to arrange them into a sequence so that no vertex has an edge pointing to a vertex earlier in that sequence. Of course, this requires the graph to be DAG (directed acyclic graph).

The algorithm is simply to find the reverse postorder in DFS (depth first search) of the vertices. This is implemented by pushing a vertex into a stack after its DFS call completes. The order in which vertices are popped out of the stack is the graph’s reverse postorder. The proof is described below:

We need to prove that for every edge from s to v, s would appear before v in reverse postorder. There are several conditions:

1. v is called and returned before the call to s. In this case, s is pushed to the stack later than v, hence s appears before v.
2. v is called later than s but returned before s returns. The former conclusion also holds.
3. v is called later than s has returned. This case is impossible. Since s has an edge to v, v has to be called somewhere earlier than s returns.

Therefore, our algorithm can give us a topological sort.

Next, we use a similar way to look for connected components in DAG. A connected component is defined as a subgraph in which all vertices have a way to reach each other. This algorithm is not so obvious: first get a topological order of the reverse of the graph G – Gr, then use the order to run DFS in G. All vertices reached by one call belong to a connected component, so we can mark them.

The proof also needs some brain.

Consider the second step of the algorithm. First, it is obvious every connected component edge is called in the second step, duh. Then we prove from the other side. Say we have a vertex v that is reached by calling DFS on s. We’re gonna prove there is an edge from v to s as well.

From the way we generated the order, s appears before v in reverse postorder of Gr. Now consider Gr, we have several conditions:

1. the call to v ends before the call to s starts. This is impossible because v has an edge to s in Gr.
2. the call to v starts after the call to s, and ends before s ends. This means there is an edge from s to v in Gr, which then proves that in G there is an edge from v to s. Connected component it is.
3. the call to v starts after the call to s ends. Impossible because s appears before v in reverse postorder of Gr.

Therefore, Kosoraju’s algorithm is correct in finding connected components of DAG.

I appreciate the brilliance of the algorithms. It’s interesting because they don’t seem so hard to me now but I spent days to understand the proof the first time I read about them. I’m reading divide-and-conquer next. I’m hoping all the complicated recursions don’t play with my mind too much.

## 2,486 thoughts on “Topological sort and Connected components in directed graph”

1. 髮際線抬眉手術，就是沿著髮際線切口，將眉毛抬高的手術（見圖藍色切口）。雖然有疤痕，但是藏在髮際線，並不明顯。

2. Thanks for the sensible critique. Me and my neighbor were just preparing to do a little research about this. We got a grab a book from our local library but I think I learned more clear from this post. I am very glad to see such excellent information being shared freely out there.

3. 【運動穿搭】內建膝蓋防護員的跑褲 3M膝支撐型彈性褲 – Tong 女漢子愛漂亮 – FashionGuide 華人時尚專業評鑑 身邊的朋友們或有在追蹤我IG和粉絲團的大家應該都知道，我一直很熱愛跟男友還有姐妹們一起參加路跑活動…，

4. Ellanse洢蓮絲(依戀詩)是一款荷蘭與英國共同研發的的新型真皮填充劑，是由30的25-50微米（µm）的聚己內酯（polycaprolactone, PCL）完美微型正圓晶球，以及70的PBS-生物降解材料（carboxymethylcellulose, CMC）製成的凝膠體，這些成分都是通過FDA(美國食品藥品監督管理局)和歐洲CE認證的安全成分，在人體內水分和二氧化碳作用下可以完全被分解吸收和排出的安全物質，對人體不會產生過敏反應，因此治療前不需經過敏檢測，在使用上幾乎不產生副作用。

5. StriVectin 皺效奇蹟 商品一覽 UrCosme (＠cosme TAIWAN) 找品牌 以UrCosme指數高至低排序第1頁 StriVectin 皺效奇蹟 化妝品商品一覽，提供 StriVectin 皺效奇蹟的產品列表，以UrCosme指數高至低排列，共42件，StriVectin 皺效奇蹟的搜尋結果之第1頁

6. Roonka 荷柏園 商品一覽 找品牌 以UrCosme指數高至低排序 第1頁 Roonka 荷柏園 化妝品商品一覽，提供 Roonka 荷柏園的產品列表，以UrCosme指數高至低排列，共1件，Roonka 荷柏園的搜尋結果之第1頁

7. 這對好兄弟同場現身真的太搶眼了！你要選彭于晏還是崔始源？ Marie Claire (HK) Edition 我們常常都說閨密團，總是在說女生們，感覺都沒有在說男生們。其實娛樂圈有很多好兄弟，單是彭于晏就有不少好朋友了，例如是剛剛成為爸爸的余文樂，以及韓國型男崔始源。 彭于晏與崔始源結緣於2015年，當時因

8. The Croatian put Barcelona 2-0 ahead on Saturday in Miami with the Catalan giants eventually coming out 3-2 winners in an entertaining match, but was not happy with the referee. Barcelona midfielder Ivan Rakitic claims he was insulted by the referee during friendly win over Real Madrid

9. Sportsmail’s Craig Hope rates the performances of the Sunderland and Manchester United players and managers at the Stadium of Light. Sunderland 1-1 Manchester United PLAYER RATINGS: Juan Mata and Wayne Rooney anonymous as stoic Santiago Vergini stars

14. Yeezys http://www.yeezy.com.co/
Yeezys http://www.yeezys.us.com/
Yeezy Shoes http://www.yeezysupply.us.com/
Yeezy Shoes http://www.yeezy-shoes.us.com/
Yeezy Boost 350 http://www.yeezy-boost350.com/
Yeezy Boost 350 http://www.yeezyboost350.us.com/
Yeezy Boost 350 V2 Blue Tint http://www.yeezybluetint.com/
Yeezy 500 Utility Black http://www.yeezy500utilityblack.com/
Yeezy 500 http://www.yeezy500utilityblack.us/
Nike Air VaporMax http://www.vapor-max.org.uk/
Salomon http://www.salomon-shoes.org.uk/
Salomon UK http://www.salomons.me.uk/
Salomon Shoes http://www.salomonspeedcross4.org.uk/
Off White Jordan 1 http://www.offwhitejordan1.com/
Nike VaporMax http://www.nikevapormax.org.uk/
Nike React Element 87 http://www.nikereactelement87.us.com/
Nike Element 87 http://www.nikereactelement87.us/
Nike Plus http://www.nikeplus.us/
Nike Outlet http://www.nike–outlet.us/
Nike Outlet Store Online Shopping http://www.nikeoutletstoreonlineshopping.us/
Nike Outlet Store http://www.nikeoutletonlineshopping.us/
NBA Jerseys http://www.nikenbajerseys.us/
Air Max 97 http://www.nikeairmax.us/
Air Max 2017 http://www.max2017.us/
Air Jordan Shoes http://www.jordan-com.com/
Jordan 11 Concord http://www.jordan11-concord.com/
Cheap Yeezy Shoes http://www.cs7boots1.com/
Wholesale Cheap NBA Jerseys http://www.cheapnba-jerseys.us/
Birkenstock Sandals UK http://www.birkenstocksandalsuk.me.uk/
Balenciaga UK http://www.balenciaga.me.uk/
Balenciaga http://www.balenciagauk.org.uk/
Balenciaga http://www.balenciagatriples.org.uk/
Balenciaga UK http://www.birkenstocks.me.uk/
Balenciaga Trainers http://www.balenciagatrainers.org.uk/
Nike Air Max 270 http://www.airmax270.org.uk/