## Data structures: Properties of Graphs

In our previous lesson, we introduced you

to graphs. We defined graph as a mathematical or

logical model and talked about some of the

properties and applications of graph. Now in this lesson, we will discuss some

more properties of graph but first I want to do a quick recap of

what we have discussed in our previous lesson. A graph can be defined as an ordered

pair of a set of vertices and a set of edges. We use this formal mathematical

notation G=(V,E) to define a graph, here V is set of

vertices and E is set of edges. Ordered pair is just a

pair of mathematical objects in which order of objects in the pair matters. It

matters which element is first and which element is second in the pair. Now as we know to denote number of

elements in a set that we also call cardinality of a set.

We use the same notation that we used for modulus or absolute value. So this is how we can denote number of

vertices and number of edges in a graph. Number of vertices would be number of elements in set V

and number of edges would be number of elements in set E. Moving forward, this is how I’m

going to denote number of vertices and number of edges in all my explanations. Now as we had

discussed earlier, edges in a graph can either be

directed that is 1 way connections or undirected that is 2 way

connections. A graph with only directed edges is called a directed graph or digraph and a

graph with only undirected edges is called a undirected graph. Now sometimes all connections in a

graph cannot be treated as equal, so we label edges with some weight or cost like what i’m showing here and

a graph in which some value is associated to connections as cost or weight is called a weighted graph. A graph is unweighted if there is no cost distinction among edges. Okay, now we can

also have some special kind of edges in a graph. These edges complicate algorithms and

make working with graphs difficult but I’m going to talk about them anyway.

An edge is called a self loop or self edge if it involves only 1

vertex. If both endpoint of an edge are same then it’s called a self loop. We can

have a self loop in both directed and undirected graphs but the question is why would we

ever have a self loop in a graph. Well, sometimes if edges are depicting

some relationship or connection that’s possible with the same node as

origin as well as destination then we can have a self loop. For example

as we discussed in our previous lesson, interlinked web pages on the internet

or the world wide web can be it presented as a directed graph. A page

with a unique URL can be a node in the graph and we can have a directed edge if a page contains link to another

page. Now we can have a self loop in this graph

because its very much possible for a webpage to have a link to itself. Have a look

at this webpage mycodeschool.com/videos. In the header, we have links for workouts

page, problems page and videos page.

Right now I’m already on videos page but I can still click on videos link and

all that will happen with the click is refresh because I’m already on videos page. My

origin and destination are same here, so if I’m representing

world wide web as a directed graph the way we just discussed then we have

self loop here. Now the next special type of edge that

I want to talk about is multi-edge. An edge is called a multi-edge if it occurs more than once in a graph.

Once again, we can have a multi-edge in both directed and undirected graphs. First multi edge that I’m showing you here

is undirected and the second 1 is directed. Now once again, the question why should

be ever have a multi-edge. Well, let’s say we are representing flight

network between cities as a graph. A city would be a node and we can have

an edge if there is a direct flight connection

between any 2 cities, but then there can be multiple flights

between a pair of cities. These flights would have different names

and may have different costs. If I want to keep the information about

all the flights in my graph, I can draw multi-edges. I can draw 1

directed edge for each flight and then I can label an edge

with its cost or any other property. I just labeled edges here with some

random flight numbers. Now as we were saying earlier, self loops

and multi-edges often complicate working with graph. Their

presence means we need to take extra care while solving

problems. If a graph contains no self loops or multi-edge

then it’s called a simple graph. In our lessons, we will mostly be dealing

with simple graphs. Now I want you to answer a very simple

question. Given a number of vertices in a simple graphs that is a a graph

with no self loops or multi-edge, what would be maximum possible number of

edges. Well, let’s see. Let’s say, we want to draw

a directed graph with 4 vertices. I have drawn 4

vertices here. I’ll name these vertices V1, V2, V3

and V4. So this is my set of vertices. Number

of elements in set V is 4. Now it’s perfectly fine if I

choose not to draw any age here. This will still

be a graph. Set of edges can be empty, nodes can be

totally disconnected. So minimum possible number of edges in a

graph is zero. Now if this is a directed graph, what do

you think can be maximum number of edges here. Well, each node can have directed edges

