Hello everyone. So far in the series on

data structures, we have talked about some of the linear

data structures like array, linked list, stack and queue. In all these

structure, data is arranged in a linear or sequential manner, so we can call

them linear data structures and we’ve also talked about tree which

is a non-linear data structure. Tree is a hierarchical structure. Now as

we understand data structures are ways to store and organize data, and for different kinds of data we use

different kinds of data structures. In this lesson, we’re going to introduce

you to another non linear data structure that has got its application in a wide

number of scenarios in computer science. It is used to model and represent a

variety of systems and this data structure is graph. When we study data structures, we often

first study them as mathematical or logical models. Here

also, we will first study graph as a

mathematical or logical model and we will go into implementation

details later. Okay so let’s get started. A graph just

like a tree is a collection of objects or entities that

we call nodes or vertices, connected to each

other through a set of edges. But in a tree connections are bound to be in a certain

way. In a tree that our rules dictating the connection among the nodes.

In a tree with N Nodes, we must have exactly N – 1 edges. One edge for each parent child relationship. As

we know an edge in a tree is for a parent child

relationship and all nodes in a tree except the root node would have apparent

would have exactly 1 parent and that’s why if they are N nodes, it

must be exactly N – 1 edges. In a tree, all nodes must be reachable

from the root and there must be exactly one possible

path from root to a node. Now in a graph there are no

rules dictating the connection among the nodes.

A graph contains a set of nodes and a set of edges and edges can be connecting nodes in any

possible way. Tree is only a special kind of graph.

Now graph as a concept has been studied

extensively in mathematics. If you have taken a course on discrete

mathematics then you must be knowing about graphs

already. In computer science, we basically study and implement the same concept

of graph from mathematics. The study of graph is often referred to

as graph theory. In pure mathematical terms we can define graph something like this. A graph G is in order pair of a set

V of vertices and a set E of edges. Now I’m using

some mathematical jargon here. An ordered pair is just a pair of

mathematical objects in which the order of objects in the pair matters. This is how we write and

represent an ordered pair, objects separated by comma put

within parenthesis. Now because the order here matters. We

can say that V is the first object in the pair and E

is the second object. An ordered pair A, B is not equal to B, A unless A and B are equal. In our definition of graph here, first

object in the pair must always be a set of vertices and

the second object must be a set of edges that’s why we are calling the pair

an ordered pair. We also have concept of unordered pair.

An unordered pair is simply a set of two elements. Order is

not important here. We write an unordered pair using curly

brackets or braces. Because the order is not important here,

unordered pair A, B is equal to B, A. It doesn’t matter

which object is first and which object is second. Okay coming back,

so a graph of is an ordered pair of a set of

vertices and a set of edges and G=(V,E) is a formal

mathematical notation that we use to define a graph. Now I

have a graph drawn here in the right. This graph is 8 vertices

and 10 edges. What I want to do is I want give some

names to these vertices because each node in a graph must

have some identification. It can be a name or it can be an index. I’m naming these vertices as V1, V2 V3, V4, V5 and so on, and this

naming is not indicative of any order. There is no 1st, 2nd and 3rd Node here. I could

give any name to any node. So my set of

vertices here is this. We have 8 elements in the

set V1, V2, V3, V4, V5, V6, V7 and V8. So this is my set of

vertices for this graph. Now what’s my set of edges. To answer

this we first need to know how to represent

an edge. An edge is uniquely identified by it’s

2 endpoints, so we can just write the names

of the two endpoint of an edge as a pair and it can be

a representation for the edge. But edges can be of two types. We can

have a directed edge in which connection is

one-way or we can have an undirected edge in

which connection is two way. In this example graph that I’m showing

here, edges are undirected but if you remember the tree that I had

shown earlier then we had directed edges in that tree.

With this directed edge that I’m showing you here, we are saying that there is link or path from vertex U to V but we cannot

assume a path from V to U. This connection is one way. For

a directed edge, one of the endpoints would be the

origin and other end point would be the destination and we draw the edge with an arrow head pointing towards the

destination. For our edge here, origin is U and

destination is V. A directed edge can be to represented as

an ordered pair, first element in the pair can be the

origin and second element can be the destination. So with this directed edge represented

as ordered pair (U,V), we have a path from U to V. If we want a path from V to U, when need

to draw another directed edge here with V as

origin and U as destination and this edge can be

the represented as ordered pair (V,U), the upper one here is (U,V) and the

