# How to dress like a man

Today **Topological sort** will tell you how to dress like a man 😄

# Table of Content:

**What is a Graph?****What is Topological Sort?****Applications of Topological Sort****Dressing like a Man(example)****How to code**

# What is a Graph?

A graph is a simple **non-linear** data structure consisting of **Nodes** and **Edges** (Node are also referred to as Vertices). An edge connects a pair of nodes. Generally a graph is represented as **G(u, v) **where **‘u’ and ‘v’ are vertices.**

In the below graph we have A,B,C,D,E vertices and edges connecting them.

This is a **Directed Graph**(edges are directed from one vertex to another).

I would like to give a simple intuition for topological sort. From the above graph let say the vertices represent a Task, and an edge represent dependency.

For Example an Edge (B, D) means ‘D’ has a dependency on ‘B’. This means that Task ‘D’ will only start once Task B is done.

Similarly ‘C’ has a dependency on ‘A’ and ‘B’(directed edges), so Task C will only start once Task ‘A’ and ‘B’ are done.

# What is Topological Sort?

**Topological sort** is a linear sorting algorithm used in a **Directed Acyclic Graph**. In a graph **G(u, v)** topological sort will sort every possible edge (u, v) such that ** ‘u’ always comes before ‘v’** in sorting order.

**Confused ? 🤔**

Lets take an example:-

In above graph let take an edge (1, 2) . In Topological sorting ‘1’ will always be before ‘2’. Now apply this same approach on all the possible edges**(u, v)** where ‘u’ and ‘v’ are the vertices of the graph.

One possible topological sort would be **1, 3, 2, 5, 4, 7, 9, 6, 8**

There can be many possible Topological sort orders but **the key point is for every edge(u, v), u will always proceed v.**

# Applications of Topological Sort:

Topological sort is a very useful sorting algorithm and there are many applications of it:

**Prerequisite for a given courses-**If a course have some prerequisite courses, and these courses also have some prerequisite than it would be best to represent it with a graph, where vertices are the courses and edges represent dependencies (**or prerequisite of a given course**).

Here topological sort will give you an order in which you should take a course (giving all the prerequisite of a given course).**Build System-**If a library have dependency on other libraries, and these libraries also have some dependencies, so the best way to represent this is with the help of a graph.

Here topological sort will give you an order in which you should build the libraries.**Dressing like a man-**Now this is what we will be looking for 😄

(but clearly there are many more useful applications of Topological sort).

The Graph should be a Directed “Acyclic” Graph (DAG):This means that

the graph should not have a cycle. If the graph have cycle than there won’t be any possible solution.Lets take the prerequisite course example and see what’s wrong with having a cycle.

Above graph represent the prerequisite of different courses. Say I want to enroll in course 2, its prerequisite is course 1, whose prerequisite is course 4 & 5, course 4's prerequisite is course 3, whose prerequisite if course 2 😵.**(AND WE ARE STUCK IN A CYCLE)**We started with course 2 and ended at course 2. This means that practically I cannot take any course. This is why cycle should not be present in a graph for Topological sort.

# Dressing like a Man:

Now with all the above discussion let take a look at how to dress like a man?

First we will have to create a graph of all the dependencies.

Below we have our graph with all the dependencies:-

In the above graph, **shoes** has dependencies on **socks** and **pants**.

This means, **we cannot wear shoes without wearing socks or pants**(which makes sense).

If we run topological sort on above graph we get one possible sorting order(dressing order).

**shirt →tie →socks →watch →pants →shoes →belt →coat**

And that is how you dress like a man 😎

# How to write code for Topological Sort:

Writing code for topological sort is very simple. All you need to know is how to run Depth-first Search on a graph**(if you don’t take a look at my previous post)**

**Steps to write code for topological sort:**

- First perform DFS(G) on all the vertices.
- As each vertex is finished searching, insert it in front of a
**linked list**. - Print your linked list to get topological sort order.

And Voila!! Now you will have a possible dressing order.

Also check out the full code on my Github account below.