What Is a Graph?
A graph is a mathematical structure G = (V, E) made of a set of vertices (also called nodes) V and a set of edges E that connect pairs of vertices. Graphs model relationships: cities linked by roads, people linked by friendships, web pages linked by hyperlinks, or tasks linked by dependencies.
Directed vs Undirected
In an undirected graph an edge {u, v} has no direction: if u connects to v, then v connects to u. In a directed graph (digraph) an edge (u, v) points one way, from u to v, and does not imply an edge back. Twitter 'follows' are directed; Facebook 'friendships' are undirected.
Weighted vs Unweighted
In a weighted graph each edge carries a numeric weight (cost, distance, capacity, time). In an unweighted graph every edge counts equally, which is the same as every weight being 1. Shortest-path meaning changes accordingly: fewest edges vs least total weight.
Core Terminology
Degree: the number of edges incident to a vertex (in-degree and out-degree for digraphs)
Path: a sequence of vertices connected by edges
Cycle: a path that starts and ends at the same vertex
Connected: every pair of vertices has a path between them
Adjacent: two vertices joined by an edge
Representing an Edge in Code
type Edge struct {
From int
To int
Weight int // 1 for unweighted graphs
}
type Graph struct {
Vertices int
Edges []Edge
Directed bool
}Dense vs Sparse
A graph is dense when the number of edges is close to the maximum possible and sparse when it is far below. A complete undirected graph on n vertices has n(n-1)/2 edges. The handshake lemma states the sum of all vertex degrees in an undirected graph equals 2|E|, since every edge contributes to two endpoints.