Introduction to Graphs

A Graph is a non-linear data structure that consists of a finite set of vertices (or nodes) and a set of edges connecting them. It is used to model pairwise relations between objects.

A graph is mathematically represented as: $$G = (V, E)$$ Where:

• $V$ is a finite set of vertices (also called nodes).
• $E$ is a finite set of edges (also called arcs or links), which are ordered or unordered pairs of vertices (u, v).

Key Components of a Graph

1. Vertices (Nodes): The fundamental units/points of a graph (e.g., cities, web pages, users in a social network).
2. Edges: The lines or connections between nodes.
   • An edge (u, v) represents a link from vertex u to vertex v.
   • Edges can be weighted (containing a value/cost, like distance or latency) or unweighted.

Real-Life Applications

• Social Networks: Vertices represent users, and edges represent relationships (friendships on Facebook, connections on LinkedIn).
• Navigation/Maps: Vertices represent intersections or cities, and edges represent roads with weights indicating distances or travel times (e.g., Google Maps GPS).
• Web Pages (Google PageRank): Vertices represent web pages, and directed edges represent hyperlinks between them.
• Network Routing: Represents routers (vertices) and data links (edges).

Directed and Undirected Graphs

1. Directed Graphs (Digraphs)

In a directed graph, edges have a specific direction. The edge (u, v) is directed from u to v and is not equivalent to (v, u).

2. Undirected Graphs

In an undirected graph, edges are bidirectional (directionless). An edge between u and v means you can traverse from u to v and from v to u ((u, v) is equivalent to (v, u)).

Graph Representations

The two most common ways to represent a graph in memory are:

1. Adjacency Matrix
2. Adjacency List

1. Adjacency Matrix

An Adjacency Matrix is a 2D array of size $V \times V$ (where $V$ is the number of vertices).

• Let the 2D array be adj[][].
• A value of adj[i][j] = 1 indicates that there is an edge from vertex i to vertex j.
• A value of adj[i][j] = 0 indicates no edge exists.
• For a weighted graph, adj[i][j] = w, where w is the weight of the edge.

Matrix representation for the Undirected Graph above:

Complexity Analysis

• Space Complexity: $O(V^2)$
• Adding an edge: $O(1)$
• Removing an edge: $O(1)$
• Querying edge existence (u -> v): $O(1)$
• Adding a vertex: $O(V^2)$ (requires resizing the 2D array)

Advantages

• Very easy to implement and understand.
• Querying if an edge exists between two vertices takes constant time $O(1)$.
• Removing an edge takes $O(1)$ time.

Disadvantages

• Consumes $O(V^2)$ space, which is highly inefficient for sparse graphs (graphs with few edges relative to vertices).
• Adding a vertex is slow ($O(V^2)$) as it requires allocating a new matrix and copying existing data.