Transcript from the "Graph Vocabulary & Representations" Lesson

[00:00:00]

>> Bianca Gandolfo: We are going to hop into graphs. So we looked at linked lists, we looked at trees, which were all a specialized type of graph. So a graph is simply a collection of vertices connected by edges. It is a data structure that is really good at representing relationships between different nodes.

[00:00:20] And not necessarily a hierarchical relationship, but any kind of relationship. And graphs are one of the most widely used data structures when we're trying to study real world things like, I don't know. Like a map, for example, all the cities and the streets would be considered a graph, the Internet, right?

[00:00:43] Different servers connected would be an example. Websites connected with links as the edges. What else? We can also represent mazes as points and edges, like Pac-Man is an example. We'll do some traversals, which will be the same as maze traversals if you wanted to make a maze solver.

[00:01:12] What else can we do with graphs? Hm, so those are kind of obvious ones. And then there's a bunch of mathematical applications as well for calculating different stuff in statistics.

>> Bianca Gandolfo: When else can we do a graph? Does anyone else have an example of a graph?

>> Bianca Gandolfo: So we can replicate natural phenomena and see if water can flow through cracks, depending on the density of the rock and things like that.

[00:01:52] So we can do all kinds of really cool modeling with graphs. Trying to think of what else. Like data compression is another use of a graph.

>> Bianca Gandolfo: So that's really cool stuff. But we have to start with one thing at a time, right? We have our vertices, or nodes, we can call them nodes, but we technically call them vertices, connected by edges.

[00:02:25] Cool. We have relationships. So we have some new vocabulary words. So again, edges, they represent a connection between two vertices. They can be directed or undirected. A directed graph means that you can only travel from one node in a certain direction. So this is a directed graph, where you could only travel from this node to this node.

[00:02:49] We can't go backwards. And so use cases for a directed graph would be a street. So any sort of navigation. Google Maps, for example, would be a really, really complex directed graph, because there's one way streets and things like that. And you can only get to places in a certain order.

[00:03:07] So that would be a directed graph. An undirected graph would be,

>> Bianca Gandolfo: I don't know, I'm thinking. One that doesn't order. Direction is not a piece data that's important to you. So the vertices, those are gonna be your nodes. They're gonna contain data. A path is just a sequence of connected vertices.

[00:03:33] So back to the example of the website with the links. You can see if there's a way to get from one website to another website by following embedded links. Web crawlers do that, your search engine does that kinda stuff. Simple path, no repeated vertices. A cycle is a path that's cyclical.

[00:04:01] So this would be a cycle. That's one of the main things that sets a tree apart from a graph by just a very, the definition of it is that a tree is a graph that has no cycles. So you'll never see a cycle in a tree. Suddenly, if your tree has a cycle, you're doing it wrong and you suddenly made a graph, which is fine.

[00:04:19] Just maybe you're using the wrong data structure.

>> Bianca Gandolfo: And then, an acyclic graph has no cycles.

>> Bianca Gandolfo: Cool, mm-hm?

>> Speaker 2: So for the undirected graph, do you need a reference going from one node to the other and another reference coming from the other node to this one, so you need to have two?

[00:04:40]

>> Bianca Gandolfo: Mm-hm, you need to have a way to represent, either going one way or the other way, yeah. Or and, it's an and, not an or. Cool.

>> Bianca Gandolfo: Yeah, so, Facebook, Twitter, any sort of social network, that would be an undirected graph, actually, where you can go from one friend to the other friend, back, and in any which order's an undirected graph.

[00:05:07] So social networks, a very, very famous example of graph is Facebook. And we hear about, Facebook graph search. And it's just really advanced algorithms around processing large graphs of data, around relationships between people, companies, interests, all kinds if interesting things. It may be a little bit creepy, right?

[00:05:29] All the data they're able to extract from that.

>> Bianca Gandolfo: Okay, so here's some common operations that we're gonna think about when we're thinking about any kind of graph. We need to be able to add an edge, delete an edge, detect if there's an edge between two nodes. Find its neighbors and see if there's a path between two vertices.

[00:05:58] Cool. Creating a vertex as well. So you can have a graph that's unconnected that's just one vertex in space. And it can live there forever and then you can just connect them anytime. That make sense?

>> Bianca Gandolfo: All right, common operations. So the next thing I want to talk about is how do we represent our graph.

[00:06:23] So when we've been talking about trees and linked lists, we've only really talked about one way to represent them more or less. And it's kind of these nested data structures with pointers. But actually, when we represent graphs, we do it in a more abstract way because we wanna optimize for certain algorithms or operations on a graph.

[00:06:44] So I'll talk about two major ones, and we're only gonna stick to one. But we'll do some exercises thinking about how can we represent this graph not as a super nested object necessarily. Like were doing with trees, that might be where your next step in your mind was.

[00:07:01] Like, we have a linked list, its objects, they have pointers to each other. We have a tree. It's an object within an object within an object, continue with more pointers right?

>> Bianca Gandolfo: Graphs, you could represent it like that, but we're gonna talk about how to optimize that representation for specific use cases.

[00:07:23] That's what we're gonna do right now. Any questions?

>> Bianca Gandolfo: I really love graphs. So here's an adjacency matrix. So you can imagine this is like a 2D array, an array within an array that is gonna represent just a binary relationship between two nodes. And so this is what graphs are really good at is representing any kinda binary relationship.

[00:07:48] And so if you can imagine what that might mean, it's huge, right? So how we do that with this adjacency matrix is simply put a 1, true, where there is an edge. So between 2 and 1, we have an edge. We represent it here as well. So we can just populate this based on,

[00:08:18]

>> Bianca Gandolfo: Where we have edges. So if we wanna add an edge, we simply change the 0 to a 1. To delete an edge, change the 1 to a 0. Cool, and this is undirected, so it does not have any opinions about which direction it can go.

>> Bianca Gandolfo: So what would have to change if we still wanted to use this adjacency matrix but we wanted to represent a directed graph?

[00:08:51]

>> Speaker 2: It'll be a zero for the one that's not direct, it has the direction to.

>> Bianca Gandolfo: Yeah, yeah, so instead of having a two way street here, we'd only put a one where it could actually travel.

>> Bianca Gandolfo: Or in this case, a negative one.

>> Bianca Gandolfo: Cool, so there's another kinda graph that I didn't tell you about yet.

[00:09:20] It's called a weighted graph. And this gives us a little more information about, we can call it the cost between two nodes. And this cost in our map example could be the time to travel between two cities, right? Which can change if there's traffic or whatever. It could be the size of pipes if we're measuring water moving through, I don't know, the plumbing system in the city or bandwidth.

[00:09:53] Or the distance between servers, so that we can calculate how long it takes to travel across the Internet, somewhere. What else could this represent, weighted?

>> Speaker 2: Use this for kinetic systems biology, you have different molecules, reactions.

>> Bianca Gandolfo: I don't know anything about biology. But if there's a cost to get from one place to another, like maybe energy, calories.

[00:10:24]

>> Speaker 2: The reaction time.

>> Bianca Gandolfo: Yeah, so those things could be represented in a graph with a cost. Or a weight, we call it a weighted graph. And this is a directed weighted graph means that it has both direction and weight.

>> Bianca Gandolfo: And you can see we represent it very similarly.

[00:10:44] We usually use just the weight instead of the one.

>> Bianca Gandolfo: Cool? Okay, and so this is very different than how we were representing our data before. It was kind of we have this idea, we draw it and then it's kind of abstract. And now to me, it feels like it's another layer abstraction.

[00:11:10] Do we feel that way? Yeah, I'm like dancing, dancing to my graph. Cool.