6.10 Topological Sorting (with Examples) | How to find all Topological Orderings of a Graph

Summary

This video script introduces topological sorting, a linear ordering of vertices in a directed acyclic graph (DAG), where for every directed edge UV, vertex U comes before V. The script explains that a graph must be directed and acyclic to have a topological sort, and demonstrates the process of finding such an ordering by calculating the in-degree of vertices, removing those with in-degree zero, and updating the graph iteratively. It clarifies that a DAG can have multiple valid topological sorts and illustrates the method with examples, highlighting the impossibility of sorting graphs with cycles.

Takeaways

• 📚 Topological sorting is a linear ordering of vertices in a directed graph such that for every directed edge UV, vertex U comes before V in the ordering.
• ⛔ The graph must be directed and acyclic (DAG) for topological sorting to be possible; undirected graphs or graphs with cycles cannot have topological ordering.
• 🔍 To perform topological sorting, start by identifying the in-degree of each vertex, which is the number of incoming edges to the vertex.
• 🔄 Begin the sorting process by selecting vertices with an in-degree of 0 and deleting them along with their outgoing edges from the graph.
• 🔄 After deletion, update the in-degrees of the affected vertices and repeat the process until all vertices are ordered or no vertices with in-degree 0 are left.
• 🤔 If at any point no vertex with in-degree 0 is found and there are still vertices left, it indicates the presence of a cycle, making topological sorting impossible.
• 🔢 In-degree is recalculated after each deletion of a vertex and its edges to reflect changes in the graph structure.
• 🌐 A directed acyclic graph (DAG) can have more than one valid topological ordering, showcasing the flexibility in the sorting process.
• 📉 The process involves iteratively reducing the in-degree of vertices by removing those with an in-degree of 0 and their associated edges.
• 📈 The topological sort order is constructed incrementally, with vertices being added in the order they satisfy the in-degree of 0 condition.
• 🔗 The presence of a cycle in a graph is a critical factor that prevents the successful completion of a topological sort, as it leads to an impasse in the sorting process.

Q & A

What is topological sorting?

Topological sorting is a linear ordering of the vertices in a directed acyclic graph (DAG) such that for every directed edge UV, vertex U comes before vertex V in the ordering.

What is the prerequisite for a graph to have a topological ordering?

A graph must be directed and acyclic to have a topological ordering. If the graph is undirected or contains a cycle, topological sorting is not possible.

What is the significance of in-degree in topological sorting?

In-degree is the number of incoming edges to a vertex. It is used to determine the starting point for topological sorting, as the vertices with in-degree of 0 are the first to be placed in the ordering.

How does the presence of a cycle in a directed graph affect topological sorting?

If a directed graph contains a cycle, it is not possible to find a topological ordering for that graph, as the presence of a cycle violates the linear ordering condition required for topological sorting.

Can a directed acyclic graph have more than one topological ordering?

Yes, a directed acyclic graph can have more than one topological ordering. The script provides examples where different selections of vertices with in-degree 0 lead to different valid orderings.

What is the first step in the process of finding a topological ordering of a graph?

The first step is to find the in-degree of each vertex in the directed graph, which will help identify the vertices that can be placed first in the topological ordering.

What happens when you delete a vertex from the graph during topological sorting?

When a vertex is deleted from the graph, all its outgoing edges are also deleted. This may change the in-degree of other vertices, which could lead to new vertices having an in-degree of 0 and being candidates for the next position in the ordering.

How does the script illustrate the process of topological sorting?

The script uses examples of directed acyclic graphs and walks through the process of identifying vertices with in-degree 0, deleting them along with their outgoing edges, and updating the in-degrees of other vertices until a topological ordering is formed.

Why is it necessary to update the in-degrees of other vertices after deleting a vertex and its edges?

Updating the in-degrees is necessary because the deletion of a vertex and its edges changes the connectivity of the graph. This may result in other vertices having their in-degree reduced to 0, making them candidates for the next step in the topological sorting.

What is the final result of topological sorting for a directed acyclic graph?

The final result is a linear ordering of all vertices such that every directed edge from vertex U to vertex V appears in the ordering as U before V. This ordering is not unique and can vary depending on the selection process.

Outlines

00:00

📚 Introduction to Topological Sorting

This paragraph introduces the concept of topological sorting, which is a linear ordering of vertices in a directed acyclic graph (DAG) such that for every directed edge UV, vertex U comes before V. The importance of the graph being acyclic is emphasized, as a cycle would make topological sorting impossible. The paragraph also mentions that a DAG can have multiple valid topological orderings. The method begins by identifying the in-degree of each vertex, starting the sorting with vertices that have an in-degree of zero, and iteratively removing them and their outgoing edges, updating the in-degrees of the affected vertices.

