Last Updated on January 9, 2023 by Prepbytes
A Graph is a non-linear data structure. It consists of vertices and edges. The vertices are sometimes also referred to as nodes, the edges are lines connecting any two nodes in the graph. The graph is denoted by G(E, V).
Components of a Graph:
A graph consists of vertices and Edges:-
- Vertices: Vertices are the basic units of the graph. Sometimes, vertices are also known as vertex or nodes.
- Edges: Edges are used to connect two nodes of a graph.
Types of Graphs:
There are many types of graphs based on the types of edges and vertices.
1. Finite Graphs
A Finite graph is a type of graph having a finite number of vertices and a finite number of edges.
2. Infinite Graph:
An Infinite graph is a type of graph having an infinite number of vertices and an infinite number of edges.
3. Trivial Graph:
A Trivial graph is a type of graph containing only one vertex and no edge.
4. Simple Graph:
A simple graph is a type of graph that only contains only one edge between the pair of vertices.
5. Multi Graph:
A Multi graph is a type of graph that contains parallel edges but doesn’t contain any self-loop is called a multigraph.
6. Null Graph:
A Null graph contains no edges between its vertices i.e isolated vertices with no edges connecting any pair of vertices.
7. Complete Graph:
A complete graph is a type of simple graph that contains direct edges from every vertex to all other vertices. A complete graph is also called Full Graph.
10. Bipartite Graph:
A Bipartite graph is a graph whose vertices can be divided into two independent sets, U and V such that every edge (u, v) either connects a vertex from U to V or a vertex from V to U. In other words, for every edge (u, v), either u belongs to U and v to V, or u belongs to V and v to U. We can also say that there is no edge that connects vertices of same set.
11. Labeled Graph:
If the vertices and edges of a graph are labeled with name, date, or weight then it is called a labeled graph. It is also called Weighted Graph.
12. Connected or Disconnected Graph:
A Graph is said to be connected if any pair of vertices of a graph is reachable from one another, in other words a graph is said to be connected if there exists at least one path between each and every pair of vertices in a graph, otherwise, it is disconnected.
13. Cyclic Graph:
A Cyclic graph is a type of graph consisting of n vertices where (n> = 3). For example, If there are 4 vertices (n=4) V1, V2, V3, V4 and there are edges connecting (V1, V2), (V2, V3), (V3, V4), (V4, V1) are called cyclic graph.
In the above graph A, B, C are 3 vertices and there are 3 edges connecting them. This type of graph is know as cyclic graph because if we start moving in one direction from a given node then we will reach that same node again because of cyclic path.
Application of graph in data structure
- Graphs are used in social networking sites. The users act as nodes and the connection between them acts as edges.
- Graphs are used in Google maps to find the shortest route between two locations.
- Graphs are also used in airlines system for effective route optimization.
- In electrical circuits, graphs can be used to represent circuit points as nodes and wires as edges.
- Graphs are used in solving puzzles with only one solution, such as mazes.
- Graphs are used in computer networks for Peer to peer (P2P) applications.
- In an operating system, graphs are used as resource allocation graphs.
In this article, we have discussed what is graph in data structure, types of graph in data structure and the application of graph in data structure.