Graph Data Structure Intro (inc. adjacency list, adjacency matrix, incidence matrix)

Key Takeaways

The graph data structure is not the same as a graph you may have learned about in math class. Graphs are collections of things and the relationships or connections between them. The data in a graph are called nodes or vertices. The connections between the nodes are called edges. One example of graphs is a social network where the nodes are you and other people and the edges are whether two people are friends with each other. There are two major types of graphs, directed and undirected. Undirected graphs are graphs without any direction on the edges between nodes. Directed graphs are graphs with a direction in its edges. An example of an undirected graph could be a social network. The nodes are people and the edges are friendships. An example of a directed graph could be the internet and web page links. The nodes are web pages and the directed edges are links to other pages, which might not necessarily point the other way. I'm going to show you three ways to represent a graph. The first way is called an adjacency list. This representation for a graph associates each vertex in the graph with the collection of its neighboring vertices or edges. In this image, A is connected to B, B is connected to A and C, and C is connected to B. This is how you could show a a relationship with text. And here is how you could show this adjacency list with JavaScript. This is an undirected graph because it does not show the direction of the edges. This can also be more simply represented as an array where the nodes just have numbers rather than string labels. Another way to represent a graph is to put it in an adjacency matrix. An adjacency matrix is a two-dimensional array where each nested array has the same number of elements as the outer array. So, it's basically a matrix of numbers where the numbers represent the edges. Zeros means there is no edge or relationship and ones mean there is a relationship. This table shows an adjacency matrix to represent the image. You can see that the labels for the nodes are on the top and left. Now, here's a JavaScript representation of the same thing. Unlike an adjacency list, each row of the matrix has to have the same number of elements as nodes in the graph. Here, we have a 3 by 3 matrix, which means we have three nodes in our graph. An adjacency matrix can be used to represent a directed graph. Here's a graph where the second node has an edge pointing toward the first node, and then the third node has an edge pointing to the first node. Notice how the numbers in the array change. There are only ones where a node is pointing toward another node, and since there only two points, there are only two nodes. The final way I will show to represent a graph is an incidence matrix. Like the adjacency matrix, an incidence matrix is a two-dimensional array. However, the rows and columns mean something else here. The adjacency matrix use both rows and columns to represent nodes. An incidence matrix uses rows rows to represent nodes and the columns to represent edges. This means that we can have an uneven number of rows and columns. Each column will represent a unique edge. Also, each edge connects two nodes. To show that there is edge between two nodes, you will put a one in the two rows of a particular column. As you can see in the diagram, edge one is connected to nodes A and B. Now, look at the column for edge one in the incidence matrix table. You will see a one in both the A row and the B row. This shows that edge one connects to nodes A and B. Here is a directed graph. For a directed graph, use -1 for an edge leaving a particular node and 1 for an edge entering a node. And here is a JavaScript implementation of the incidence matrix. Graphs can also have weights on their edges. So far, we have unweighted edges where just the presence and lack of edges binary, 0 or 1. You can have different weights depending on your application. A different weight is represented as a number greater than 1. Well, now you know about the different types of graphs and how to represent them in JavaScript. In my next video about graphs, I will cover graph traversal algorithms. Thanks for watching. My name is Beau Carnes. Don't forget to subscribe, and remember, use your code for good.