liveBook · Manning

Node

As explained in The Coder Cafe

A vertex is an individual element in a graph that may be connected to other vertices by edges.

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

How The Coder Cafe covers it

How deep it goes
Defines vertices and explains their representation and processing, without developing a standalone vertex implementation.
Examples
Uses social-network connections, network reachability, dependency ordering, and source-to-sink flow paths.
What it assumes
Defines vertices and edges before using in-degree and flow-network terminology.
What you can do after
Evaluate/understand it by comparing vertex representations and tracing how topological sort processes vertices.
How it connects
Connects vertices to edges, adjacency matrices, adjacency lists, in-degree, topological sort, and flow networks.

Also explained in

Compare how 20 books explain node →

Related concepts

This explainer was generated by Manning's knowledge graph from the text of The Coder Cafe. The section links point to the parts of the book it draws on.