Types of Graph in Data Structure with Examples

Let’s see types of graph in data structure:

Undirected Graphs

Undirected graphs, distinguished by their bidirectional edges, model relationships where the direction of interaction is not specified. Traveling between nodes is possible in both directions, reflecting the reciprocal nature of these relationships.

Directed Graphs

Directed graphs, also known as digraphs, are a type of graph where edges have a specific direction, typically represented by arrows. They excel at modeling relationships where the direction of interaction matters.

Weighted Graphs

A weighted graph is a type of graph in data structure where each edge is assigned a numerical weight. These weights often represent distances, costs, or some other measure associated with the edges.

Unweighted Graphs

Unweighted graphs have edges without assigned numerical values, treating all connections equally. They are used for representing basic relationships and connectivity patterns.

Bipartite Graphs

A bipartite graph is a type of graph in data structure whose vertices can be divided into two disjoint sets, such that all edges connect vertices from different sets.

Trees

A tree is a hierarchical data structure consisting of nodes connected by edges, with a unique starting node called the root. Each node, except the root, has one parent and zero or more child nodes. The nodes without children are called leaves.

Cycles

A cycle in a graph is a sequence of vertices and edges that starts and ends at the same vertex, forming a closed loop.

Sparse Graphs

Sparse graphs are graphs where the number of edges is significantly smaller than the maximum possible number of edges. In sparse graphs, nodes have fewer connections relative to the total number of nodes.

Dense Graphs

Dense graphs are characterized by a high number of edges, approaching the maximum possible number of edges for the given number of vertices. In dense graphs, most nodes are interconnected, resulting in a close-to-complete connectivity pattern.

Different Types of Graph in Data Structure

Graphs in data structure can be of various types and be used based on the requirements of the application.

Finite Graph

A finite graph is a type of graph in data structure which has a finite (countable) number of vertices and edges, i.e. If a graph G=(V,E) consists of a finite number of vertices and edges denoted by V and E respectively, then the graph is a finite graph.

Infinite Graph

An infinite graph is a type of graph in data structure which has infinite number of vertices and edges, i.e. If a graph G=(V,E) consists of an uncountable number of vertices or edges denoted by V and E respectively, then the graph is an infinite graph.

Trivial Graph

A finite graph G=(V,E) is said to be trivial if it has only one vertex. Since such a graph has only one vertex, it does not have any edges.

Simple Graph

A simple graph G=(V,E) is a type of graph in data structure in which a pair of vertices V1 and V2 are connected by only one edge. In such a graph, since least cost is a single value, there will be only one edge connecting 2 locations.

Multi Graph

A graph G=(V,E) which contains more than 1 edge or a loop (not self-loop) between 2 vertices is called a multi graph. In such a graph, we can find more than one routes (edges) connecting 2 places (vertices), some of which could be longer, others shorter.

• Parallel Edges: Parallel edges in a graph refer to multiple edges between the same pair of vertices.
• Loop: A loop in a graph occurs when an edge connects a vertex to itself.

Null Graph

A null graph G=(V,E) is a type of graph in data structure which has only isolated vertices, ie. such a graph does not have any edges connecting the vertices.

If we consider the 2 locations to be vertices, then due to no route between them, there would be no edges connecting them.

Complete Graph

A graph G=(V,E) is said to be complete if each vertex in the graph is adjacent to all of its vertices, i.e. there is an edge connecting any pair of vertices in the graph.

An undirected complete graph with n vertices will have n(n-1)/2 edges, while a directed complete graph with n vertices will have n(n-1) edges. The following figure shows graphs Ki where i represents the number of vertices.

We can clearly see how all the vertices in each graph have an edge connecting each other.

Pseudo Graph

A pseudo graph G=(V,E) is a graph that contains self loop and multiple edges. Consider the folllowing pseudo graph abcd. Between a and b, there exist 2 paths. b also contains a self loop. Thus, we can say that abcd is a pseudo graph.

Regular Graph

A graph G=(V,E) is said to be regular if every vertex V of the graph is adjacent or connected to the same number of vertices. All complete graphs are regular but it isn't the same vice versa. Consider the following example.

Bipartite Graph

A graph G=(V,E) is called a bipartite graph if its vertex set can be partitioned into two non-empty disjoint subsets A and B such that every edge (a,b) connects a vertex from A to B or vice versa. In bipartite graphs, there would be no edge that connects vertices from the same set.

Further they are added to their respective set and the connections can be shown in the image to the right.

Labelled Graph

A labelled graph G=(V,E) is one in which the vertices and edges of a graph are labelled with a name, data, or weight.

Digraph Graph

A digraph, also known as a directed graph, is one in which the vertices are ordered in a particular sequence. Thus, the edges are usually represented by arrows that point in a particular direction.

In such a graph, changing the direction of arrows can alter the meaning of the graph. In the following figure

Subgraph

A graph in data structure is said to be a subgraph if it is a part of another graph. In the following example, graphs H1, H2 and H3 are subgraphs of the graph G.

Connected or Disconnected Graph

A unidirected graph is connected if there is a path from any vertex to any other vertex, or any vertex is reachable from any other vertex. A connected graph of n vertices has at least n-1 edges.

A disconnected graph is one that is not connected, i.e. at least one of the vertices is not connected to any other vertex.

Cyclic Graph

A graph that has one or more cycles is called a cyclic graph. A jogging path around the city that connects various landmarks could be considered as a cyclic graph. In the following figure, BCDE represents a cyclic graph since it consists a cycle denoted by BCED.

Types of Subgraph

Vertex Disjoint Subgraph

A subgraph with no common vertex is called a vertex disjoint subgraph. Any two graphs A = (V1, E1) and B = (V2, E2) are said to be vertex disjoint of a graph G = (V, E) if V1(A) intersection V2(B) = null.

Since vertices in a vertex disjoint graph cannot have a common edge, a vertex disjoint subgraph will always be an edge disjoint subgraph. In the above example, since subgraph EFG and ABCD have no vertex in common, they are said to be vertex disjoint subgraphs.

Edge Disjoint Subgraph

A subgraph with no common edge is called an edge disjoint subgraph. A subgraph is said to be edge disjoint if E1(A) intersection E2(B) = null. In the above example, since graphs ABCD and BEFG have no edge in common, they are said to be edge disjoint subgraphs.

Spanning Subgraph

A spanning subgraph of a graph is a subgraph that includes all the vertices of the original graph. It is formed by selecting a subset of edges from the original graph while ensuring that the selected edges form a tree or a forest.

Advantages of Graphs

• Graphs, with their visual simplicity and versatility, shine in data representation.
• Complex relationships and trends are unraveled, patterns emerge with clarity.
• Connections between entities, from social networks to roadmaps, are effectively captured.
• Visualizations spark insights, guiding decision-making and problem-solving.
• Graphs, a powerful tool for communication and analysis, empower understanding.

Disadvantages of Graphs

• Graphs can become cluttered and difficult to interpret when dealing with large datasets.
• Certain types of relationships, such as those involving qualitative data, are not well-suited for graph representation.
• Identifying specific patterns or anomalies can be challenging in complex graphs.
• Misinterpretation of graph elements can lead to erroneous conclusions.
• Careful selection of the appropriate graph type and clear labeling are crucial for effective communication.