Unlocking Graphs: How Social Networks Map Relationships with Vertices and Edges

What Is a Graph?

In social networks like QQ, friendships can be represented as a graph , a data structure where each user is a vertex and each friendship is an edge . This models the complex web of connections between people.

Vertices, Edges, and Degree

Each vertex (node) may have multiple edges linking it to other vertices. The number of edges incident to a vertex is called its degree . In a directed graph, the number of outgoing edges is the out‑degree and the number of incoming edges is the in‑degree .

Directed vs. Undirected Graphs

A graph is undirected when edges have no orientation, resembling a mutual friendship. A directed graph adds arrows to edges, indicating a one‑way relationship such as “follows”.

Storing Graphs: Adjacency Matrix

The adjacency matrix (a two‑dimensional array) records connections between every pair of vertices. A cell contains 1 if an edge exists, otherwise 0. For example, an 8 × 8 matrix can represent eight people and their mutual relationships.

The matrix is simple but wastes space when the graph is sparse (many zeros), known as a sparse matrix.

Storing Graphs: Adjacency List

An adjacency list uses linked lists (or arrays of lists) where each vertex stores a list of its neighboring vertices, effectively recording only existing edges. This approach saves memory for sparse graphs.

Choosing Between the Two

Array (adjacency matrix) : fast edge lookup but high memory consumption; best for small or dense graphs.

Linked list (adjacency list) : memory‑efficient for large, sparse graphs but slower to check for a specific edge.