Learn how to represent an unweighted undirected graph using an edge list. We build a sample graph with nodes and edges, then show the vertex list and edge list as tuples. See why storing indexes instead of node values makes lookups faster in constant time. Follow along as we list every connection without duplicates. This is the first in a series covering all four combinations of weighted and directed graphs with edge lists.
00:00 Introduction to Edge List Representation
00:56 Drawing a Sample Graph with Nodes
02:05 Adding Undirected Unweighted Edges
03:10 Graph as a Tuple of Vertex and Edge Lists
03:40 Building the Vertex List
04:24 Storing Nodes as Objects with Indexes
06:13 Creating the Edge List of Tuples
07:00 Listing Edges by Node Values
11:36 Limitations of Storing Node Values
12:30 Switching to Index-Based Edge List
14:08 Constant-Time Lookups with Indexes
16:54 Summary of the Edge List Method
17:16 Preview of Next Videos in the Series
17:44 Closing Remarks and Subscribe Request
=-=-=-=-=-=-=-=-=
Thanks for watching!
Find us on other social media here:
- https://www.NeuralLantern.com/social
- Twitter / X: https://x.com/NeuralLantern
- Rumble: https://rumble.com/c/c-3696939
- BitChute: https://www.bitchute.com/channel/pg1Pvv5dN4Gt
- Daily Motion: https://www.dailymotion.com/neurallantern
- Minds: https://www.minds.com/neurallantern/
- Odysee: https://odysee.com/@NeuralLantern:5
Please show your support!
- Buy me a coffee: https://ko-fi.com/neurallantern
- Subscribe + Sharing on Social Media
- Leave a comment or suggestion
- Subscribe to the Blog: https://www.NeuralLantern.com
- Watch the main “pinned” video of this channel for offers and extras
Hello there! Let’s talk about representing an unweighted,
undirected graph in your machine using an edge list representation.
Okay, so hopefully you watched my previous videos. If you haven’t, you might want to take a step back
and check them out. We talked about, you know, what is a graph? What are some basic rules and
terminology of a graph? Not graph and paper, but a graph. And we talked about representing paths
in graphs.
representing paths in graphs using either a list of nodes or a list of edges and we’re going to
take the edge list concept one step further and we’re going to actually just say this whole graph
is being represented as an edge list it’ll make sense in a little bit but uh so the first thing
i’m going to do is try to set up my stuff which is always set up wrong because i’m the one setting it
up and it always gets messed up okay so i got a graph paper and uh oh i got to make this other
thing full screen. Sorry.
um i’m going to draw a random graph just real fast so i’m going to do i don’t know just some random
nodes so remember a graph is a collection of nodes and edges doesn’t even have to have edges but you
know we’ll just say so we’re going to do that’s bad let me try one more time we’ll get that okay
so we get i’m trying to get this circle perfect because i’m gonna have to duplicate it rare okay
i’ve got a node here and i’m just going to give it an arbitrary value i’m going to say it’s got a 3
and then i’m going to duplicate it a few times just to make a graph that is a little bit
interesting so we have something uh something to kind of challenge us i guess so it’s not
incredibly boring um and then i’m going to change some of the values here and then well i’ll change
the next ones and then we’ll start looking at edges which edges do we want to make okay so
right now we’re just making a graph make this graph along with me if you want to or uh you
you know, after you.
to or uh you know after you think you understand do another graph on your own
okay so i’m gonna make some edges right now remember this is going to be an undirected
unweighted graph so the edges are just going to be lines they’re not going to have direction on
them and they’re not going to have weights on them i’m going to do a line over here i’m just
randomly doing lines doesn’t really matter um what we do exactly the point is going to be let’s
practice represented
be let’s practice representing this graph okay so i’m just making a random graph it’s kind of like
a little bit dense i don’t know um maybe i’ll just stop there and then i’ll add a wonky line just
just to prove we can be cool about this i don’t know we’ll do another one right here so it’s a
slightly more interesting graph okay so um that’s just a graph and uh what i’m going to do is i’m
going to say this is a, you know, an unweighted, oops, weighted.
oops waited undirected uh graph and we’re going to use the edge list of representation
i have spell check on this i really hope i do nope okay i guess i forgot to fix that months ago
all right so then the next thing we’re going to do is uh we’re going to look at the idea of like
how do we start with the edge list representation okay um the first thing i’m going to say is that
our graph
that the our graph in an edge list representation is a tuple just meaning it’s you know some things
put together if you know tuples encoding already uh the tuple is going to consist of a collection
of vertices and edges what’s going to be an edge list don’t make fun of my ease please
anyway so uh let’s do the first thing is going to be the vertex list so how do we represent the
vertex list or the node list well i’m just going to say that my vertex list v
to say that my vertex list v is equal to something and we’ll just put inside of this
some vertices so the easiest way when you’re kind of drawing this right now is i’m just going to
start putting the values of the node i’m going to say well here’s a three and uh i guess i could
sort them for whatever reason uh if we’re going to do binary search on them later but we’re not
going to i’m just going to maybe you know what i’ll go from left to right so that’ll make more
sense, just visually. So I’ll go from left to right. 3, 13, 6, 12.
3, 13, 6, 12, and a 15, and an 18.
You can see all of those are nodes, right?
Somebody stop me if I forgot a node.
Okay, here’s the thing though.
What are we actually storing in this vertex list?
You probably don’t want to store the node values.
I mean, you could be a little slow and dumb though,
but we want the option to be a little bit faster later
and also the option to turn these vertices into full classes,
like give them extra properties and whatever.
So what I’m going to say is that…
So what I’m going to say is that I’m writing down the number 3 and the number 13 here for you, but you should imagine in your code you would have an object of type vertex or node, like a full class, and you would basically be stuffing pointers inside of that vector, inside of that list.
I keep saying list. It is called an edge list representation, but you can probably imagine
that this could just as easily be a vector. If you’ve seen my other videos, you know what that is.
but uh so i want to be able to index this uh faster so for me personally i make this a vector
and not an actual list but we’re going to call it a list anyway so three should be a pointer
uh to a full node object uh smart pointer raw pointer whatever you want 13 should be a full
pointer to an entire uh entirely different node object with just 13 assigned as its uh template
type value because we’re making this a vector we can actually index
can actually index uh the nodes right so like this is like index 0 for the 3 node index 1 for the 13
node so i’m just going to put the indexes here whoops just to drive the point home a little
bit further so if i told you hey let’s do uh the node at index 2 you would know that is the node
that is in the very middle with the value of 6 because index 0 and 1 and 2 brings you to this
node right here um which is a 6 so this is going to this is going to help us later let me save this
Real fast, by the way.
let me save this real fast by the way i’m just going to do that okay so uh the next thing that
we need to do is uh make an edge list the edge list is really where it’s all at that’s really
where all the data is it’s going to tell us exactly where everything is or it’s going to
describe the whole graph pretty much so the edge list is another we’ll say that’s a list this could
be like a linked list or vector or whatever you want i’m just going to say it’s a linked list
and every item in the list is going to be another tuple so remember above the graph itself was a
tuple containing a vertex list and an edge list so the edge list is a list of tuples
meaning you know items bundled together for one tuple and then just like a list of those
so what i’m going to try to do is describe every single edge uh one by one using one tuple each
inside of the edge list so the first thing i’m going to do just you know to make this a little
little bit easier.
thing I want to do just you know to make this a little bit easier is I’m going to ignore the
indexes for the vertex list and I’m going to say let’s describe everything happening from the three
node outwards or just to every other node so the three node itself I’m going to look at its
connections from left to right so the three node let’s just start by putting a three here
maybe I should describe the legend real fast the tuples will basically be the start node
and then the end node
and then the end node and then the uh well the weight if there was a weight but we’re doing an
unweighted graph so it’s really just going to be a tuple of two items the other thing to keep
in mind is that because this is an undirected graph it really doesn’t make a difference what
node is the start node and what node is the end node you can just swap them and it’s totally fine
for me personally i’d rather you know sort before assigning the start node and end node that way
when i read the graph later it’s a little bit faster because i wouldn’t have to check in both
directions but
wouldn’t have to check in both directions but it really honestly doesn’t matter right now so
start node and end node so the start node here is 3 and the end node is going to be 13 so that’s the
first thing that we’re doing that’s the first tuple and then i’m going to say what else does
the 3 connect to it connects to the not the 6 it connects to the 12. okay so the 3 connects to the
- again we could have said 12 comma 3 wouldn’t have mattered but i’m just going to try to keep
it sorted so then
keep it sorted so then what else does the three connect to it connects to the uh the 18 doesn’t
connect to the 15 and just confirm that if i’m looking at the three i can see three lines
touching it so that means okay there’s got to be three tuples for the for the e for the three so
i’m going to say three connects to the 18. and now i’ve described everything happened to do with the
three note i will simply continue let’s see should i do like a new line maybe i should try to do a
new line for every
try to do a new line for every start node so this is easier to look at okay so i’m going to do that
and i’m going to say the next line is we’ll start at the 13 this time so the 13 the 13 is also
connected to the 3 because it goes in both directions with an undirected graph but we
already described that connection with that first row so 3 comma 13 describes 13 comma 3 i don’t
want to duplicate edges so forget about that let’s look at what else 13 is connected to it’s connected
it to the six
connected to it’s connected to the six so I’m just going to put 13 comma 6 and then that’s the end of
the 13’s connections oh I could have used tabs for that hang on let me do that okay so now let’s look
at the six node six is not connected to the three it is connected to the 13 but we already described
the 13 6 connection in the previous row so forget that and then I’m just going to look to the right
So the 6 is connected to the 12 and the 15.
the 12 and the 15 12 and the 15 and also the 18 so i’m going to do 6 comma 12 maybe i’m going to
do a copy paste here real fast just to make it easier 6 12 and 6 15 and 6 18 so again all i’m
doing is describing you know what other nodes the current node is touching and i’m going to do that
using a tuple that just has one node and has another node and that’s pretty much it so when
we’re done with this
it so when we’re done with this uh we’re going to look at the 12 node 12 node it’s connected to
the six already handled it’s connected to the three it’s already handled and it’s connected
to the 18 not handled yet so i’m going to say 12 goes out to 18. okay then we’re going to look at
the 15 node 15 and 6 that’s already handled in that third row so forget that 15 and 18 that is
is not
15 and 18 that is not handled yet so we’re going to do 15.18 by the way this is one benefit of
going from left to right visually all i really have to do is just look my eyes to the right and
i’ll see nodes that i need to take care of and if i look my eyes to the left i’ll see nodes that i
already took care of if that makes sense so now that we’re done with the 15 let’s see we did 3 13
6 12 15 let’s just take care of the 18 if there’s anything left to take care of i can guarantee
there’s not going to be.
there’s not going to be because every node the 18 is the node on the farthest you know the furthest
to the right so everything on the left is already handled so we don’t even have to put anything for
the 18 node okay give me a second to clean up this graph real fast i think i want to maybe
move this up a little bit okay uh now here’s the thing though we’ve only named node values so if
we wanted to i don’t know let’s say check to see if the uh let’s say we have an edge we’re looking
Thank you.
let’s say we have an edge we’re looking at the 3 comma 13 edge and we’re asking now do both of
those nodes exist the edge describes these two nodes do they exist or uh maybe let’s look at
the three here and we want to figure out just you know what other nodes does three touch so we start
iterating through all the edges here how can we actually get a pointer to that node to manipulate
it in the code right now it’s okay because it’s a diagram but you know this is not very
diagram but you know this is not very good storing values directly in this notation in your code you
probably want to store pointer uh pointers there but maybe not necessarily smart pointers they take
a little bit of extra memory and it’s kind of cumbersome but um we could store an index into
this vertex list to make things a little bit faster let me show you what i mean but first i’m
going to duplicate this list that we just made already, duplicate it over here, and
over here and maybe i’ll label the first one and i’ll say so we already have start node and end
node i’m going to say e underscore by value so we’re storing the edge list by node values and
then here we’re going to store nodes by their index in the vertex list so what do i mean by
index well okay right here the first node that we’re mentioning is the three well look at the
three node in the vertex list it’s at index zero right so i’m just going to put a zero
zero right so i’m just gonna put a zero that’s it change it to an index then i look at the 13
that’s index one and then i look at the three again that’s index zero um and then the 12 is
index three and then the three again is index zero and the 18 is index five um if that was too fast
i’m sorry just rewind and play it back in slow motion i think this video is already getting way
too long so then i do the same thing for every single other tuple so the 13 node um that is
node um that is index one so i’m going to put a one there the sixth node is index two go on to
the next node so the sixth node is index two and then the 12 is index three and the six is two and
the 15 is actually four the six again is two the 18 is five move on to the 12 node here uh that’s
index 3, 18 node is index 5, and then
the 15
and then uh the 15 is index 4 and then 18 again is index 5 so now on you know on both sides like
in both of these edge lists uh i’m representing the graph it’s just that one can be a little bit
more efficient than the other uh for example if i was going to let’s just say i wanted to scan
every single edge in the graph well i could scan this list right here in linear time so linear time
based on the number of edges and every single time i see an edge i can jump directly to the
Corresponding.
jump directly to the corresponding vertex or node in constant time because i have an index
so for example let’s say uh you know this uh the sixth node um touching the 15 node so that
particular edge right there let me i want to be more interactive here how can i do this okay
uh suppose i want to do
612 node and so that’s going to be pointing to this edge right up here i want to see you know
what’s going on with both of those nodes well if i was looking at the value-based edge list
and i wanted to get a hold of let’s say the sixth node itself so i can like do something with that
vertex like delete it or move it or just whatever i would have to then scan the entire vertex list
i’d have to go you know this one this one this one this one this one until i eventually found
the corresponding value.
uh the corresponding value this wouldn’t really support duplicate values either
uh it would be kind of hard to do that but uh i’ve i’ve slowed down the program it’s linear
time based on the number of vertexes and if you’re already doing linear time based on the number of
edges this is like it’s technically still a scalable data structure but it’s not super fast
it could be faster on the other hand uh so like i just said uh sorry for repeating myself if we did
the index
the index based uh edge list it says two three here which is the 612 how can i find the sixth
node well i just look at index two and instead of scanning oh gosh hang on
i’m not as fast as i used to be okay dude there’s like did you see that uh
a whole bunch of pink dots everywhere now what have i done okay
So, uh…
so uh i’m looking at the 612 edge i see that the indexes are two and three that means in constant
time i can just jump directly to i guess i’ll put it in red in constant time index two right there
and index three right there i do not have to scan the vertex list or the vector i guess if it was a
vertex list like an actual linked list then i’d still have to scan because it’s linear time to do
it but if it’s a vector
But if it’s a vector or an array, I can just jump to an index in constant time, so it’s way faster.
So what I’m trying to say is that this representation is what you want to do in the code when it comes to, I don’t know, representing diagrams and stuff.
I don’t know. The one on the left is more human friendly.
So this is the basic idea for how to represent an unweighted and also undirected graph in the machine using the edge list method of representation.
i guess i’m going to cut the video i hope you learned a little bit of stuff and had
a little bit of fun in the next video i think i’m going to do uh weighted uh undirected graphs
and this i’m going to do four videos for this one representation type i’m going to do unweighted
undirected and then weighted and undirected and then unweighted and directed i’m gonna
do all four combinations all right see you in the next video thanks for watching
hey everybody thanks for watching this video again from the bottom of my heart i really appreciate it
i do hope you did learn something and have some fun if you could do me a please a small little
favor could you please subscribe and follow this channel or these videos or whatever it is you do
on the current social media website that you’re looking at right now it would really mean the
world to me and it’ll help make more videos and grow this community so we’ll be able to do more
videos, longer videos, better videos, or just I’ll be able to keep making videos in general.
just i’ll be able to keep making videos in general so please do do me a kindness and uh and subscribe
you know sometimes i’m sleeping in the middle of the night and i just wake up because i know
somebody subscribed or followed it just wakes me up and i get filled with joy that’s exactly what
happens every single time so you could do it as a nice favor to me or you could you could troll me
if you want to just wake me up in the middle of the night just subscribe and then i’ll i’ll just
wake up i promise that’s what will happen also uh if you look at the middle of the screen right now
you should see a QR code, which
screen right now you should see a QR code which you can scan in order to go to the website which
I think is also named somewhere at the bottom of this video and it’ll take you to my main website
where you can just kind of like see all the videos I published and the services and tutorials and
things that I offer and all that good stuff and if you have a suggestion for clarifications or
errata or just future videos that you want to see please leave a comment or if you just want to say
hey what’s up what’s going on you know just send
what’s going on? You know, just send me a comment, whatever. I also wake up for those in the middle
of the night. I get, I wake up in a cold sweat and I’m like, it would really, it really mean
the world to me. I would really appreciate it. So again, thank you so much for watching this video
and, um, enjoy the cool music as, as I fade into the darkness, which is coming for us all.
Thanks for watching!
