Graphs

In computer science, a graph is a fundamental model used to describe complex relationships between nodes. Unlike linear structures such as arrays, linked lists, or trees, graphs can flexibly represent an arbitrary number of entities and their many-to-many connection relationships. Whether it is the friendship relationship in social networks, web links on the internet, or route planning in transportation networks, graphs serve as the mathematical abstraction underlying these scenarios. Understanding the essence of a graph is a crucial step in mastering modern algorithm design.

A graph consists of two main components: vertices (Vertex) and edges (Edge). Vertices represent the entities or objects within the graph, while edges represent the associations or relationships between them. Formally defined, an undirected graph $G$ can be represented as an ordered pair $G = (V, E)$, where $V$ is a finite non-empty set of vertices, and $E$ is a finite set of vertex pairs, i.e., the set of edges. If the graph has directionality, an edge is defined as an ordered pair $(u, v)$, representing a directed connection from vertex $u$ to vertex $v$.
Based on the direction and properties of edges, graphs are primarily classified into undirected graphs, directed graphs, weighted graphs, and multigraphs. In an undirected graph, the edge connecting two vertices has no direction, implying a bidirectional relationship; in contrast, a directed graph strictly distinguishes between the starting point and the endpoint. Furthermore, if each edge is accompanied by a numerical value (such as distance, cost, or time), the graph is referred to as a weighted graph, which is particularly common in path optimization problems.

There are several methods to store graphs in computer memory, with two being the most widely used: the adjacency matrix and the adjacency list. The adjacency matrix uses a two-dimensional array to store the graph, where the element $A[i][j]$ indicates whether there is an edge between vertex $i$ and vertex $j$. The advantage of this method lies in its constant time complexity $O(1)$ for querying whether two vertices are connected; however, it suffers from low space efficiency when handling sparse graphs, as it requires allocating a large amount of memory even if most positions remain empty.

In contrast, an adjacency list stores connection information for each vertex using arrays or linked lists. For every vertex, we maintain a list recording all neighbor vertices directly connected to it. This structure is more space-efficient and is particularly suitable for sparse graphs where the number of edges is far less than the square of the number of vertices. Its time complexity grows linearly with the scale of the graph. Below is a simple Python code example demonstrating how to construct an undirected graph using an adjacency list:

class Graph:
    def __init__(self):
        self.adj_list = {}

    def add_vertex(self, vertex):
        if vertex not in self.adj_list:
            self.adj_list[vertex] = []

    def add_edge(self, v1, v2):
        self.adj_list[v1].append(v2)
        self.adj_list[v2].append(v1)  # Undirected graph requires bidirectional addition

# Example: Constructing a simple social network graph
g = Graph()
g.add_vertex("Alice")
g.add_vertex("Bob")
g.add_vertex("Charlie")
g.add_edge("Alice", "Bob")
g.add_edge("Bob", "Charlie")

Graph Traversal Algorithms and Applications

Graph traversal is a fundamental operation for processing large-scale graph data, with common algorithms including Depth-First Search (DFS) and Breadth-First Search (BFS). Depth-First Search explores every branch in depth using recursion or stack structures until no further exploration is possible, making it suitable for tasks such as detecting cycles and generating spanning trees. In contrast, Breadth-First Search utilizes a queue structure to expand layer by layer, capable of finding the shortest path from a starting point to all other vertices (in unweighted graphs), and is commonly used in social network friend recommendation systems.

The application scenarios of graphs are extremely diverse. In navigation software, cities are treated as vertices and roads as edges, with the Dijkstra algorithm used to calculate the shortest path; in bioinformatics, protein interactions are often analyzed in graph form; in compiler design, control flow graphs assist in optimizing code execution order. Mastering the theory and implementation techniques of graphs not only helps solve specific engineering problems but also cultivates systematic logical thinking abilities and abstract modeling capabilities.