to all other nodes. In this figure here, each node can have

directed edges to 3 other nodes. We have 4 nodes in

total, so maximum possible number of edges here

is 4 * 3 that is 12. I have shown

edges originating from a vertex in same color here. This is the maximum that we can draw if

there is no self loop or multi-edges. In general if there are N

vertices then maximum number of edges in a

directed graph would be N * (N – 1), so in a simple directed graph of number of edges would be

in this range 0 to N * (N-1). Now what do

you think would be the maximum for an undirected graphs. In an undirected graph, we can have only

1 bi-directional edge between a pair of nodes. We can’t

have 2 edges in different directions, so here the maximum would be half of

maximum for directed. So if the graph is simple and undirected

number of edges would be in the range 0 to (N * (N – 1)) / 2. Remember this is true only if there is

no self loop or multi-edge. Now if you can see number of edges in

the graph can be really really large compared to a number of vertices. For example if number of vertices in a

directed graph is equal to 10, maximum number of edges

would be 90. If number of vertices is 100, maximum number of edges would be 9900. Maximum number of edges would be close

to Square of number of vertices. A graph is called dense if number of

edges in the graph is close to maximum possible number of edges that is if the number of edges is of

order of square of number of vertices, and a graph is called sparse if the

number of edges is really less typically close to a number of

vertices and not more than that. There is no defined boundary for what

can be called dense and what can be called sparse. It all depends on context but this is an important classification.

While working with graphs, a lot of decisions are made based on

whether the graph is dense or sparse. For example we

typically choose a different kind of storage structure in computer’s memory

for a dense graph. We typically store a dense graphs and

something called adjacency matrix, and for a sparse graph we typically use

something called adjacency list. I’ll be talking about

adjacency matrix and adjacency list in next lesson. Okay, now the next concept

that I want to talk about is concept of path in a graph. A path in a graph is a sequence of vertices where each

adjacent pair in the sequence is connected by an

edge. I’m highlighting the path here in this

example graph. This sequence of vertices A B F and H is a path in this graph. Now we have an undirected graph here,

edges are bi-directional. In a directed graph, all edges must also

be aligned in 1 direction the direction of the

path. A path is called simple path if no vertices

are repeated and if vertices are not repeated

then edges will also not be repeated. So in a simple path both vertices and

edges are not repeated. This path A B F H that I have highlighted

here is a simple path but we could also have

a path like this. Here, start vertex is A and end vertex is D. In this path, 1 edge and 2 vertices are repeated. In graph theory, there is some inconsistency

in use of this term path. Most of the time, when we say path

we mean a simple path and if repetition is possible we used

this term walk. So a path is basically a walk in which no vertices or edges are repeated. A walk is called a trail if

vertices can be repeated but edges cannot be repeated. I’m highlighting

a trail here in this example graph. Okay, now I want to say this once again

walk and path are often used as synonyms but most

often when we say path we mean simple path, a path in which

vertices and edges are not repeated. Between 2 different

vertices if there is a walk in which vertices or edges

are repeated like this walk that I’am showing you here in

this example graph then there must also be a path or simple

path that is a walk in which vertices or

edges would not be repeated. In this walk that

I’m showing you here, we’re starting at A and we are ending our walk at C. There is a simple path from A to C

with just 1 edge. All we need to do is, we need to avoid

going to B E H D and then coming back again to A. So

this is why we mostly talk about simple path between 2 vertices because if any other walk is possible

simple path is also possible and it makes most sense to look for a

simple path so this is what I’m going to do

throughout our lessons. I’m going to say path and by path, I’ll mean simple path and if it’s not a simple path I’ll say it

explicitly. A graph is called strongly connected if

in the graph there is a path from any vertex to any

other vertex. If it’s an undirected graphs, we simply

call it connected and if it’s a directed graph, we call it

strongly connected. In leftmost and rightmost graphs that I’m

showing you here, we have a path from any vertex to any

other vertex but in this graph in the middle, we do

not have a path from any vertex to any other vertex. We cannot

go from vertex C to A. We can go from A to C but we

cannot go from C to A, So this is not a strongly

connected graph. Remember if it’s an undirected graph, we