05:00

🔍 Step-by-Step Topological Sorting Process

The second paragraph delves into the step-by-step process of topological sorting. It explains how to update the in-degrees of vertices after removing a vertex with an in-degree of zero and its outgoing edges. The paragraph illustrates the process with examples, showing how the in-degree changes as vertices are removed and how the process continues until all vertices are placed in a topological order or until it's determined that a cycle prevents a valid ordering.

10:02

🚫 Cycle Detection in Topological Sorting

The final paragraph discusses the importance of cycle detection in determining whether a topological sort is possible. It provides examples of graphs with cycles and explains why these cannot be topologically sorted. The paragraph also demonstrates how the process of topological sorting can reveal the presence of cycles by reaching a point where no vertex has an in-degree of zero, indicating a cycle and the impossibility of a valid topological ordering.

Keywords

💡Topological Sorting

Topological Sorting is a linear ordering of vertices in a directed graph such that for every directed edge UV, vertex U comes before V in the ordering. It is a key concept in the video, as it is the main topic being discussed. The script explains that topological sorting is only possible for directed acyclic graphs (DAGs), and it cannot be performed on graphs with cycles. The video provides examples of how to perform topological sorting by starting with vertices that have an in-degree of zero and iteratively removing them and their associated edges until all vertices are ordered.

💡Directed Acyclic Graph (DAG)

A Directed Acyclic Graph, or DAG, is a directed graph with no cycles. It is essential in the context of topological sorting because only DAGs can be topologically ordered. The script emphasizes that the presence of a cycle in a graph makes topological sorting impossible, as demonstrated with examples where cycles prevent the completion of the sorting process.

💡In-Degree

In-Degree refers to the number of incoming edges to a vertex in a directed graph. The script explains that finding the in-degree of each vertex is the first step in the topological sorting process. Vertices with an in-degree of zero are the starting points for creating the topological order because they have no incoming edges, indicating that they can be placed at the beginning of the ordering without violating the ordering rules.

💡Out-Degree

Out-Degree is the number of outgoing edges from a vertex in a directed graph. While the script does not explicitly define out-degree, it is implied when discussing the deletion of edges after selecting a vertex with an in-degree of zero. The out-degree affects the topological sorting process as it determines how many edges need to be removed when a vertex is placed in the order.

💡Cycles

Cycles in a graph refer to a sequence of edges that starts and ends at the same vertex, forming a loop. The video script makes it clear that cycles are a critical factor in determining whether a graph can be topologically sorted. If a graph contains a cycle, as shown in the examples, topological sorting is not possible because it would violate the linear ordering rule.

💡Linear Ordering

Linear Ordering is a sequence in which elements are arranged in a line following a specific order. In the context of the video, linear ordering is synonymous with topological ordering, where vertices are placed in a sequence that respects the directed edges of the graph. The script illustrates how topological sorting creates a linear ordering that satisfies the condition that for every directed edge UV, U appears before V in the sequence.

💡Vertex

A vertex, also known as a node, is a fundamental unit of a graph, representing an entity with which edges connect to other vertices. The script frequently refers to vertices when explaining the process of topological sorting, emphasizing their role in forming the order and how their in-degrees determine the sequence of the sorting.

💡Edge

An edge in a graph is a connection between two vertices, representing a relationship or link between them. The script discusses edges in the context of directed graphs, where edges have a direction, and their orientation is crucial for topological sorting. The process involves considering the edges that are incoming to a vertex (in-edges) and outgoing from a vertex (out-edges).

💡Algorithm

Although the term 'algorithm' is not explicitly mentioned in the script, the process described for topological sorting is an algorithmic procedure. The steps of finding in-degrees, selecting vertices with zero in-degree, deleting vertices and their edges, and updating the graph are all part of an algorithm to determine the topological order of a DAG.

💡Multiple Orderings

The concept of multiple orderings refers to the possibility that a directed acyclic graph can have more than one valid topological sort. The script illustrates this by showing different sequences that satisfy the topological sorting conditions for the same graph, emphasizing that there is not a single correct answer but multiple valid solutions.

Highlights

Topological sorting is a linear ordering of vertices in a directed acyclic graph (DAG) such that for every directed edge UV, vertex U comes before V.

A graph must be directed and acyclic to perform topological sorting; undirected or cyclic graphs are not suitable.

The presence of a cycle in a directed graph makes topological ordering impossible.

Topological sorting can have multiple valid orderings for a single directed acyclic graph.

The method to find topological sorting involves identifying the in-degree of each vertex in the graph.

In-degree is the number of incoming edges to a vertex, and out-degree is the number of outgoing edges.

