For the graph implementation, following data structures are used.

In sequential representation, Adjacency matrix is used.
In Linked representation, Adjacency list is used.

In graph implementation, various data structures are commonly used to represent the graph and facilitate operations on it efficiently. Some of the key data structures used in graph implementation include:

Adjacency Matrix: A 2D array where the entries indicate whether an edge exists between the vertices. This approach is suitable for dense graphs (graphs with many edges).
Adjacency List: A collection of lists or arrays where each vertex has a list of its neighboring vertices. This approach is more memory-efficient for sparse graphs (graphs with fewer edges).
Edge List: A list of tuples or objects representing edges, each containing the pair of vertices connected by that edge along with any associated weight or attributes.
Hash Map (Dictionary): In conjunction with other data structures, a hash map can be used to efficiently store and retrieve information about vertices and edges.
Priority Queue (Heap): Used in algorithms such as Dijkstra’s shortest path algorithm and Prim’s minimum spanning tree algorithm to efficiently select the next vertex to explore based on certain criteria.
Union-Find (Disjoint Set): Used in algorithms such as Kruskal’s minimum spanning tree algorithm to efficiently determine whether adding an edge between two vertices would create a cycle in the graph.

The choice of data structure depends on the specific requirements of the graph and the operations to be performed on it. For example, if the graph is dense and edge lookups are frequent, an adjacency matrix might be more suitable. Conversely, if the graph is sparse and memory efficiency is a concern, an adjacency list might be preferable.