Graphs
This lesson will look at how to work with the graph data structure in JavaScript. We will see at how we can create graphs via Nodes and edges , access elements of a graph via depth wise and breadth wise search.
We'll cover the following...
A Graph is a data structure that is helpful in mapping several real-world scenarios. e.g. you and your friends on Facebook form a graph called a social graph. Similarly, the roads between towns and cities form a graph commonly know as 'Map'.
In computer science, a graph consists of a set of vertices and a set of edges. The vertices are the entities and edges define relationships between those entities. e.g. Bob, Frank, and Anna are friends. Frank has a friend named Jane who isn't a friend with Bob and Anna. In this example, all four people are vertices and edges represent a direct friendship. Let's look at the following graph
The above graph shows edges that don't have any direction. Such graphs are called Undirected Graphs. Undirected graphs show that the connection goes both ways. Here we are using an undirected graph as friendship is a mutual relationship (or at least it is supposed to be).
The edges with arrows represent direction of the relationship and such graphs are called Directed Graphs. e.g. let's draw a map of places where a directed edge represents that a road connects vertex A to B. If the edge goes from A to B, it means that the there is a road (one-way road) from A to B. Let's see an example
The above graph shows that if you are in Town A, you cannot directly go to Town D. You would either have to go through Town B or Town C. Similarly, from Town D, you cannot go anywhere except Town A, etc.
We've discussed some theories about graphs. Let's see how can we represent vertices and edges in a graph.
We've already established that a graph is a set of vertices and a set of edges. Representing vertices is easy. It's just a list of vertex names. Edges is a little tricky. For every edge, we need to store a source and destination vertex. There are two common ways to store edges. They are called
- Adjacency Matrix
- Adjacency List
Let's look at both of these techniques.
Adjacency Matrix is a square matrix (table) where first row and first column consists of vertices in the graph. The rest of the cells contain either 0 or 1 (it could be another number for weighted graphs but let's ignore that for a while). So each Row x Column intersection points to a cell and the value of that cell dictates whether the vertex represented by Row and vertex represented by Column are connected or not. If the value is 1 for cell V1 x V2, then V1 is connected to V2. An example would help here. Let's create the adjacency matrix for the town graph we saw above.
Now if you have to tell whether there is a direct road from Town A to Town D, you ...