Directed graph node neighbors

14
votes

In a directed graph, what is a definition of a node neighbor ?

To be more specific, in the graph below, which nodes are considered to be neighbors of node 0?

enter image description here

Cracking the coding interview seems to suggest that both 1 and 2 are neighbors of 0, but it doesn't state it clearly and I can't find a proper definition online.

EDIT:

My confusions arises from this specific passage:

In the adjacency matrix representation, you will need to iterate through all the nodes to identify a node's neighbors.

This seems to imply that 2 is considered 0's neighbor, otherwise you just need to go through 0's row to find its neighbors. But it never says this clearly.

2
algorithmdata-structuresgraph
I agree with you that 2 is considered 0's neighbor IF the definition just requires that there is an edge between 2 and 0 (disregarding direction). But this is a great question: can a node be the neighbor of a node that is not it's neighbor? Certainly the adjacency matrix would label 2 connecting to 0 but also has 0 NOT connecting to 2. I haven't found a clear answer in a quick search, so I'm curious too. - Carser
I would not mind that much. Usually such stuff is always defined when used in a context, and then its clear. When it's not directly clear from the context, people are more specific and talk of ingoing and outgoing neighbors. Or predecessors and successors etc. - Zabuzard

2 Answers

12
votes

In a directed graph, "neighbor" is rarely used without qualification (and when it is, at least some would argue that it's probably a mistake). Usually you speak of out-neighbors (or outgoing neighbors)--vertices that have an edge from a vertex, and in-neighbors (or incoming neighbors)--vertices that have an edge to the vertex.

Likewise, where you'd speak of a neighborhood in an undirected graph, in a digraph you'd speak of an outgoing neighborhood or an incoming neighborhood.

2
votes

In a digraph each directed edge has a tail and a head, respectively where the edge departs and where it arrives thus forming in-neighbors and out-neighbors of a node N. All nodes where the edge arrives, departing in N, are out-neighbors. All nodes where an edge departs, arriving in N, are in-neighbors.

The out-neighbors of a node N are all the nodes in the singly linked list belonging to that element N residing in the array (or hashmap) of the ALR (adjacency list representation) that defines the graph.

In an adjacency matrix, one must agree whether to place the tail node per row and the head node per column or vice versa. The body of the (usually asymmetric) matrix contains the relevant values defining in or out neighbors.