below one is (V,U) and they are not same. Now if the edge is undirected, the

connection is 2 way and undirected edge can be

to represented as an unordered pair here because the edge is

bi directional origin and destination are not fixed. We

only need to know what two end points have been connected by the edge. So now that we know how to present edges,

we can write the set of edges for this example graph here. We have an undirected edge between V1

and V2 then we have 1 between V1 and V3 and

then be have V1 V4. This is really simple and just go ahead

and write all of them. So this is my set of edges. Typically in

a graph, all edges would either be directed or

undirected. It’s possible for a graph to have both

directed and undirected edges but we are not going to study such

graphs, we are only going to study graphs in which all edges would either be

directed or undirected. A graph with all directed

edges is called a directed graph or digraph and a graph with all undirected ages is

called an undirected graph. There is no special name for an

undirected graph. Usually, if the graph directed, we

explicitly say that it’s directed graph or digraph. So these are

two types of graphs. Directed graph or digraph in which edges are uni-directional or ordered pairs and undirected graph in which edges are

bi-directional or unordered pairs. Now many real-world

systems and problems can be modeled using a graph.

Graphs can be used to represent any collection of objects having some

kind of pairwise relationship. Let’s have a look

at some of the interesting examples. A social network like Facebook can be

represented as an undirected graph. A user would be a node in

the graph and if 2 user are friends, there

would be an edge connecting them. A real social network would have millions

and billions of nodes. I can show only few in my diagram here

because I’m short of space. Now social network is an undirected

graphs because friendship is a mutual relationship. If I’m your

friend, you are my friend too. So connections have to be 2 way. Now once

a system is modeled as a graph a lot of problems

can easily be solved by applying standard algorithms

in graph theory. Like here in this social network, let’s

say we want to do something like suggest friends to a user. Let’s say we

want to suggest some connections to Rama. One possible approach to do so can be

suggesting friends of friends who are not connected already. Rama has

3 friends, Ella, Bob and Katie and friends of 3 that are not connected to Rama

already can be suggested. There is no friend of

Ella which is not connected to Rama already. Bob however, has 3 friends Tom, Sam, and Lee that are not friends with Rama so

they can be suggested and katie has two friends Lee and Swati that are not connected to Rama.We have

counted Lee already, so in all we can suggest these for users

to Rama. Now even though we described this

problem in context of a social network. This is a standard graph problem. The

problem here in pure graph terms is finding all nodes

having lenght of shortest path from a given

node equal to 2. Standard algorithms can be applied to

solve this problem. We’ll talk about concepts like path in

a graph in some time. For now just know that the problem that

we just described in context of a social network is a standard graph

problem. Okay so a social network like Facebook

is an undirected graph Now let’s have a look at another example.

Interlinked web pages on the internet or the World

Wide Web can be represented as a directed graph.

A web page that would have a unique address or URL

would be a node in the graph and we can have a directed edge if a

page contains link to another page. Now once again, there are billions of pages

on the web but I can show only few here. The edges

in this graph are directed because that relationship is not mutual this

time. If page A has a link to page B then

it’s not necessary that page B will also have a link to page A. Let’s say one of the pages on

mycodeschool.com has a tutorial on graph and on this page I have put a link to Wikipedia article on

graph. Let’s assume that in this example

graph that I am showing you here. Page P is my mycodeschool tutorial

on graph with this address or URL

mycodeschool.com/videos/graph and lets say, page Q is the

Wikipedia article on graph with this URL Wikipedia/org/wiki/graph. Now on my page that is page P, I have put a link to the Wikipedia page on

graph. If you are on page P, you can click on

this link and go to page Q but Wikipedia has not reciprocated

to my favor by putting a link back to my page. So if you are on

page Q you cannot click on the link can

come to page P. Connection here is one way and that’s why we have

drawn a directed egde here. Okay now once again if we are able to

present web as a directed graph, we can apply

standard graph theory algorithms to solve problems and to perform tasks. One of the tasks that search engines

like Google perform very regularly is web crawling. Search engines use a

program called web crawler that systematically browsers the

World Wide Web to collect and store data about web

pages. Search engines can then use this data to provide quick and accurate results

against search queries. Now even though in this context, we are

using a nice and heavy term like web crawling. Web crawling is basically graph

traversal or in simpler words, act of visiting all

nodes in a graph and no prizes for guessing that there

