Figure: A Beginner's Guide to the Basic Concepts and Adjacency List Representation of Graphs

A graph consists of vertices (nodes) and edges (connections). Vertices are the basic units, and edges can be directed (digraph) or undirected. Weighted graphs have edges with weights (e.g., distances), while unweighted graphs only retain connection relationships. The adjacency list is an efficient representation method that solves the space waste problem of the adjacency matrix in sparse graphs (where the number of edges is much less than the square of the number of vertices). Its core is that each vertex stores a list of directly connected vertices. For an undirected graph, if vertex 0 is connected to 1, 2, and 3, its adjacency list is [1, 2, 3]. For a weighted graph, the adjacency list can store tuples of "neighbor + weight". The space complexity of an adjacency list is O(V + E) (where V is the number of vertices and E is the number of edges), making it suitable for sparse graphs. It facilitates traversal of neighboring vertices but requires traversing the adjacency list to check if an edge exists between two vertices. Mastering the adjacency list is fundamental for algorithms such as graph traversal and shortest path finding.