= Neighbour enumeration
= Neighbor enumeration
{synonym}
<Neighbour enumeration> reports the <neighbours> of a specified <vertex>. For a <simple graph>, scan its <adjacency list> and report each entry. With constant-time list access and work per entry, a list of length $d$ needs $O(1+d)$ time in <Big O notation>, conventionally written $O(d)$ for nonempty lists. Use <vertex degree> for an <undirected graph> and <outdegree> for a <directed graph>. Obtaining the list reference can take constant time; consuming it requires visiting every entry.<Algorithms, 4th edition by Robert Sedgewick and others/Digraph.java>[Digraph.java, class documentation and adj: obtaining the collection versus iterating in time proportional to outdegree]{ref}
In our undirected example, enumerating $C$'s <neighbours> reads $A,B,D$: three entries. Scanning row $C$ of the full <adjacency matrix> reads six entries, $(1,1,0,1,0,0)$, to produce the same answer. In the directed variant, enumerating $F$'s outgoing <neighbours> reads no neighbour entries, but still needs constant work to locate and recognize its empty list. For a <multigraph>, scanning lists enumerates incident <edges> with multiplicity; reporting only distinct <neighbours> additionally requires removing repetitions.
For a short <time complexity> argument, each reported entry requires at least one output operation, and one scan suffices. Across all <vertices>, the undirected entry count is $\sum_{v\in V}\deg(v)=2|E|$ by the <handshaking lemma>; the directed count is $\sum_{v\in V}d^+(v)=|E|$. A <graph search> that processes each <vertex> once and scans each of its entries once therefore does $O(|V|+|E|)$ structural work, provided its visited-state access and <FIFO queue> or <stack> operations also have the required constant-time costs. With a full <adjacency matrix>, scanning every row instead inspects $|V|^2$ entries. This is how the representation enters the analysis of <breadth-first search> and <depth-first search>.
Back to article page