simply say connected and if it’s a directed graph we say a strongly

connected. If a directed graph is not strongly connected but can be turned into connected

graph by treating all edges as undirected then such a directed graph is called

weakly connected. If we just ignore the directions of

edges here, this is connected but I would recommend that you just

remember connected and strongly connected. This leftmost undirected graph is connected. I removed 1 of the edges and now this

is not connected. Now we have 2 disjoint connected

components here but the graph overall is not

connected. Connectedness of a graph is are really

important property. If you remember, intracity road

network with a city that would have a lot of 1 ways can

be present as a directed graph. Now an intra-city road network should

always be strongly connected. We should be able to reach any street

from any street, any intersection to any intersection.

Okay, now that we understand concept of path. Next, I want to talk about cycle in a

graph. A walk is called a closed walk if it starts an ends at same vertex like what i’m showing here and there is 1

more condition, the length of the walk must be

greater than 0. Length of a walk or path is number of edges

in the path like for this closed walk that I’m showing

you here. length is 5 because we have 5 edges

in this walk. So a closed walk is a walk that starts

and ends at same vertex and the length of which is greater than

0. Now some may call closed walk a cycle but generally we used

the term cycle for a simple cycle. A simple cycle is a close walk in which other than start

and end vertices no other vertex or

edge is repeated. Right now, what I’m showing

you here in this example graphs is a simple cycle or we can just say cycle. A graph with no cycle is called an

acyclic graph. A tree if drawn with undirected edges would

be an example of and undirected acyclic graphs. Here

in this tree, we can have a closed walk but we

cannot have a simple cycle. In this closed walk that I’m showing you

here, our edge is repeated. There would be no simple cycle in a tree

and apart from tree, we can have other kind of undirected

acyclic graphs also. A tree also has to be connected. Now we

can also have a directed acyclic graph, as you can see here also we do not have

any cycle. You cannot have a path of lenght greater

than 0 starting and ending at the same vertex. A directed cyclic graph is often

called a DAG. A cycles in a graph cause a lot of

issues in designing algorithms for

problems like finding shortest route from 1 vertex to another and we will talk about cycles a lot when

we will study some of these advanced algorithm in coming lessons. For this lesson, I’ll stop here now.

In our next lesson, we will discuss ways of creating and storing graph in

computers memory. This is it for this lesson. Thanks for

watching.

## param bole

Sep 9, 2014, 1:26 pmSimply amazing

## Niraj Shah

Sep 9, 2014, 2:34 pmPerfect..just perfect. Can't wait for other videos

## erol yeniaras

Sep 9, 2014, 3:37 pmYou are the best!

## Suresh Dharavath

Sep 9, 2014, 5:31 pmIn sparse graph whether the number edges can be less than the number of vertices?( like an edge with two vertices )

## Som Pathak

Sep 9, 2014, 5:33 pmWhen you are good at something you should always do it for free !!!!! and you are perfect …Great Video!!!!

how much time would you take to complete graphs

## Charvak Patel

Sep 9, 2014, 6:11 pmGOod job

## SandyOC100

Sep 9, 2014, 9:43 pmI love your videos dude! You always seem to know exactly what i'm doing in my course and upload your videos precisely when i need them. Best presentation on YouTube by far.

## v9

Sep 9, 2014, 6:32 pmPlease do some videos on DP. How to think in terms of overlapping sub problems and optimal sub structure.

How to build intuition of the solution

## ganesh raj

Sep 9, 2014, 6:14 amhi sir .firstly,i like to congratulate on the video series.you are too good in explaining difficult concepts.

i like to have your suggestion on DATA STRUCTURE BOOKS.

please suggest books fr

for beginners and

intermediate.

thanks in advance .

## Roy Mor

Sep 9, 2014, 8:04 pm@Animesh Nayan Sent an email to mycodeschool via gmail please read 🙂

## Shubham Mohanka

Sep 9, 2014, 12:58 pmjust keep on the good work dude.ur tutorials are d best 🙂

## zakariae bruxelles

Sep 9, 2014, 9:11 pmthank you i hope that you can continue to the advanced courses in graph

## Shashwat Srivastav

