Graphs

A Graph is a non-linear data structure consisting of vertices and edges. The vertices are sometimes also referred to as nodes and the edges are lines or arcs that connect any two nodes in the graph. More formally, a Graph is composed of a set of vertices (V) and a set of edges (E). The graph is denoted by G (E, V).

image

Types of Graphs

There are several types of graphs in data structures:

image

1. Undirected Graphs: Edges have no direction, i.e., the edges do not have arrows indicating the direction of traversal.

2. Directed Graphs: Edges have a direction, i.e., the edges have arrows indicating the direction of traversal.

3. Weighted Graphs: Edges have weights or costs associated with them.

4. Unweighted Graphs: Edges have no weights or costs associated with them.

5. Complete Graphs: Each vertex is connected to every other vertex.

6. Bipartite Graphs: The vertices can be divided into two disjoint sets such that every edge connects a vertex in one set to a vertex in the other set.

7. Trees: A connected graph with no cycles.

8. Cycles: A graph with at least one cycle.

9. Sparse Graphs: A graph with relatively few edges compared to the number of vertices.

10. Dense Graphs: A graph with many edges compared to the number of vertices.

11. Finite Graphs: A graph with a finite number of vertices and edges.

12. Infinite Graphs: A graph with an infinite number of vertices and edges.

13. Trivial Graph: A graph with only one vertex and no edges.

14. Multi Graph: A graph which may have multiple edges (also called parallel edges), i.e., edges that have the same end nodes. Thus, two vertices may be connected by more than one edge.

15. Null Graph: A graph is known as a null graph if there are no edges in the graph.

Operations of the Graphs in data structure

There are several operations that can be performed on graphs in data structures:

• Add Vertex: This operation adds a vertex to the graph.

• Add Edge: This operation adds an edge between two vertices in the graph.

• Remove Vertex: This operation removes a vertex from the graph.

• Remove Edge: This operation removes an edge between two vertices in the graph.

• Query: This operation checks if there is an edge between two vertices.

• Neighbors: This operation lists all vertices connected to a given vertex.

• Search: This operation searches for an entity in the graph.

• Traversal: This operation traverses all the nodes in the graph.

Complexity Table

Operation	Adjacency Matrix	Adjacency List
Access	O(1)	**O(
Search	**O(	V
Insertion	**O(	V
Deletion	**O(	V