Adjacency list

The adjacency list (or neighbor list ) is a way to store the graph in the computer. It is represented in its simplest form by a singly linked list of all nodes of the graph, where each node ( in undirected graphs ) or successor has a list of all its neighbors ( in directed graphs ). Multiplicities of the edges, node weights, and edge weights are usually stored in attributes of the individual elements. Depending on the problem, it may be necessary to place a singly linked list using a doubly linked list and the list of successors to manage in a directed graph in addition a list of predecessors. She is in practice usually the canonical representation of graphs, as can many graph-theoretical problems can be solved only with adjacency lists in linear time.

Definition

With a set of nodes and a set of edges a graph is given ( without multiple edges). That is to say it is and it is precisely when the graph contains an edge from to. At each node, adjacency is defined as

Ie for each node is the list of all neighbors (or successor ).