The topological sorting process begins by selecting vertices with an in-degree of zero.

After selecting a vertex with in-degree zero, all its outgoing edges and the vertex itself are removed from the graph.

The in-degrees of the vertices affected by the removal of edges are updated in the next step.

The process repeats, selecting the next vertex with an in-degree of zero and removing it along with its edges.

If at any point no vertex with an in-degree of zero is found, and there are still vertices with in-degree greater than zero, the graph contains a cycle.

The video provides examples to demonstrate the method of finding topological sorting for different graphs.

In the examples, it's shown how the graph's structure changes with each step of the topological sorting process.

The importance of updating in-degrees after each removal is emphasized for the correct progression of the sorting.

The video concludes by reiterating that for every directed acyclic graph, more than one topological ordering is possible.

A directed graph with a cycle cannot have a topological ordering, as demonstrated with examples.

The video explains the theoretical and practical aspects of topological sorting with clear examples.

The method is applicable in various fields such as project scheduling, task sequencing, and more.

Transcripts

hi guys welcome back in this video I'm

going to discuss with you what is

topological sorting or you can also say

topological ordering fine what is the

topological ordering and how to find out

topological altering of a given graph

fine so first of all we'll just discuss

some key points of topological sorting

what is topological sorting a

topological ordering okay first point is

to find out topological ordering that

graph should be directed and acyclic

that is the must condition graph should

be dug that means directed and acyclic

graph if graph is undirected you cannot

find out topological sorting if graph is

directed but it contains any cycle like

this suppose we have 1 2 & 3 3 vertices

this 1 2 2 3 & 3 to 1 1 to 2 2 to 3 and

3 to 1 the cycle is wrong now so such

type of cycle contains if in graph then

it is not possible to find out

topological ordering of that graph so

that graph should not contain any cycle

not a single one fine that is must

condition now what is topological

sorting see topological sorting is

basically a linear ordering linear

ordering of the vertices in the graph

such that for every directed edge UV so

I see the edges from you to suppose u to

V vertex u to V then in the or brain you

must come before V fine I have written

the definition here for vertex u 2 V u

comes before vertex V in that ordering

we will discuss it with the example then

you will get it right and see one more

point is for every dag if graph is

directed in Si Si clique then at least

one topological sorting would be there

at least one but it is not compulsory

that that graph will have only one

topological sorting as

Telegraph can have more than one

topological sorting two three four five

six fine any number of topological

sorting now we'll discuss the method how

to find out topological sorting okay

discuss it with the help of one example

now suppose this one is our graph see

this is directed graph sorry this was

directed acyclic graph or not first of

all check it out this is directed yes

every edge is having some direction is

there any cycle directed cycle this this

no this is not coming like that this

no there is no cycle fine so topological

sorting or topological ordering on this

graph is possible now how to find out

topological sorting the first step is

very first step find out the in degree

of each vertex in the directed graph we

have the concept of in-degree and

out-degree fine in degree means the

number of edges coming to that word X

and how degree means the number of edges

outgoing from that vertex now find out

in degree of every vertex indicative of

this one is is there any edge which is

coming to one no there are two edges

which are outgoing from this one no I

just coming so in degree of this one is

zero in degree of this 2 is there is

only one edge that is coming one in

degree of this four is one and two edges

are coming to four to this edges like

this right in degree of this five is one

in degree of three is two edges are

coming to three one two now we have

finally found out the in degree of every

vertex by first step is this second step

is you will start by writing down the

topological ordering or you can say the

linear or drain from the vertex having

in degree 0 find you and choose that

vertex first that is having in degree 0

now find out which vertex is having in

degree 0 1 so we will

one okay

now second step is we have selected this

one fine

so from this graph we will delete this

one and all the edges which are outgoing

from this one every edge so from this

one how many edges are outgoing one into

fine so we will delete this one and we

will delete this this one also this one

and this one now when we delete these

edges then obviously the in degree of

these vertices would be changed

yes or no so the graph would be

something like that we have only two we

have four we have three we have fine

fine two to four still we have four to

three we have four to five we have this

edge no we are not having one this edge

we are not having this edge we have only

two to three now in degree of this two

will become what now you have to update

the in degree of these vertices in

degree of this two is now zero because

first it was one this edge was deleted

then it would be minus 1 1 minus 1 that

is 0 it would be 2 - 1 - 1 edges had has

been deleted now in degree of this 4s

only this edge 1 5 is as it is 3 is in

degrees - now we have this graph now

again select the vertex having in degree

0 which one is having in degree 0 2 will

write down to here next the same step we

will delete this too.we will delete and

will delete the every vertex out going

from this to this also and this also

fine and update the degree of these

vertices you are supposed to update that

what degree of those in degree of those

