Your heap videos were enormously helpful to me when I was just learning the data structures. I'm sure this would've also made learning graphs a lot easier. Keep it up, man!
+Algorithms with Attitude I still have lots of friends that I know will find these enormously helpful, and it never hurts to look over the basics again every once in a while!
Sebrianne Ferguson Consider vertex 3. I think it is cleaner to store an array, indices 1 and 2 (or an array from 0 if your language starts indices at 0) instead of trying to store values at 4 and 5 after skipping 1 to 3. It isn't a big difference, just slightly cleaner to me.
+Raymond Berry If you want to use an adjacency matrix for a weighted graph, you can keep the weight of an edge in each location, but you need to have a special value for edges that don't exist, like nil/null if you have it, or positive/negative infinity depending on whether or not edge weights are something you want to minimize/maximize. Or, you could keep a reference to an edge object instead, with a null reference for non-existent edges.
Hello, On 4:27 you say that you can convert vertex outgoing list to vertex incoming list or the other way around. But what if let's say you have a complete graph, then each node has an adjacency list of order(n), then wouldn't the algorithm of converting be O(n^2)? Another question is how to determine which way to store information is better: matrix or lists of each node? Thanks
If there are n vertices, and m edges, the runtime is order (n + m). The size of the graph is also considered to be order (n + m). If it is a complete graph, it will take the time you suggest, but that is linear in the size of the graph, even if it isn't linear in the number of vertices. To know which one is better, it depends on which operations you want most. Need a list of vertices adjacent to some vertex? The adjacency list will be better for you. Need to look up if edges exist between specified vertices? Then the adjacency matrix would be better. If either was better than the other in all situations, the worse-off one would fade away, and not be considered useful anymore.
I guess the main implication is that the size of the graph is not just the number of vertices or number of edges, BUT the number of vertices plus the number of edges, correct? So, the answer is to think.
I had a similar question for why the memory usage was Theta(|V| + |E|) at the 6:36 mark. The question and answer discussion here for was helpful for me. Thanks!
![Yailin La Mas Viral, @kreizyk.official - Dale 2 (Remix) [Video Oficial]](http://i.ytimg.com/vi/JaYHBzgqz94/mqdefault.jpg)
Fantastic lesson, keep it up!!
+Cadu BFS should be ready Sunday or Monday...
Such a huge amount of useful info in such a short period of time! Awesome!
Hope you'll come up with more advanced graph algorithms :)
Keep it up!
Your heap videos were enormously helpful to me when I was just learning the data structures. I'm sure this would've also made learning graphs a lot easier. Keep it up, man!
+Pablo Berrotaran Thanks. I just finished the next video (BFS), but will start a shortest paths set next. (Perhaps too late for you though, sorry.)
+Algorithms with Attitude I still have lots of friends that I know will find these enormously helpful, and it never hurts to look over the basics again every once in a while!
This helped me a lot, thank you very much!
Great video!!
What an awesome video! Thank you so much!
Wish you would be my professor instead the one I paid $1000 and still suck at it. Bravo.
Some of my students wish they only need to see me on video...
Gotta appreciate the Pina Colada song joke!
How come indices are cleaner with the bottom part of the matrix at 2:27
Sebrianne Ferguson Consider vertex 3. I think it is cleaner to store an array, indices 1 and 2 (or an array from 0 if your language starts indices at 0) instead of trying to store values at 4 and 5 after skipping 1 to 3. It isn't a big difference, just slightly cleaner to me.
hi, When i drawing a matrix for a weighted list. Do I put the value of the weight instead of 1? i think i didn't understand that bit sorry.
+Raymond Berry If you want to use an adjacency matrix for a weighted graph, you can keep the weight of an edge in each location, but you need to have a special value for edges that don't exist, like nil/null if you have it, or positive/negative infinity depending on whether or not edge weights are something you want to minimize/maximize. Or, you could keep a reference to an edge object instead, with a null reference for non-existent edges.
Algorithms with Attitude ok thank you I've got it now :)
Hello,
On 4:27 you say that you can convert vertex outgoing list to vertex incoming list or the other way around.
But what if let's say you have a complete graph, then each node has an adjacency list of order(n), then wouldn't the algorithm of converting be O(n^2)?
Another question is how to determine which way to store information is better: matrix or lists of each node?
Thanks
If there are n vertices, and m edges, the runtime is order (n + m). The size of the graph is also considered to be order (n + m). If it is a complete graph, it will take the time you suggest, but that is linear in the size of the graph, even if it isn't linear in the number of vertices.
To know which one is better, it depends on which operations you want most. Need a list of vertices adjacent to some vertex? The adjacency list will be better for you. Need to look up if edges exist between specified vertices? Then the adjacency matrix would be better. If either was better than the other in all situations, the worse-off one would fade away, and not be considered useful anymore.
I guess the main implication is that the size of the graph is not just the number of vertices or number of edges, BUT the number of vertices plus the number of edges, correct?
So, the answer is to think.
I had a similar question for why the memory usage was Theta(|V| + |E|) at the 6:36 mark. The question and answer discussion here for was helpful for me. Thanks!