It is a collection of edges and vertices. It can be used to display any form of network.
The following graph contains a total of 4 vertices and 5 edges. In this graph, vertices are A, B, C and D while edges are AB, BD, DC, CA and AD. Vertices are also known as nodes. The line connecting these vertices is the edge. Vertices are like objects and edges indicate the relation between those vertices. Data is stored in nodes. This data can be of numerical data type or any other data structure.
Following are some major terminologies related to the graph:
Vertices
Vertices are also known as ‘nodes’ and can be represented as circles.
Edges
Edge is a connection between two different vertices or nodes. Edges are represented by ‘lines’ and they join two vertices or nodes.
Adjacency
There exist two types of adjacency in the graph:
Adjacent Vertices
They are those vertices that have an edge linking them.
Adjacent Edges
If there is a shared vertex among two edges then there exist adjacent edges.
Degree
It refers to the number of edges corresponding to a particular vertex.
Size
It shows the overall number of edges in a graph.
Path
It is an order of well-defined vertices such that two succeeding vertices are side-by-side. If there is an edge linking the two vertices that can be considered in a path but the vertex cannot recur.
To understand the graph, let us consider the following graph consisting of three vertices X, Y and Z. Edges in this graph are XY and XZ. The degree of node X is 2 because it connects two nodes. Similarly, the degree of Y and Z nodes is one. The size of this graph is two because there are two edges.
Types of Graph
Un-Directed Graph
In this, no directions are specified on the edges. This is also known as bi-directional. It has no defined traversal order. It can be traversed in both directions.
Directed Graph
This is also known as uni-directional. In this, every edge has specific directions. An edge goes from a single vertex to the other vertex. It contains an arrow pointed that represents the direction we can reach from one point to another in the only direction. The reverse direction is not possible.
Let us consider the following graph in which every edge has specified some directions. Direction from X to W is not equal to W to X because we can move only one direction in a directed graph.
Connected Graph
It contains a minimum of one path among each pair of vertices.
In the following graph, if we want to reach node C. So, node C can be reached from node A. Node A can be reached from B and node B can be reached from D or E. There exists various path to reach node C. From any point, we can reach point C and there exists at least one path.
Disconnected Graph
It contains no path among each pair of vertices. It is a combination of two or more linked graphs.
In the following graph, if we are at point D and we want to reach C. So there is no way that we can reach C or A from D due to the absence of an edge between A and B.
Weighted Graph
In this, we specify some particular weight to every edge. Weight is a real number that is associated with each edge of the graph.
In the following graph, we have specified weight 5 for edge XW. Similarly, a weight of 6 and 7 have been specified for edges WY and YX.
Un-Weighted Graph
In this, no weight will be specified for every edge. The following graph contains three vertices W, X, Y and three edges XW, WY, YX. It does not contain weight to its edge.
Cyclic Graph
It consists of cycles. It has an identical beginning and concluding vertex. In the following graph, both the starting and ending vertex is A.
Acyclic Graph
It does not contain any cycle or loop. In the following graph, there are a total of three vertices X, W and Y and two edges XW and WY. In this graph, the starting and ending vertices are also not the same. Also, it does not contain any cycles.
Dense Graph
It contains several edges closer to the highest possible number of edges. To represent it, an adjacency matrix can be used.
In the graph below, there are five vertices and a maximum of ten edges.
Sparse Graph
It contains several edges closer to the least possible number of edges. The adjacency list could be used to represent it.
The following graph consists of four edges (BA, AC, CD, DB ) and four vertices (B, A, C, D). As it contains four edges that are closer to the least number of edges. So, it is a sparse graph.
Complete Graph
It comprises distinct vertices linked by a distinctive edge. In this form of a graph, every single node is adjacent to all the other nodes. In this, if we have x number of nodes then edges will be x(x-1)/2.
Multi Graph
It consists of several edges between nodes. In the graph below, it can be observed that there are two edges between the nodes V and W . So, it is a multi-graph.
Implimentation of Graph
Following are the different techniques to implement a graph:
Adjacency Matrix
It is a two-dimensional matrix of size n into n which is represented in the form of ‘X[n][n]'.In this, ‘n’ refers to the number of vertices and it would be several rows and columns. Each row and column represent specific vertices. It is a symmetrical matrix as both rows and columns are of n size. We will write the entry in the matrix as either 1 or 0. If there exists an edge from row to column vertex then the matrix is filled with 1 entry. If there is no edge found from row to column vertex then the matrix is filled with 0 entry.
Example
To represent the graph by an adjacency matrix, we will have an n x n matrix and ‘n’ is the number of vertices in the graph. By looking at the graph, there are a total of five vertices so the order of the adjacency matrix will be 5 x 5.So, firstly we will write all the vertices as column-wise and row-wise. There will be five rows as well as five columns. While filling out the matrix, the diagonal elements will be written zero as there is no loop in it.
Now, we will check from row to column to determine whether an edge exists or not. If an edge is present between adjacent nodes then it would be marked as 1 in the matrix otherwise marked as 0. Sometimes there would be the weight of the edge in the graph. In such a case, if there exists an edge then its weight will be written in the matrix instead of 1.While no edge will be marked as 0 in this case.
Space complexity for this matrix is O(n2) because it contains an ‘n’ number of rows and columns.
Advantages of Adjacency Matrix
It has the following advantages:
Adding or removing an edge is very simple in this representation as it takes the order of one time 'O(1)'.
It is very simple to implement an adjacency matrix.
Disadvantages of Adjacency Matrix
It has the following disadvantages:
It takes more space.
Adding or removing a vertex is a very costly operation.
Adjacency List
As its name implies, it is in the form of a linked list. It is an array of linked lists. Each linked list shows vertices that are connected to the vertex assigned to the index of the array. Each vertex would maintain one linked list.
Example
To understand the adjacency list, let us take again the previous graph. So initially we will calculate the number of vertices or nodes. We have a total of five vertices. So we will establish an array list having five nodes. There would be one linked list for each node and it would contain an adjacent node to the corresponding node. Every element of the array will point toward a list that will possess all the adjacent nodes. Vertex A comprises two adjacent nodes B and D. So it will maintain one list that contains B and D. Vertex B comprises three adjacent nodes A, C and D. Now vertex C contains also three adjacent nodes B, D and E. Vertex D includes four adjacent nodes A, B, C and E. Then vertex E contains D and C nodes.
Space complexity using the adjacency list is O(n+2e). Where term 2e shows the edge is written two times.
Advantages of Adjacency List
It has the following advantages:
It saves a lot of space.
Its process of adding an edge and vertex is very time efficient.
Disadvantages of Adjacency List
It has the following disadvantages:
Its process of removing an edge and vertex is not time efficient.
If we have to look for the relationship among two vertices then this query is not very efficient.
Incidence Matrix
It is a matrix in the form of V into E.V signifies the overall number of vertices and E signifies the overall number of edges. An incidence matrix is an asymmetrical type of matrix in which several rows are V and the number of columns is equivalent to the number of edges. Each column represents that it is an edge that is connected between two vertices.
Example
To understand the incidence matrix, let us take an undirected graph. This graph comprises four vertices A, B, C and D. And there are five edges. To create an incidence matrix for this graph, all the vertices will be listed row-wise. While all edges will be listed column-wise. For each vertex, we will check all the edges that are connected with it. If the vertex is connected with the edge then it will be marked as 1 in the graph other marked as 0.
In the case of the directed graph, the direction will be mentioned in the graph. For all outgoing edge, entry will be marked as 1. For all incoming edge, entry will be marked as -1. For no edge, entry will be marked as 0.
Incidence List
It is a list where for every vertex we store a list of objects which represents the edges that were incident with that vertex. For a directed graph, an edge will be present only for one vertex. For an undirected graph, we store both outgoing and incoming edges.
Example
Let us take a directed graph to create an incidence list. It contains five nodes and seven edges. Firstly, we will list down all the nodes from A to E. Then, we will check outgoing edges for each node and then write them in the list. With each edge, we will also store the endpoint of that edge.
Applications of Graph
It is the following applications:
One of its applications is the worldwide website. While we open any article or post on a site, it links to a new page. This link to a new page can be considered as an edge. And when this new page opens, this can be considered as data. So, web pages are considered as vertices.
Another application of graphs is in google map. In google map, when we type a destination, it tries to find out the shortest destination. So, google map uses a graph algorithm to determine the shortest route.
Graphs are used for route planning mechanism in-flight networks. Flight Network is also an application of graphs. To travel distance, flights usually don't have much fuel. So flights have to stop at some airport. Then they have to find the shortest route that they can take to reach the destination. So, flight networks throw the data in the graph and then they find the shortest path.
Graphs also have applications in product recommendations. Various e-commerce websites store the product data in the form of a graph.
