What is Graph data structure?

A graph is a collection of nodes (vertices) and edges (connections) that represent pairwise relationships between nodes. Graphs are widely used to model various real-world systems, including social networks, transportation networks, computer networks, and more. Graphs can be classified into two main types based on the presence of direction in edges:

Undirected Graph

An undirected graph is a graph where the edges have no direction. The connections between nodes are bidirectional.

   A----B
   |    |
   |    |
   D----C

Directed Graph (Digraph)

A directed graph is a graph where the edges have a direction. The connections between nodes are unidirectional.

   A---->B
   |     |
   |     v
   D<----C

Graph Terminology

• Vertex (Node): A fundamental unit of a graph that represents an entity. It can store additional information (data).
• Edge (Arc): A connection between two vertices that represents a relationship or link.
• Degree of a Vertex: The number of edges incident to a vertex.
• Path: A sequence of vertices connected by edges.
• Cycle: A path where the first and last vertices are the same.
• Connected Graph: A graph where there is a path between any two vertices.
• Weighted Graph: A graph where each edge has an associated weight/cost.
• Sparse Graph: A graph with relatively few edges compared to the number of vertices.
• Dense Graph: A graph with many edges, close to the maximum possible.

Graph Representation

There are multiple ways to represent a graph in memory. The two common representations are:

Adjacency Matrix

A 2D matrix where each cell (i, j) represents the presence or absence of an edge between vertices i and j.

       A B C D
    A  0 1 0 1
    B  1 0 1 0
    C  0 1 0 1
    D  1 0 1 0

Adjacency List

A collection of linked lists or arrays where each list represents the neighbors of a vertex.

   A -> B -> D
   B -> A -> C
   C -> B -> D
   D -> A -> C

Example of an Undirected Graph

   A----B
   |    |
   |    |
   D----C

Example of a Directed Graph

   A---->B
   |     |
   |     v
   D<----C

Graphs are fundamental data structures in computer science and are used in various algorithms, such as searching, shortest path finding, and cycle detection. Understanding graphs and their representations is crucial for solving complex real-world problems in computer science and network analysis.