= Adjacency list edge conventions
For a <directed graph>, store $v$ in $\mathrm{Adj}[u]$ for the <edge> $u\to v$. The reverse <edge> $v\to u$ is separate and is stored only if it exists. Consequently, list length is <outdegree>, not <indegree>, and each directed <edge> contributes one entry in total. An incoming-list index is additional storage.<Algorithms, 4th edition by Robert Sedgewick and others/Digraph.java>[Digraph.java, addEdge, adj and outdegree: one entry in the tail's collection; indegree is maintained separately]{ref}
Orient the seven <edges> of our example from earlier to later labels. The resulting <directed graph> has
$$
\begin{aligned}
\mathrm{Adj}[A]&=(B,C), & \mathrm{Adj}[B]&=(C), & \mathrm{Adj}[C]&=(D),\\
\mathrm{Adj}[D]&=(E,F), & \mathrm{Adj}[E]&=(F), & \mathrm{Adj}[F]&=().
\end{aligned}
$$
There are now seven entries, with <outdegrees> $(2,1,1,2,1,0)$. In particular, $F$ needs an empty list even though it is reached from $D,E$: incoming <edges> do not make $F$'s outgoing list nonempty. Replacing each directed <edge> by an <undirected graph> connection would lose this distinction.
Our running <simple graph> excludes <self-loops> and repeated <edges>. If those restrictions are relaxed, specify how the <adjacency list> encodes them. Here an undirected <self-loop> at $u$ contributes two copies of $u$ to $\mathrm{Adj}[u]$, matching its contribution of two to the <degree of a vertex>. A directed <self-loop> contributes one copy, and one each to <outdegree> and <indegree>. Distinct parallel <edges> retain distinct entries; a <multigraph>'s list length can therefore exceed its number of distinct <neighbours>.<Algorithms, 4th edition by Robert Sedgewick and others/Graph.java>[Graph.java, class documentation: parallel edges and two-entry undirected self-loop convention; addEdge applies both insertions even when v equals w]{ref}<Algorithms, 4th edition by Robert Sedgewick and others/Digraph.java>[Digraph.java, class documentation and addEdge: parallel edges permitted; a directed self-loop adds one outgoing entry and increments indegree once]{ref}
For example, add one undirected <self-loop> at $A$ to the seven-<edge> example. Its list becomes $(B,C,A,A)$, the <vertex degree> of $A$ becomes four, and the total entry count becomes sixteen for eight <edges>. If an application instead stores a <self-loop> once, it must account for its doubled undirected <vertex degree> separately. In a <weighted graph>, an entry can be an <ordered pair> $(v,w)$ meaning destination $v$ and weight $w$; the weight belongs to the <edge>, not to the destination <vertex>.
Back to article page
