Transitive closure of a Graph (Reachability Matrix)

Find transitive closure of the given graph. It is the Reachability matrix.

[@AnnoyedUnicorn]

I'm a French student the day before my exam, and thank you very much for this video ;)

[@coconut1010]

Pareil c est fou, ya peu de contenu en français sur ça

[@AnnoyedUnicorn]

Oh I failed it btw, but still ^^

[@aniketbhoite7168]

@@AnnoyedUnicorn ohhh you still came back after a year .....😅

[@subhranil_mukherjee]

sir i don't think in a directed graph each vertex is obviously reachable to itself. i think what it means is "starting from a vertex v, can we get back to v following any path in the graph?". Let me know your thoughts.

[@sanjeewanigunasekara4304]

I think you are correct.

[@AnnoyedUnicorn]

With the methode I learned with my math professor, we addition to the identity Matrix, so obviously, he is right ;)

[@matthewstruble8881]

of course not, but that's not what the graph is saying. think, if we knew that [2,1] is a path, then of course [2,1] -> [1,1] is also a valid way to reach node 1. if the matrix is not made this way the algorithm will fail

[@missakasms]

Yes u are correct i guess

[@cicakmuhamed]

You're right. Otherwise, the diagonal from left-to-right would always be filled with 1's in the transitive closure and that would not convey much useful information. Also, in the video, you cannot reach A starting from A (there exists no path, at 1:10) but he marked it as 1 in the transitive closure, which means he actually meant that "it is obvious every vertex can reach itself".

[@craigruchman7007]

My text book mentions transitive closure but did not give an example. Thanks so much for the clear example. Question: Closure is when we perform said operations on ALL vertices without adding any new elements to our set. Yes? Also, the edges don’t alow paths in both directions. So this makes it non-commutative. If they were bi-directional, it would be commutative - yes?

[@Tyokok]

thanks for the video! quick Question: is diagonal always 1? meaning any vertex can reach itself? it doesn't need a self-circle edge? i thought without self-circle edge self reach=0.

[@vibranteye4369]

I learned it this way as well...

[@Tyokok]

@@vibranteye4369 what you mean? can you make it clear please? So it should 0 or 1, and the meaning of each? Thanks a lot!

[@manognadevineni8901]

Noo here if we start from say a.. we will get back to a ; So here we'll take diagonal as 1.. i.e. if we do have a closed path for any vertex we can take its diagonal one as 1 or else 0 ..

[@Tyokok]

@@manognadevineni8901 so you saying regardless we have self-circle edge, we always set diagonal to 1, like convention ?

[@manognadevineni8901]

@@Tyokok if a node has a self circle then its quite good it will be having 1 in its diagonal...but here look into the question if we start from 1 we will get back to 1.. that means a path exsits .. so we will take it as 1 .

[@jongmagee]

Big help again, thank you!

[@dulamshiva5340]

sir can you please explain how A will reach to A again in the adjacent matrix...i feel their is a flaw in solution

[@revanth6476]

we can also use bfs right..?

[@pg9227]

sir your videos on graph theory is good and no doubt everybody can easily understand. sir i am requesting you please make videos on graph coloring ,vertex coloring,np completeness and linear programming in graph theory. I am eagerly waiting for response. Thanking you sir

[@mayurwarpe2763]

Great sir...you have clear my doubt Please make video on DFS algorithm

[@joepaul9475]

thank you. very useful

[@tomsonthomas7658]

In a digraph D, prove that a vertex y is reachable from a vertex x if and only if D contains an (x, y)− path. 2. Show that a digraph D is strong if every vertex of V (D) is reachable from every vertex other vertex of V (D). 3. Show that a digraph D is strong if and only if it has a closed Hamilton walk. 4. Develop a strong digraph D = (V, A) and extract possible separator from D.

[@abdultamim1428]

Thank you, sir; it was great. Please send me some material about(Transit function and betweenness) if you have any!

[@SOURABHGOLCHHABCE]

sir can u upload more questions on dynamic programming for interview purpose and sir upload daily one algorithm please sir i request you you should daily upload one algorithm please sir

[@madanagopal5585]

Today my xm this is video is very helpful ❤️

[@balasrinivas7517]

please teach particle swarm algorithm

[@tekbssync5727]

please provide the code for this Qs.

[@Shree_krishna77]

Thank you sir ❤❤❤❤

[@hashcodez757]

thanks alot sir!!

[@arifulislamhabib2937]

Thank You.

[@JananiAnbarasan]

Sir, please explain TSP!

[@rohansodhi4713]

There is no path from A to A So how did you write the path from A to A?

[@gangireddyakula6395]

Ossm sir I'm easily understand to see ur videos 🥰TQ u so much sir

[@tayebdz8581]

thank you

[@ManiTeluguGamer23]

Tqu so much sir

[@mt03adventures]

Ty

[@Rexxxxaaa12]

i think the diagonals should be 0 as there is no selfloop

[@masakkali9996]

Is the transitive closure of this graph is correct??

[@pavlos.konstantinidis]

nope

[@tazelhossan2838]

Wrong teaching. There is no path for node a. Please check it Again.

[@bwbs7410]

this is wrong. First, this isn't how the algorithm to obtain the transitive matrix is preformed. Second, a path from A to A signifies a looped edge. Thus, all values on the main diagonal [top left corner to bottom right corner] should all be zero because this graph has no looping edges.

[@Anime_Animation_Illustration]

You are talking about Adjacent matrix 😅

[@jethanpaul818]

you're confusing between adjacent matrix representation of a graph and transitive closure , get a book cormen to be specific and see the algorithm on transitive closure maybe you can understand that he is correct.

[@samudralashanmukrao2185]

How can reach form a to a 🤔

[@shubhamshejaval8526]

Same doubt bro

[@Anime_Animation_Illustration]

Because it is same node re

[@tauchainagoras6044]

check this out.. shortest code ever

[@setYourHandleHttp404]

7 minutes for only describing a matrix!!! I thought you are also describing the Floyd-Warshall algorithm.

[@venkyg6745]

A to C there is no path ..

[@52_sopansharma52]

galat padha rh ho

[@nitinsingh9604]

Jake khud padh le pahele

[@gokuljs837]

Teach properly

[@ossamabinhassanietstudent3418]

Abey chutiye.... Loop kahan dikhaaya gaya hai Harr vertex Pai