Sep 9, 2014, 10:34 pmSIR,U TEACH THE BEST THROUGH YOUR VIDEOS ..BUT AFTER BINARY TREES WHY U DIDN'T COVER SORTING TECHNIQUES LIKE HEAP SORT, SHELL SORT..THEY ARE ALSO HARD TO UNDERSTAND AND RELATED TO TREES IN SOME WAY ….WILL THEY COME AFTER GRAPHS??

…..

waiting for response curiously!!

## Ankur

Sep 9, 2014, 4:12 pmawesome.. waiting for more on graphs with clear implementation details..because that's where graphs are headache for me

## zakariae bruxelles

Oct 10, 2014, 4:19 pmi'm still waitinf for your new videos for this data structure i hope that you can explain how to represent the graph in memory especially with the Adjacency array(not the matrix Adjacency )

## Sebastian Kunju

Oct 10, 2014, 4:09 pmReally good explanation. Is there any plan to put more videos on graph? If so, when can we expect?

## Mario Salomon

Oct 10, 2014, 4:55 pmwhen are we having the next graph videos? 🙂 it would be nice to learn the implementation of it!

## Nour

Oct 10, 2014, 10:53 pmHi sir, don't you have a plan to make lessons on Heap sorting ?

## Ankur

Oct 10, 2014, 5:24 pmgive me more

## shainesh baheti

Oct 10, 2014, 7:08 amwhy you stopped graph here…please teach…DFS,BFS adjacency list and matrix..problems on strongly connected..graph…I have learnt all the DS and algorithm from your videos only…all videos rock!!..

## CHANDAN H S

Nov 11, 2014, 7:53 pmyour tutorials are d best ever…keep uploading new videos..Good Luck..!!

## Mansi Tiwari

Nov 11, 2014, 3:41 pmare you planning to do any videos on hashing? it would be really nice to have them.

## Kelly Shaw

Nov 11, 2014, 3:07 amGreat video series! It just so happens that I am currently working on a graph CV++ project now and could really use the next video in the series right now!

## Sri Ram

Nov 11, 2014, 6:50 pmWhich writing pad do you use for your tutorials? 🙂

## karthik sirimulla

Nov 11, 2014, 2:33 amIs there a next lesson after this on Graphs ??

I was not able to find the next lesson ….Plz help !!!

## ullekh niraula

Nov 11, 2014, 7:57 pmur really good at what you do.. seriosly, everything I have learned in data structure this semester is from your tutorials. thanks man.

## Vaibhav Chauhan

Dec 12, 2014, 7:54 pmI have tried many books and video lectures for DS and ADA; MIT, Skiena, Coursera[Tim Roughgarden] and what not, nothing worked for me, I was a bit too casual in learning then and those videos couldn't keep me interested.

Somehow I found your series and have seen a lot of your playlists and will finish all soon. You sir are a brilliant teacher, perfect in teaching the basic concept, then telling how to improve, limits, edge cases, comparisons with other techniques, videos are neither too long nor too short, and you have even shown us step by step implementation in C/C++. That is just marvelous, I read your blog posts and Quora, and would like to thank you for such an amazing effort for the students and other learners like us. I know you must be very busy with your professional life too but please continue this series whenever you can take out time. 🙂

Thank you once again!

## Gurpreet Mohaar

Dec 12, 2014, 5:17 amThese videos on data structures are pretty good. thumbs up

## john smith

Dec 12, 2014, 3:03 amgraphs are [email protected][email protected][email protected] i hope you continue with this series. you are good teacher

## Shubham Singh

Dec 12, 2014, 1:44 pmyou're doing a great job..all videos are simply awesome..

books gives us a lot of confusion but when you see it practically , graphically than it looks much easier to grasp thing..excellent and keep it up !!

## Python Ruby

Dec 12, 2014, 3:13 amAre you going to update the series?I hope you continue doing it,because your tutorial is so great!

## varnit saini

Dec 12, 2014, 6:43 amplease update your series . I am hungry for more .BTW too good and thanks for uploading such treasure .Looking for more videos soon

## Ivan Rei

Dec 12, 2014, 6:53 pmare you not continuing the video? 🙁 your way of teaching is really one of a kind btw.. really made my life easier. you should make it more complete, maybe make it commercial if that helps (something like CBTNuggets)