are standard algorithms for graph traversal. We will be studying graph traversal

algorithms in a later lessons. Okay now the next thing that I want to

talk about is concept of a weighted graph. Sometimes in a graph, all

connections cannot be treated as equal. Some connections can be preferable to

others like for example we can represent intercity road network that is the

network of highways and free ways between cities as an

undirected graph. I’m assuming that all highways would be

bi-directional. Intra-city road network that is road

network within a city would definitely have one-way roads and so Intra-city network must be

represented as a directed graph but intercity road network in my opinion

can be represented as an undirected graph. Now clearly we cannot

treat all connections as equal here. Roads would be of different lengths and

to perform a lot of tasks to solve a lot of problems, we need to

take length of roads into account. In such cases, we associate some weight or cost with every edge. We label the edges with

their weights. In this case weight can be lenght of the roads,

so what to do here is I’ll just label this edges with some values for

the lenghts. Let’s say these values are in kilometers and now edges in this graph are weighted and

this graph can be called weighted graph. Let’s say in this graph, we want to

pick the best route from city A to city D. Have a look at these four possible

routes, I am showing them in different colors. Now if I would treat all edges as equal then I would say that the green route

through B and C and a red route through E and F are equally

good. Both these paths have to three edges and

this yellow route through E is the best because we have only two

edges in this path. But with different weights assigned to

the connections, I need to add up weights of edges in a path to calculate

total cost. When I’m taking weight into account shortest

route is through B and C. Connections have

different weights and this is really important here in this

graph. Actually, we can look at all the graphs as weighted graphs An unweighted graph can basically be seen

as a weighted graph in which weight of all

the edges is same and typically we assume to weight

as one. Okay so we have represented inter-city cities

road network as weighted undirected graph. Social network

was an unweighted undirected graph and World Wide Web was an unweighted

directed graph and this one is a weighted undirected graph. Now this was inter-city road network. I

think intra-city road network that is road network within a city can be

modeled as a weighted directed graph because in a

city that would be some one ways. Intersections in interest city’s road

network would be Nodes and road segments would be our edges, and by the way we can also draw an

undirected graph as directed. It’s just that for each undirected edge

we will have 2 directed edges. We may not be able to redraw a directed

graph has undirected but we can always redraw an undirected

graph as directed. Okay I’ll stop here now. This much is

good for an introductory lesson. In next lesson, we will talk about some more

properties of graph. This is it for this lesson. Thanks for

watching !

thanks a lot

Each of your videos are priceless. Thanks so much.

You are so didatic and constant paced, my friend. Thank you.

I had to prepare for an interview and needed to brush up on some old forgotten information. Your videos fantastic and I found that my knowledge came flowing back again. So thanks very much for taking so much time to put together such a great set of information!

Your videos help me super much, really enjoying them!! Thank you mycodeschool!

Great job !

I hope you upload videos about graph traversal and searching. Thank for the videos we aprecciate

thanks

thank u

