| by Kenneth Chase | 91 comments

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.

91 Comments

param bole

Sep 9, 2014, 1:26 pm Reply

Simply amazing

Niraj Shah

Sep 9, 2014, 2:34 pm Reply

Perfect..just perfect. Can't wait for other videos

erol yeniaras

Sep 9, 2014, 3:37 pm Reply

You are the best!

Suresh Dharavath

Sep 9, 2014, 5:31 pm Reply

In 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 pm Reply

When 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 pm Reply

GOod job

SandyOC100

Sep 9, 2014, 9:43 pm Reply

I 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 pm Reply

Please 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 am Reply

hi 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 Reply

@Animesh Nayan Sent an email to mycodeschool via gmail please read 🙂

Shubham Mohanka

Sep 9, 2014, 12:58 pm Reply

just keep on the good work dude.ur tutorials are d best 🙂

zakariae bruxelles

Sep 9, 2014, 9:11 pm Reply

thank you i hope that you can continue to the advanced courses in graph

Shashwat Srivastav

Sep 9, 2014, 10:34 pm Reply

SIR,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 pm Reply

awesome.. 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 pm Reply

i'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 pm Reply

Really 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 pm Reply

when are we having the next graph videos? 🙂 it would be nice to learn the implementation of it!

Nour

Oct 10, 2014, 10:53 pm Reply

Hi sir, don't you have a plan to make lessons on Heap sorting ?

Ankur

Oct 10, 2014, 5:24 pm Reply

give me more

shainesh baheti

Oct 10, 2014, 7:08 am Reply

why 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 pm Reply

your tutorials are d best ever…keep uploading new videos..Good Luck..!!

Mansi Tiwari

Nov 11, 2014, 3:41 pm Reply

are you planning to do any videos on hashing? it would be really nice to have them.

Kelly Shaw

Nov 11, 2014, 3:07 am Reply

Great 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 pm Reply

Which writing pad do you use for your tutorials? 🙂

karthik sirimulla

Nov 11, 2014, 2:33 am Reply

Is 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 pm Reply

ur 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 pm Reply

I 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 am Reply

These videos on data structures are pretty good. thumbs up

john smith

Dec 12, 2014, 3:03 am Reply

graphs 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 pm Reply

you'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 am Reply

Are 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 am Reply

please 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 pm Reply

are 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 am Reply

I 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 am Reply

Many thanks for uploading these treasuries videos. Please try to complete Graphs.

Abdullah Aghazadah

Jan 1, 2015, 4:52 am Reply

Great explanation, thanks for making this series.

Khaled Chikh

Feb 2, 2015, 11:43 pm Reply

Fantastic

Manikandan Kbk

Jul 7, 2015, 3:06 am Reply

Two Words–>Thank You!!!

Gullu Studios

Aug 8, 2015, 1:36 pm Reply

while(1)
{
cout<<Thank you so much Sir;
}

sameer mahabole

Sep 9, 2015, 11:26 am Reply

This 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 pm Reply

The 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 am Reply

You 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 am Reply

Excellent explanation.

Dharan Doshi

Dec 12, 2015, 8:24 am Reply

You Are Absolutely Perfect At This !!

Wish You :

while(1)
{
Your_Subscribers++;
}

Jedidiah Avelino

Jan 1, 2016, 3:11 am Reply

this 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 am Reply

Should 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 am Reply

sir
i need tutorials of algorithm course for next semester
can you please help?

HARPREET SINGH

May 5, 2016, 4:07 am Reply

Thanks for excellent explanation.

Jagamohan Samal

May 5, 2016, 3:16 pm Reply

sir ur explanation is superbbb
do you videos on java??

Sonnix Jackson

Jun 6, 2016, 12:13 am Reply

Congratulations sir. How can i get your contact?

Shepherd Yannis

Aug 8, 2016, 9:19 pm Reply

There is subtitle, pretty considerate.

binay Singh

Nov 11, 2016, 3:34 pm Reply

thank 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 am Reply

can anyone tell me how these type of tutorial videos are made?

The Soundtrack Source

Dec 12, 2016, 1:09 pm Reply

Excellent video! Very informative

Hüseyin İYİBAŞ

Dec 12, 2016, 9:25 pm Reply

9:44 ?

מתן איבס

Apr 4, 2017, 6:47 pm Reply

great video!

RAKESH RAY

May 5, 2017, 5:43 am Reply

good,very nice

Saivarshini Ravi

Jun 6, 2017, 12:45 pm Reply

Such 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 pm Reply

I am not clear when does an edge is repeated and when vertex are repeated?

Ajay Sabarish

Jun 6, 2017, 4:55 pm Reply

sir,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 pm Reply

Keep up the good work sir, ur awesome!

Anil Kumar

Jul 7, 2017, 2:13 am Reply

Good.

saptarshi sengupta

Aug 8, 2017, 6:22 am Reply

These 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 am Reply

Hello, 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 pm Reply

Happy teacher's day.😀

Shreyash Patil

Oct 10, 2017, 6:24 am Reply

Nice video….

Bryan Truong

Nov 11, 2017, 9:34 pm Reply

you are a hero

Michael

Nov 11, 2017, 12:42 am Reply

You're an amazing teacher.

dudekula afreen

Nov 11, 2017, 7:35 am Reply

I need a vedio on radix sort plzzzzzzzz

Leon Van Les

Nov 11, 2017, 8:57 pm Reply

Perfect explanation, helped a lot

Pritha Majumder

Dec 12, 2017, 4:07 pm Reply

Awesome

shafaat jamil rokon

Dec 12, 2017, 1:18 pm Reply

Love from Bangladesh

Mohamed Moustafa

Dec 12, 2017, 2:36 pm Reply

Where graph traversal (BFS, DFS) ?

Nikhil Ghodke

Feb 2, 2018, 1:39 pm Reply

You 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 am Reply

explanation is good keep going on sir

Eyal Pery

Apr 4, 2018, 5:27 pm Reply

Genious

Salwa Aldrsi

Apr 4, 2018, 6:32 pm Reply

amazing explanation.

Prashanthi Kuchana

May 5, 2018, 7:15 am Reply

This is so clear!! Thanks a ton for these videos

Frederic Cartier

May 5, 2018, 4:08 am Reply

A 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 pm Reply

your site is not working, it is showing 502 error.

Usama Iftikhar Butt

Aug 8, 2018, 3:02 pm Reply

thank u bro for such an amazing concepts

Rahul Gupta

Aug 8, 2018, 3:44 pm Reply

the 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 pm Reply

dat dag doe

Khalifani Diliku

Sep 9, 2018, 7:33 am Reply

nice explaination i like it

buttegowda

Oct 10, 2018, 3:02 pm Reply

Excellent 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 am Reply

just 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 am Reply

at 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 pm Reply

Great 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 pm Reply

WTF 1 minute unsinkable add.

nucatm

Feb 2, 2019, 6:16 pm Reply

Very good. Thanks!

Pooja D

Mar 3, 2019, 4:28 am Reply

Worth to watch it, I wasted my 2 hours to search about graph theory then finally found your video, really helpful..thanks a lot..🙏

Leave a Reply