I talked about what graphs are in terms of not only computer science but just as a general concept in my last post. I suggest you read that first if you don't already have an understanding on what graphs are.
Now I would like to discuss this topic in the context of computer science and how such useful data structures can actually be implemented. This will be a language agnostic tutorial, meaning that these concepts can be implemented in any language.
There are 2 main ways to implement graphs:
- Adjacency Matrix
- Adjacency List
Adjacency Matrix
Let us take a look at the first method - adjacency matrix. In this method we will be representing a graph using a table. For this example assume we have a undirected, unweighted graph, however this method work for directed and weighted graphs as well. In this method we will label the rows and columns of our table with nodes. Next we look for connections in our graph, assume that node '1' is connected to node '2', then we will put a value of 1 in the square with position [2, 1], where 2 represents the column, and 1 represents the row. We use a value of one because it is standard for representing TRUE. We continue with this process and fill in all the connections. The picture below shows this example (Credit to GeeksForGeeks for the image).
If the graph was weighted we would just fill in the squares with the weights instead of 1.
There are not many advantages to this method except for the fact that inserting and deleting connections is very easy. However in a graph with few connections and lots of nodes, a lot of the squares in the matrix would be empty, and this is wasted space which is not very good. Also adding or removing a node to the graph means that you will have to add or remove a row and column which is not recommended.
Conclusion
This is one way one that graphs are represented, and it is relatively easy to code yourself, however something like this would not be favored in big projects or industry simply because of how much space it wastes and it being hard to rescale.
We will discuss a better way to represent graphs - Adjacency lists - in the next article. I hope you enjoyed reading.
Top comments (0)