Wow this is a great video, thanks a lot for the help! i`m definitely gonna have to sub now.

Honestly Ella needed friends more than Rama.

Best

the channel is really great and your voice is Lil bit like Stuart little 😁

Very good, clear and smart approach of presenting. Very professional.

Thank you

you guys are awesome

u sound like stuart little :p but u r a good teacher 🙂

I would be wary when representing an undirected graph as a directed graph with double directed edges, as this messes up certain algorithms. Other than that, spectacular lesson!

u make everything look so easy… I loved all ur ds videos…keep it up!!

n thanx for providing.

Just One word Awsome

Hats off to the quality of this one and related tutorials!

great videos, really appreciate the effort you put into the examples.

Instagram and twitter are better examples for directed graphs.

This is the most cogent and easily understandable explanation of basic computer science I have seen. I look forward to watching the rest of your videos.

So if Facebook can be represented by undirected graph then instagram could be represented by directed grapth?

4:28 V1 ZULUL

do u have videos for Insertion ,Bubble, Quick and Heap Sort?

+mycodeschool please sir can you insert some videos to explain the ideas of topological sort ,backtracking and dynamic programming because I found your videos so helpful for me I'll be pleased if you answerd my request and thank you so much

You are so AWESOME !!!

Hello. Is one vertex also a graph? is that graph connected if it only has one vertex? is then minimum graph degree 0? Pls help, tnx

Best explanation I've seen so far! Excellent Video!!!

Great tutorial! Thank you! Can you please tell me the tool you used to create these videos.

Directed graph is a graph with all edges unidirectional. Then why in the given example at 7:46 has one unidrectional edge??

F***ing genius! God, thanks for being born, dude! I read a whole 28 page chapter and I was totally clueless… I watch our 16 minute video and I totally get it now…

Well done, thank you!

what is mean of a[10]={0}

please give me a ans..

Good Explanation. Keep up the good work. Thank you

E -> D is the shortest route, based on weights. Otherwise, E -> A -> B -> C -> D has a total weight of 680. If E -> is congested, then E –> A … -> D is the shortest route.

please upload video for advance data structure

superb work!!!!! thankyou so much for making me understand the concept of data structures so beautifully !!!!

Can anyone help me to clarify some questions in data structures ..please help me anyone help me. I can post my questions if u help me.. plsssss

One of the best tutorials on Datastructures I have come accross, Thank you so much for sharing this knowledge this way.. !! kudos to your teaching skills

what a name "Swati"

.. good

Came for a refresher on these things and will probably end up watching your videos all day. Your videos really hit all points and are delivered so well, Thank you:)

Thank you!

do you have video on map in c++

"If I am your friend, you are my friend too." 😀

this is the best introduction to graph I've seen so far

Great videos, thanks a lot for your help!!

This is very, very clear!!

I am interested in doing some research around your video contents. Can we talk?

Great video ! keep it up codeschool

Thank u sir.

great explanations man, well done!

Great Video I really enjoyed your dtata structures playlist.

Sir i am trying to open mycode website for problem solving it gives bad gateway error.

so easy to get, thanks

nyz work..Thank

A graph can be represented as Map as well

Directed acyclic graphs bro. Now I know how IOTA and tangle work lol

Your best dude, you should open up a coding test site like hackerrank, codility as well

Amazing!

Excellent!

Awesome

Clear video and nice explaination

V1 ZULUL

Wikipedia has not returned my favor by giving a link to my video… ha ha awesomely scripted.. beautiful way to teach.. kudos… keep up the good effort.

Great one sir

wtf just add some how to code graphs bro. not this shit.

You draw so beautiful 🙂

poce bleu

g pairdu seyse monute 2 MA VVUUUUIIIIII

Sir can u make video on Hash table in C++ plz .

Wow, one of the more clear and precise explanations.

Amazing man, amazing video

Nice tutorial!!

Well explained!

Vey nice way of explanation . Good work !!

So a graph in c++ is like a non-sequential linked list where all the nodes are pretty much pointing to another node randomly? And the the nodes that are being pointed to are the "neighbors" of that node that is doing the pointing?

amazing explanation

thank u sir for such an amazing videos

You are a great man and more better than proffessors in my college, I have learned a lot from you . I felt like I was waste fellow , I couldn't understand data structures, algorithms and pointers

even if I had studied many times. but after watching your videos ,those concepts became easy .only because of you dude. you are a life saver,thanks a lot.But wanna see you back in you tube, why don't you upload more videos to save people like us.

Go back by clicking, left pointing arrow icon on the top-left corner of your page, just below the tab button…

and what if I am following a certain someone on Facebook.

So great buddy. Your explanations are so perfect and easy to understand.

Thanks a lot

A year later I'm still here. I owe my degree to this you sir.

Just loved how you wrote 'facebook' in blue. Little things matter. Impressive!!!

Great info.

There is no special name for an undirected graph…my heart sank a little for some reason

Your videos are really helpful , Thanks a lot.

fascinating, I had never considered that the entire graph could be a data structure. I was introduced to trees in my studies, but for some reason, I never considered it a subset of the set of all graphs.

Social networks like Instagram are directed graphs. 🙂

I have to make a game with graphs for my last hw ;-;

played this on 2.5 speed and in just 4 minutes I'm already feeling good about graphs thanks

if you are my friend then I'm your friend too then why not I love her but she doesn't. 🙁

funniest video so far 😉 thx a lot!

You are like a great teacher who goes deep into making the concepts as lucid as possible. I am a working professional, if you need anything that I can be helpful to this channel, please do email me. I strongly feel this channel has the potential to change billion minds across globe.

Thanks animesh nayan

Good information bro..

I was struggling with my data structures assignment. I watched the 50 minute lecture over and over and still didn't get it. This video is a life saver and I can finally get on with the assignment.

can you please make videos on AVLTree