## Sean Yang

Jan 1, 2015, 2:34 amI really like your videos, please continue making them! BTW, can you cover heap in data structure as well?

## Fargham Ahmad

Jan 1, 2015, 4:14 amMany thanks for uploading these treasuries videos. Please try to complete Graphs.

## Abdullah Aghazadah

Jan 1, 2015, 4:52 amGreat explanation, thanks for making this series.

## Khaled Chikh

Feb 2, 2015, 11:43 pmFantastic

## Manikandan Kbk

Jul 7, 2015, 3:06 amTwo Words–>Thank You!!!

## Gullu Studios

Aug 8, 2015, 1:36 pmwhile(1)

{

cout<<Thank you so much Sir;

}

## sameer mahabole

Sep 9, 2015, 11:26 amThis is by far the best video series I have found on this topic. You're concepts are strong and the way you explain in excellent. Most of the vids on graph theory (even the shorter ones ~ 6 – 15 mins) tend to be boring, but not yours. Please complete the series, you will get a lot of subscribers (in other words, even if you may not be doing this for money, you may earn from your vids here).

## Matthew Powers

Sep 9, 2015, 4:23 pmThe explanations in this video are fantastic. You have a gift for explaining computer science topics clearly. Thank you.

## Aditya Sinha

Oct 10, 2015, 10:03 amYou have a way of explaining things very neatly. Thank you so much and keep up the good work.

## Biranchi Narayan Nayak

Nov 11, 2015, 5:10 amExcellent explanation.

## Dharan Doshi

Dec 12, 2015, 8:24 amYou Are Absolutely Perfect At This !!

Wish You :

while(1)

{

Your_Subscribers++;

}

## Jedidiah Avelino

Jan 1, 2016, 3:11 amthis question is beyond the topic but i'll ask anyway, did you build your site? in the case that you built it, is there any chance that you could make a tutorial on how to integrate a pagination/page module such as that in your website? also, did you use some kind of a javascript plugin?

## Abhishek Kaukuntla

Jan 1, 2016, 5:38 amShould I thank youtube because of which these videos are available or mycodeschool for posting these because there's youtube?

The voice, appropriate usage of the examples and the speed of the explanation makes such an imprint in your brain that it's very easy not to forget these concepts later on.

## sanjay ranjan

Apr 4, 2016, 9:26 amsir

i need tutorials of algorithm course for next semester

can you please help?

## HARPREET SINGH

May 5, 2016, 4:07 amThanks for excellent explanation.

## Jagamohan Samal

May 5, 2016, 3:16 pmsir ur explanation is superbbb

do you videos on java??

## Sonnix Jackson

Jun 6, 2016, 12:13 amCongratulations sir. How can i get your contact?

## Shepherd Yannis

Aug 8, 2016, 9:19 pmThere is subtitle, pretty considerate.

## binay Singh

Nov 11, 2016, 3:34 pmthank you so much sir for all the data structure videos … your videos are best to very easiy understandable..

## Ashutosh Raghuwanshi

Dec 12, 2016, 7:37 amcan anyone tell me how these type of tutorial videos are made?

## The Soundtrack Source

Dec 12, 2016, 1:09 pmExcellent video! Very informative

## Hüseyin İYİBAŞ

Dec 12, 2016, 9:25 pm9:44 ?

## מתן איבס

Apr 4, 2017, 6:47 pmgreat video!

## RAKESH RAY

May 5, 2017, 5:43 amgood,very nice

## Saivarshini Ravi

Jun 6, 2017, 12:45 pmSuch a great video. Would be great if you can cover heaps in data structures as well,

## Ahmed Abdul Fatah Ahmed Alhaj

Jun 6, 2017, 7:03 pmI am not clear when does an edge is repeated and when vertex are repeated?

## Ajay Sabarish

Jun 6, 2017, 4:55 pmsir,your videos are excellent,though there are many such videos,but none can compete with yours in clarity and simplicity,you don't delve too much into the theory and explains it in simple language,with great examples. If teaching is an art,you are the raja ravi varma of it.

## Rahul Raj

