A node, also called a vertex, is an individual element of a graph. Edges connect pairs of vertices. A vertex might represent a person in a social network or a machine in a computer network; the edges describe the relationships between them. section 1.3
What an edge means depends on the graph. A directed edge has a direction, as when one person follows another. An undirected edge represents a mutual connection. Edges can also carry weights, such as travel time between cities. Whether one vertex can be reached from another determines whether the graph is connected. section 1.3
Two common representations make different tradeoffs when looking up a connection between vertices:
- An adjacency matrix records whether an edge goes from vertex i to vertex j. An edge lookup takes O(1) time, but the matrix uses O(v²) space for v vertices, including unused entries in a sparse graph. section 1.3
- An adjacency list stores the edges associated with each vertex. It uses O(v + e) space for v vertices and e edges; finding a particular edge takes O(d) time, where d is the vertex’s degree. section 1.3
A linked-list node is a related but distinct use of the word. It holds data and a pointer to the next node, rather than simply naming a vertex in a graph. Linked-list nodes need space for those pointers, and reaching a later node requires following them from the start unless its location is already known. section 1.1
Vertices in algorithms
In a topological sort, each vertex has an in-degree: its number of incoming edges. Vertices with zero in-degree enter a queue; processing one reduces the in-degrees of vertices reached by its outgoing edges. This produces an ordering for a directed acyclic graph. In a flow network, vertices instead mark places where flow enters or exits, including the source and sink; a path is a sequence of connected vertices. section 1.4.1 section 1.4.2



















