Adjacency list

An adjacency list represents a graph by storing, for each vertex, a list of its neighboring vertices. It uses space proportional to the vertices and edges.

Adjacency: Adjacency is the relationship in which two vertices share an edge in a graph. Each stored neighbor records an adjacency between vertices.
Adjacency matrix: An adjacency matrix represents a graph with a table whose entries indicate whether vertex pairs share an edge. It offers faster edge-existence checks at the cost of space proportional to the square of the vertex count.
Breadth-first search: Breadth-first search explores a graph outward from a starting vertex, visiting vertices in increasing distance order. It scans each visited vertex's list to enqueue undiscovered neighbors.
Graph theory: Graph theory studies mathematical structures made of vertices connected by edges. Adjacency lists are a data representation for graphs.
Directed graph: A directed graph is a graph whose edges have a specified direction. Its lists record outgoing neighbors, so each directed edge has a source-specific entry.
Incidence matrix: An incidence matrix records which vertices are endpoints of which edges. It organizes graph relationships by edges rather than storing each vertex's neighbors.
Depth-first search: Depth-first search explores a graph by following one path as far as possible before backtracking. Its recursive or stack-based exploration follows entries in each adjacency list.
Vertex (graph theory): A vertex is a point in a graph that may be connected to other vertices by edges. An adjacency list stores one neighbor collection for each vertex.
Undirected graph: An undirected graph is a graph whose edges have no direction. Each edge usually appears in both endpoint lists.
Edge list: An edge list represents a graph as a collection of its edges, each specified by endpoint vertices. It stores edges directly but requires scanning them to find a vertex's neighbors.

Linked from 11 pages