Graph Data Structure

A Graph is a non-linear data structure consisting of vertices and edges. The vertices are called nodes, and the edges are lines connecting any two nodes in the graph.

Basic components of a graph:

1. Vertex (Node): Represents a point in the graph.
2. Edge: Represents a connection between two vertices.

Graph Representation:

• Adjacency Matrix

Adjacency Matrix

• Adjacency List

Adjacency List

Basic operations on Graph:

• Insertion of Nodes/Edges in the graph — Insert a node into the graph.
• Deletion of Nodes/Edges in the graph — Delete a node from the graph.
• Searching — Search for an entity in the graph.
• Traversal — Traversing all the nodes in the graph.

Graph Traversal:

• Depth-First Search (DFS)
• Breadth-First Search (BFS)

Shortest Path Algorithms:

• Dijkstra’s Algorithm
• Bellman-Ford Algorithm
• Floyd-Warshall Algorithm

Minimum Spanning Tree (MST):

• Prim’s Algorithm
• Kruskal’s Algorithm

Topological Sorting:

• Kahn’s Algorithm
• Depth-First Search (DFS) based approach