Graph as a Data Structure
Graphs are used to represent elements that share connections between them. It is considered as a non-linear data structure that has Node/Vertices (V) as the elements and the edges (E) as the connection link between the elements. A graph G with a set of vertices (V) with a set of edges (E) is represented as G (V, E).
A, B, C, D, E, F, and G are the vertices in the graph G.
A-B, A-G, A-D, B-A, B-G, B-C, B-E, C-B, C-E, C-F, D-A, D-F, E-B, E-C, E-F, F-G, F-D, F-C, F-E, G-A, G-B, and G-F are the edges of Graph G. Since they are undirected edges, the A-D edge is the same as the D-A edge and similarly for others.
Graphs can be divided into Undirected and Directed graphs. The Facebook friends group is a real-life example of an undirected graph. When a person adds a new friend on Facebook, both of them have the same access to each other’s profile. The undirected can also mean bi-directional so that all nodes can interact both ways, so the direction does not come into consideration.
A, B, C, D, E, F, and G are the vertices in the graph G.
A-B, A-D, B-G, B-C, B-E, C-F, D-A, D-F, E-C, E-F, G-A, and G-F are the edges of Graph G. Here, the direction of edges is important, so the A-D edge is not the same as the D-A edge.
In a directed graph, the edges are not necessarily mutual. Suppose the edges are roads between 2 cities. Here, a person in City A can travel directly to City B but, a person in City B cannot travel to City A directly. The person has to take a different route, ie, B-G-A. In this diagram, a person in City A and City D can travel back and forth.
Another real-life example of a directed graph is the Instagram followers network. Consider directed edges representing a person following another from the above diagram. Person C is being followed by B and E, but C only follows F. If both are following each other then both of them will be having full access to each other profiles. Influencers on Instagram will be having many directed edges toward them. Here, Person F is such a case.
Both graphs can be with weights, and they can be anything that we assume. If we are taking the nodes as different cities and the edges as the roads connecting them, then the weight could be the distance between two cities, or the gasoline required for a car to travel the distance, and even the time of travel. The weight changes according to the situation in which the graph is constructed.
The main question that arises for someone who is new to graphs is how we represent these graphs. The most commonly used representations for graphs are :-
- Adjacency Lists
- Adjacency Matrix
Adjacency Lists
It is a collection of unordered lists, each describing the set of neighbors of a particular node in the graph. Let us check the above graphs.
Adjacency Matrix
It is a 2D matrix of shape (VXV) with 1 and 0 indicating a connected and disconnected edge between two vertices respectively.
In the upcoming blogs, we will see how to visualize graphs using Python.
Thanks for reading. Hope you find this information useful and feel free to connect with me on Linkedin.
