Graph Basics: Vertices, Edges, and Adjacency

A Graph is the most versatile non-linear data structure in computer science. While trees enforce strict parent-child hierarchies with no cycles, graphs place no restrictions on how nodes connect.

Formal Definition of a Graph

A Graph G is formally defined as an ordered pair:

G = (V, E)

• V: A set of Vertices (also called Nodes), representing entities (users, airports, web pages).
• E: A set of Edges (also called Links or Arcs), connecting pairs of vertices.

Copy code    ( A ) ---------- ( B )
      |                |
      |                |
      |                |
    ( C ) ---------- ( D )

Essential Graph Terminology

1. Adjacent (Neighbors): Two vertices connected directly by an edge (A and B are adjacent).
2. Degree of a Vertex:
   • In an undirected graph: total number of edges connected to the vertex.
   • In a directed graph: In-Degree (incoming edges) and Out-Degree (outgoing edges).
3. Path: A sequence of edges connecting a sequence of vertices (e.g., A → B → D).
4. Cycle: A path that starts and ends at the same vertex (A → B → D → C → A).
5. Connected Graph: An undirected graph where there is a valid path between every pair of vertices.
6. Disconnected Graph: A graph with isolated components or nodes unreachable from one another.

Graph Classification

Copy code                         Graphs
                        /      \
                Undirected    Directed (Digraph)
                (Two-way)        (One-way arrows)
                 /    \           /        \
          Unweighted Weighted   Unweighted Weighted

• Undirected: Edges are bidirectional (e.g., mutual friendships on Facebook).
• Directed (Digraph): Edges have direction (e.g., Twitter/X followers, hyperlinks on the web).
• Weighted: Edges carry numerical values representing distance, cost, latency, or toll.

Summary

• Graphs model arbitrary networks of relationships (G = (V, E)).
• Vertices represent entities; edges represent connections.
• Graphs can be directed/undirected, cyclic/acyclic, and weighted/unweighted.