What is a Graph? Vertices and Edges
You'll learn: The fundamental building blocks of graphs—vertices (nodes) and edges (connections)—and how they form one of the most versatile data structures in computer science.
The Core Idea
A graph is a data structure consisting of two components:
- Vertices (also called nodes): Individual points or entities
- Edges: Connections or relationships between pairs of vertices
Think of a graph like a social network: each person is a vertex, and each friendship is an edge connecting two people. Or imagine a map where cities are vertices and roads are edges connecting them.
Visual Understanding
In a simple graph with 4 vertices (A, B, C, D):
- The vertices are the labeled points: A, B, C, D
- The edges are the lines connecting them: A-B, B-C, C-D, A-D
Unlike trees (which you've studied), graphs have no restrictions on connections. A vertex can connect to many others, connections can form cycles, and there's no concept of a "root" or hierarchy by default.
Key Differences from Trees
While trees are a special type of graph, general graphs are more flexible:
- Trees have exactly N-1 edges for N nodes; graphs can have any number
- Trees are always connected; graphs can have isolated vertices
- Trees have no cycles; graphs often do
Common Graph Terminology
- Adjacent vertices: Two vertices connected by an edge
- Degree: The number of edges connected to a vertex
- Path: A sequence of edges connecting one vertex to another
Key Takeaway: A graph is a collection of vertices (nodes) connected by edges (relationships), forming one of the most general and powerful ways to represent interconnected data.