This is going to be a theoretical article rather than a practical one.

A solid background preparation for this post would be familiarity of **how a graph is represented in the computer**: as an adjacency matrix or a lists of edges.

Of course, you don’t have to know [yet] how to implement that with code, as already mentioned, this is going to be mainly a theoretical article!

Another important symbol you’ll encounter is [n], which indicates all the natural numbers from 1 till n: example: [4] = {1,2,3,4}, [1] = {1}, …

# Topological Sort

## Given a graph , return a function such that(s.t)

### What exactly does that mean, in English?

Having an edge(a line that connects 2 vertics) (notice that the internal order between u and v is very important: ), we want to associate to vertex a larger number than vertex

**Simple as that.**

Let’s begin by searching for a vertex in the graph, with no edges entering it. such vertex is knows as a *“Source” **. Example(Image from Wikipedia):*

In the graph above,** vertexes number 5, 3, 7 are all sources**, since no edges are entering to them.

In mathematical terms, we write:

which reads: “the in degree of equals 0″.

Without hesitating, we could confidently** assign to the source vertex the lowest number we are allowed to assign!** *Why?* because there is no such an edge whereas is our source!, therefore, there is no s.t

Next, we **remove our source from the graph**(and all the edges that get out off it) from the graph, and search for another source in the graph, again.

## The whole algorithm:

Input: Output: 1) 2) while 2.1) 2.2) 2.3) 2.4) remove u and all it's edges 3) return L()

## Runtime

Mainly, the part which consumes the longest time is the `while`

loop, the others(i.e part (1) and (3) just take time)

part (2.1): Finding the source is done by iterating over all the vertices of the graph, and checking whether . Therefor, this part takes time, where is the number of vertices in the graph .

part (2.2) and (2.3) take just

part (2.4) is done by iterating on all the vertices which satisfy the condition . In other words, those vertices are the end-points of the edges that branches out the source .

The number of those vertices equals .

Note that

### Total Runtime( is the source in the i-th iteration):

That’s quit a large runtime though! We need to optimize the algorithm above so that the runtime gets down to

As you already seen, the part which consumes a lot of time, is finding a source vertex. Thus, we should modify the algorithm to reduce the process of finding a source.

**What you’re about to see is:**

- finding all the possible sources in the graph(before entering the
`while`

loop) which takes as we already discussed. - In the
`while`

loop, when removing the current source vertex , we check if any of the vertices with edges branching out of was transformed to a source, if so, then we’re adding them to the group of ‘sources’. This last part takes whereas is the current source to be removed.

After all the iterations of the loop, this part takes because

### Here is the modified algorithm:

1) 2) 3) while 3.1) 3.2) 3.3) 3.4) remove u and all it's edges 3.5) foreach in u.neighbours : 3.5.1) if : 3.5.1.1) 4) return L()

The runtime of the modified topological sort algorithm above is

# Proof of Correctness

All been nice and smooth until now..(or was it?! 🙂 )

**However…**

### Does the algorithm works always OR what happened was one Big lie??

Well…it’s kinda BOTH!!

**wait**..before you report the blog…

I kept the fact that we’re dealing with graphs called **DAG** in this sorting algorithm!!

*DAG – Directed Acyclic Graph!*

Now that we’re on steady formation, let’s proof the correctness by stating the following Rule:

**Rule 1:** In a DAG, there is always at least one source vertex.

**Proof 1:**

Start by , if a source, then we’re done! Else, consider , such that , now we know that because the graph is DAG, therefor we check if is a source, if not, we’ll take and so on…

At the iteration, we’ll be looking at , notice that . However, when the iterations are done (since and when means that we looked at all the vertices in the graph because $latex v_{n+1} \notin V), but the iterations are done when we find a source! Thus there is always a source vertex in a DAG.

**Rule 2:** When removing a vertex from a graph, it stays DAG (and thus we can find a source in it again)

**Proof:**

This rule guarantees that the loop does not stuck at any iteration because it didn’t find a source even though it didn’t finished looking at all the vertices yet.

So, when removing a vertex, we basically removing the edges which branches out of it, therefore, we cannot get to have a circle in out DAG!