In this tutorial, you will learn what a Graph Data Structure is. Likewise, you will discover representations of a graph.
In this article, you will learn-
What is a graph (data structure)?
A graph is a typical data structure that comprises a finite set of nodes (or vertices) and a set of edges associating them.
A pair (x,y) is alluded to as an edge, which conveys that the x vertex interfaces with the y vertex.
In the example beneath, circles address vertices, while lines address edges.
Graphs are used to take care of genuine issues that include the portrayal of the issue space as a network. Instances of networks incorporate telephone networks, circuit networks, social networks (like LinkedIn, Facebook, and so on)
For instance, a single user in Facebook can be addressed as a node (vertex) while their association with others can be addressed as an edge between nodes.
Every node can be a structure that contains data like the user’s id, name, gender, and so on
A graph data structure is an assortment of nodes that have data and are associated with different nodes.
Let’s attempt to understand this through an example. On facebook, everything is a node. That incorporates User, Photo, Album, Event, Group, Page, Comment, Story, Video, Link, Note…anything that has data is a node.
Each relationship is an edge starting with one node then onto the next. Whether you post a photograph, join a group, similar to a page, and so on, another edge is created for that relationship.
All of Facebook is then an assortment of these nodes and edges. This is on the grounds that facebook uses a graph data structure to store its data.
All the more absolutely, a graph is a data structure (V, E) that comprises of
- An assortment of vertices V
- An assortment of edges E addressed as ordered pairs of vertices (u,v)
In the graph,
V = {0, 1, 2, 3}
E = {(0,1), (0,2), (0,3), (1,2)}
G = {V, E}
Types of graphs:
Undirected Graph:
In an undirected graph, nodes are associated with edges that are generally bidirectional. For instance, if an edge associates nodes 1 and 2, we can traverse from node 1 to node 2, and from node 2 to 1.
Directed Graph
In a directed graph, nodes are associated by directed edges – they just go in one direction. For instance, if an edge interfaces nodes 1 and 2, yet the arrow point focuses towards 2, we can just traverse from node 1 to node 2 – not the opposite direction.
Graph Terminology
- Adjacency: A vertex is supposed to be Adjacent to another vertex if there is an edge associating them. Vertices 2 and 3 are not Adjacent in light of the fact that there is no edge between them.
- Path: A grouping of edges that allows you to go from vertex A to vertex B is known as a path. 0-1, 1-2, and 0-2 are paths from vertex 0 to vertex 2.
- Directed Graph: A graph in which an edge (u,v) doesn’t really imply that there is an edge (v, u) too. The edges in such a graph are addressed by arrows to show the direction of the edge.
Graph Representation
Graphs are ordinarily addressed twoly
1. Adjacency Matrix
An adjacency matrix is a 2D array of V x V vertices. Each row and column address a vertex.
In the event that the value of any element a[i][j] is 1, it addresses that there is an edge associating vertex I and vertex j.
The adjacency matrix for the graph we created above is
Since it is an undirected graph, for edge (0,2), we additionally need to mark edge (2,0); making the adjacency matrix symmetric about the corner to corner.
Edge lookup(checking if an edge exists between vertex An and vertex B) is very quick in adjacency matrix representation however we need to reserve space for each conceivable connection between all vertices(V x V), so it requires more space.
2. Adjacency List
A Adjacency list addresses a graph as an array of linked lists.
The index of the array addresses a vertex and every component in its connected rundown addresses the other vertices that structure an edge with the vertex.
The Adjacency list for the graph we made in the first example is as per the following:
An Adjacency list is productive as far as storage since we just need to store the values for the edges. For a graph with a large number of vertices, this can mean a lot of of saved space.
Graph Operations
The most common graph operations are:
- Check if the element is present in the graph
- Graph Traversal
- Add elements(vertex, edges) to graph
- Finding the path from one vertex to another
Thanks for reading! We hope you found this tutorial helpful and we would love to hear your feedback in the Comments section below. And show us what you’ve learned by sharing your photos and creative projects with us.