vertices which are being affected

because of because of deletion of this -

and these edges now the graph would be

is 2

has been deleted now we have only three

we have four we have five yes four to

five we have four to five million four

to three we have do we have this edge no

two has been deleted do we have this no

this has also been deleted we have only

two edges now now in degree of three

would become first of all it was 2 minus

1 that is 1 only for e 1 3 1 minus 1 is

because this one has been deleted so in

degree C you can see this there is no

issue in coming to that vertex that is 0

and here we have only one now again

select the vertex having in degree 0 we

have 4 write down this for the same step

4 would be deleted and also the outgoing

edges would be deleted now the graph

would be we have only vertex 3 and 5 now

these two edges has been deleted is

there any edge between these 3 and 5 no

in degree of this 3 is now 0 in degree

of this 5 is now zero now select again a

vertex having in degree 0

now see here we have 2 what this is

having in degree 0 3 & 5 so you can take

this 3 also and you can take 5

suppose we are taking this three now

three has been deleted now you can take

this 5 or the second ordering is

possible that is 1 2 4

yata cassity's and after that first of

all we will take this 5 and then we'll

take this 3 so 2 topological ordering of

topological ordering is possible off for

this graph alright we'll take one more

example suppose we have this kind of

graph 1 2 3

and 5c now find out the topological

ordering of this graph see the

topological ordering of this graphs

you'll not be able to find out why so

because this graph is having one

directed cycle see this then this then

this this is a cycle and we have already

discussed in these properties that if a

graph is having any cycle then you would

not be able to find topological ordering

for that graph so let us see is it

possible is it true or not same step

find out in degree of every vertex in

degree of 1 is 1 in degree of this 2 is

2 1 & 2 2 edges are coming to that

vertex 3 is 1 & 2 2 edges are coming for

5 in degree 0 for 4 in degree 0 select

the vertex having in degree 0 you can

select either 4 or 5 it's up to you

suppose we are selecting for case 1 is

this 4 or case to me you can select fine

that's why I have told you for a graph

directed acyclic graph many topological

ordering are possible we are taking this

case suppose we have choosen this for

now after choosing this for delete this

4 and also this vertex now the graph

would be 1 2 3 this one this one and

this one now this one has been deleted

but we have this 5 now in degree of this

5 is same in degree of 3 is still two in

degree of 1 is still 1 but in degree of

2 is now 1 la too--they this has been

deleted then 2 minus 1 that is 1 C 1

edge now again select a vertex I mean

degree 0 we have 5 suppose we have taken

this 5 now delete this 5 and this edge

now the graph would be 1 2 & 3 this one

this one and this one now 5 has been

deleted

now put 8 the in degree of every vertex

1 1

and still 2-1 deleted my one now is

there any vertex having in degree zero

no every vertex is having degree one one

one so we cannot proceed further that is

why I am saying if a graph contains a

cycle then it would not be possible to

find out topological ordering because if

graph contains a cycle then at some

point you will do it you will reach

tonight some situations then at that

time you will not have any vertex you

will not find any vertex having in

degree zero okay so that is the case you

can take one more example suppose we are

having this kind of graph now we are

supposed to find out topological sorting

of this graph find out first step in

degree of every vertex in degree of is

zero no I just coming in degree of D is

one two three in degree of C is zero in

degree of D is one to select a vertex

having in degree zero you can select

either C or you can select hey so case

one is we have selected a and suppose

case two we have selected C now

case one we have selected a now after

selection of a these would be deleted

okay and the graph would be something

like that we have B we have C we have D

this one this one and this one and these

edges has been related and update the in

degree of every vertex sorry or you can

see the update in degree of vertex which

are being affected because of this

deletion in degree of B now become 2 and

B become 1 and C in degrees 0 now select

a vertex having in degree 0 we have only

C has been selected delayed this delayed

this fine after deletion of Bees edges

in degree of D would become 0 and in

degree of B would become 1 then we would

select in degree zero vertex having in

degree 0 that is d after

the selection of did this edge is also

be deleted then we'll select right or

the next case was suppose you have

selected this C then delete this and

this and the graph would be a b and b we

are having this edge we are having this

edge we are having this one update in

degree this is having zero same this

will be having to 3 minus 1 this will be

having 1 now we will select a because in

vertex a is having in degree 0

now delete this this one and this one

you have selected this a nor delete the

outgoing edges of the say also and this

vertex also now in degree of this would

be updated to 0 after this deletion by

an integral of this B would be updated

to 1 now you can select after that you

can select B and you can select now D so

these are 2 topological ordering

possible of this graph right so for

every directed acyclic graph more than

one topological ordering is possible

okay I'll say in the next video

till then bye bye take care