Jul 7, 2017, 6:15 pmKeep up the good work sir, ur awesome!

## Anil Kumar

Jul 7, 2017, 2:13 amGood.

## saptarshi sengupta

Aug 8, 2017, 6:22 amThese videos are very good . But that Saurabh Shukla Shit keeps popping up. That's very annoying .. YouTube should block his channel …

## Frankie Lin

Aug 8, 2017, 5:59 amHello, the example you should on this video at 11:53 stated that the third graph is a strongly connected graph. However, the definition of SCG is "if there is a path from any vertex to any other vertex", and you said a path is a walk with no repetition of vertices and edges. However, the thid graph, let's say we want to find a path from A to B, We can go

A->D->B->D->B and there are repetitions of both vertices and edges. So I wonder why is that. Can someone explain?

## Milind Modi

Sep 9, 2017, 7:18 pmHappy teacher's day.😀

## Shreyash Patil

Oct 10, 2017, 6:24 amNice video….

## Bryan Truong

Nov 11, 2017, 9:34 pmyou are a hero

## Michael

Nov 11, 2017, 12:42 amYou're an amazing teacher.

## dudekula afreen

Nov 11, 2017, 7:35 amI need a vedio on radix sort plzzzzzzzz

## Leon Van Les

Nov 11, 2017, 8:57 pmPerfect explanation, helped a lot

## Pritha Majumder

Dec 12, 2017, 4:07 pmAwesome

## shafaat jamil rokon

Dec 12, 2017, 1:18 pmLove from Bangladesh

## Mohamed Moustafa

Dec 12, 2017, 2:36 pmWhere graph traversal (BFS, DFS) ?

## Nikhil Ghodke

Feb 2, 2018, 1:39 pmYou somehow confused me about connected ,strongly connected and that type of graphs u could have simplified it

Otherwise u are great teacher

Seriously

## Venkataswaralu Nandam

Mar 3, 2018, 4:38 amexplanation is good keep going on sir

## Eyal Pery

Apr 4, 2018, 5:27 pmGenious

## Salwa Aldrsi

Apr 4, 2018, 6:32 pmamazing explanation.

## Prashanthi Kuchana

May 5, 2018, 7:15 amThis is so clear!! Thanks a ton for these videos

## Frederic Cartier

May 5, 2018, 4:08 amA really good explanation with very clear graph and text. Thank you for the quality of your video. From now graphs are more clear and affordable than before.

## Amusing Tech

Jul 7, 2018, 4:52 pmyour site is not working, it is showing 502 error.

## Usama Iftikhar Butt

Aug 8, 2018, 3:02 pmthank u bro for such an amazing concepts

## Rahul Gupta

Aug 8, 2018, 3:44 pmthe self loop concept seems to be an illusion.. Even, in any act of 'get','fetch', we minimum need two coordinates with minimum two objects (one could be requester and second could be object itself) , Even in neural network of mind…

## Rakshit Sinha

Sep 9, 2018, 9:16 pmdat dag doe

## Khalifani Diliku

Sep 9, 2018, 7:33 amnice explaination i like it

## buttegowda

Oct 10, 2018, 3:02 pmExcellent clarity, very rare to see this . Thanks a lot. I have been struggling with graphs. You made it so simple

## Kumar .vivek

Dec 12, 2018, 4:25 amjust one word – Awesome . Please share the link of your videos on various DS problems , System design and Scalability that are asked in Interviews.

## Krupesh Anadkat

Dec 12, 2018, 9:38 amat 11:10 he meant any vertex to EVERY other vertex… in definition. Reply to this if i am wrong.

## Wilson Soethe Cursino

Dec 12, 2018, 12:25 pmGreat work, I am so glad that we have people like you that take the time and effort to provide ivy league college quality content for FREE. and for that we can not THANK YOU enough.

## 0xbad0dead

Feb 2, 2019, 5:41 pmWTF 1 minute unsinkable add.

## nucatm

Feb 2, 2019, 6:16 pmVery good. Thanks!

## Pooja D

Mar 3, 2019, 4:28 amWorth to watch it, I wasted my 2 hours to search about graph theory then finally found your video, really helpful..thanks a lot..🙏