Graph Data Structure

A Graph is a non-linear data structure that represents a set of objects (called vertices or nodes) connected by links (called edges or arcs). Unlike linear structures (arrays, linked lists) or hierarchical structures (trees), graphs allow for complex, many-to-many relationships.

Think of a graph like a map of a city. The cities are the vertices, and the roads connecting them are the edges. You can travel from one city to another via multiple paths, and there can be multiple ways to reach the same destination.

Mathematical Definition

Formally, a graph G is defined as:

G = (V, E)

Where:

• V = Set of vertices (nodes)
• E = Set of edges (connections between nodes)

Example

Consider a graph G defined as:

V = {A, B, C, D, E}
E = {(A,B), (A,C), (A,D), (B,D), (C,D), (B,E), (E,D)}

This graph has 5 vertices and 6 edges.

        A
       /|\
      B C D
      |\ /
      E

(A visual representation showing connections)

Real-World Applications of Graphs

Graphs are everywhere! Here are some common real-world applications:

Fundamental Graph Terminology

1. Vertex (Node)

A vertex is a fundamental unit of a graph, representing an entity or a point.

• Example: In a social network, each person is a vertex.
• Vertices are often labeled or numbered for identification (like A, B, C or 1, 2, 3).

2. Edge (Arc)

An edge is a connection between two vertices.

• Undirected Edge: A two-way connection (represented as (u, v)). Example: A friendship on Facebook.
• Directed Edge: A one-way connection (represented as u → v). Example: A follower on Twitter.
• Edges can also be:
  • Unweighted: Only presence or absence matters.
  • Weighted: Each edge has a value (weight, cost, distance, capacity).

3. Degree of a Vertex

The degree of a vertex is the number of edges connected to it.

For Undirected Graphs:

• Degree = Number of edges incident on the vertex.
• Example: Vertex v connected to vertices a, b, c has degree 3.

For Directed Graphs:

• In-degree: Number of edges coming into the vertex.
• Out-degree: Number of edges going out from the vertex.
• Example: If vertex v has 2 incoming edges and 3 outgoing edges:
  • In-degree = 2
  • Out-degree = 3

4. Adjacent Vertices (Neighbors)

• Two vertices are adjacent if they are connected directly by an edge.
• The neighbors of a vertex are all vertices adjacent to it.
• Example: In an undirected graph, if (v, w) is an edge, then v and w are neighbors.

5. Path

• A path is a sequence of vertices where each consecutive pair is connected by an edge.
• The length of a path is the number of edges in the path.
• Example: Path v₁ → v₂ → v₃ → v₄ has length 3.

6. Simple Path

• A simple path is a path that does not repeat any vertices.
• Important in avoiding cycles when finding the shortest path.

7. Cycle (Circuit)

• A cycle is a path where the first and last vertices are the same.
• The cycle length is the number of edges involved.
• Example: v₁ → v₂ → v₃ → v₁ forms a cycle of length 3.

8. Connected Graph

• In an undirected graph, a graph is connected if there exists a path between every pair of vertices.
• If not, the graph is disconnected and has multiple connected components.

9. Strongly Connected Graph (Directed)

• A directed graph is strongly connected if for every pair of vertices u and v, there is a path from u to v and from v to u.

10. Weakly Connected Graph (Directed)

• A directed graph is weakly connected if its underlying undirected graph is connected (ignoring edge directions).

11. Subgraph

• A graph G' = (V', E') where V' ⊆ V and E' ⊆ E.
• Essentially a smaller graph contained within a larger graph.

12. Weighted Edge

• An edge that has a numerical value (weight).
• Used to represent costs, distances, or capacities.
• Example: In a road network, the weight can be the distance between cities.

13. Self-Loop

• An edge that connects a vertex to itself (v → v).
• Usually avoided in simple graphs but allowed in some specialized structures.

14. Multiple Edges (Parallel Edges)

• When two vertices are connected by more than one edge.
• Allowed in multigraphs, not in simple graphs.

15. Complete Graph

• A graph where every pair of distinct vertices is connected by a unique edge.

• Number of edges in an undirected complete graph with n vertices:

  text

  Number of Edges = n(n - 1) / 2

• Example: A complete graph with 4 vertices has 4*3/2 = 6 edges.

16. Bipartite Graph

• A graph whose vertices can be divided into two disjoint sets U and V, such that every edge connects a vertex in U to one in V.
• No edges between vertices in the same set.

17. Tree

• A connected acyclic undirected graph.
• Has n vertices and n-1 edges.
• A special type of graph with a hierarchical structure.

18. Degree Sequence

• The list of degrees of all vertices in a graph.
• Used to analyze graph properties.

19. Bridge (Cut-edge)

• An edge which, when removed, increases the number of connected components.
• It disconnects the graph.

Types of Graphs

1. Directed vs. Undirected

2. Weighted vs. Unweighted

3. Simple vs. Multigraph

Graph Representation

1. Adjacency Matrix

A 2D array of size V × V where matrix[i][j] = 1 if an edge exists between i and j, else 0.

Advantages:

• Easy to implement
• O(1) time to check if an edge exists
• Good for dense graphs

Disadvantages:

• O(V²) space, even for sparse graphs
• Expensive for traversal

2. Adjacency List

An array of linked lists, where each list stores the neighbors of a vertex.

Advantages:

• O(V + E) space, efficient for sparse graphs
• Easy to traverse

Disadvantages:

• O(V + E) time to check if an edge exists
• Slightly more complex to implement