图的基础世界 | The Fundamental World of Graphs

图的基础世界 | The Fundamental World of Graphs

什么是图？ | What is a Graph?

当我们第一次听到“图”这个词时，大多数人脑海中浮现的可能是照片、绘画或者网页上的图片。然而，在计算机科学与数学的领域里，“图”这个概念有着截然不同却同样精彩的意义。图（Graph）是一种用来表示物体与物体之间关系的数据结构——它由一系列的节点（Node）和连接这些节点的边（Edge）组成。简单来说，如果你想把“谁认识谁”这个问题用一种结构化的方式表达出来，图就是最好的选择。

When we first hear the word "graph," most people imagine photos, paintings, or images on a webpage. However, in the realm of computer science and mathematics, the concept of a "graph" carries a different yet equally fascinating meaning. A graph is a data structure used to represent relationships between objects—it consists of a collection of nodes (also called vertices) and edges that connect these nodes. Simply put, if you want to express "who knows whom" in a structured way, a graph is the perfect choice.

让我们用一个所有人都熟悉的情景来理解图的概念——社交网络。想象一下微信或微博上的好友关系：每个用户就是一个节点，而当两个用户互相关注或成为好友时，他们之间就存在一条边。整个社交网络就像一张巨大的蛛网，每个节点代表一个人，每条边代表人与人之间的联系。这正是图结构最直观的体现。

Let's understand the concept of graphs through a scenario familiar to everyone—a social network. Imagine the friend relationships on WeChat or Weibo: each user is a node, and when two users follow each other or become friends, there exists an edge between them. The entire social network resembles a giant spider web, where each node represents a person and each edge represents the connection between people. This is the most intuitive manifestation of graph structures.

在正式的定义中，图 G 通常被表示为 $G = (V, E)$，其中 $V$ 代表顶点的集合（Vertex Set），$E$ 代表边的集合（Edge Set）。这个简洁的数学表达式蕴含着图的本质：顶点是图的基本构成单元，边定义了顶点之间的某种关系。不妨把顶点想象成地图上的城市，把边想象成连接这些城市的道路——如此一来，图就变成了一张微缩的交通网络图。

In formal definition, a graph G is typically denoted as $G = (V, E)$, where $V$ represents the set of vertices (vertex set) and $E$ represents the set of edges (edge set). This concise mathematical expression contains the essence of graphs: vertices are the basic building blocks, and edges define some relationship between vertices. You can imagine vertices as cities on a map and edges as roads connecting these cities—in this way, a graph becomes a miniature transportation network map.

图的组成要素 | Components of a Graph

节点：图的基本单元 | Nodes: The Basic Units of Graphs

节点（Node），又称顶点（Vertex），是图结构中最基本的元素。每一个节点通常代表一个具体的实体，这个实体可以是真实世界中的一个人、一座城市、一个网页，也可以是抽象概念中的一个概念或一个事件。节点是图的“实体”，边的存在赋予了节点之间相互联系的意义。

A node (also called a vertex) is the most fundamental element in a graph structure. Each node typically represents a specific entity, which can be a person, a city, a webpage in the real world, or an abstract concept or event. Nodes are the "entities" of a graph, and the existence of edges gives meaning to the connections between nodes.

在图 $G = (V, E)$ 中，如果我们有一个包含5个节点的图，那么顶点集可以表示为 $V = \{v_1, v_2, v_3, v_4, v_5\}$。每个节点都可以拥有自己的属性（Attributes）或特征（Features）。例如，在一个社交网络中，每个用户节点可能包含姓名、年龄、兴趣等属性；在一个分子图中，每个节点代表一个原子，其属性可能包括原子序数、电子数、化学键类型等信息。

In a graph $G = (V, E)$, if we have a graph containing 5 nodes, the vertex set can be denoted as $V = \{v_1, v_2, v_3, v_4, v_5\}$. Each node can have its own attributes or features. For example, in a social network, each user node might contain attributes such as name, age, and interests; in a molecular graph, each node represents an atom, and its attributes might include atomic number, electron count, and chemical bond types.

节点的度（Degree）是图论中一个非常重要的概念。对于无向图（我们稍后会详细介绍），一个节点的度是指与该节点相连的边的数量。如果一个用户有100个好友，那么在社交网络图中，这个用户节点的度就是100。度的概念帮助我们理解节点在网络中的“重要性”——通常，度越高的节点在网络中越处于核心位置。

The degree of a node is a very important concept in graph theory. For an undirected graph (which we will introduce in detail later), the degree of a node refers to the number of edges connected to that node. If a user has 100 friends, then in the social network graph, the degree of this user node is 100. The concept of degree helps us understand the "importance" of a node in a network—generally, nodes with higher degrees occupy more central positions in the network.

```mermaid graph LR A((v₁)) --- B((v₂)) A --- C((v₃)) A --- D((v₄)) B --- C C --- D D --- E((v₅))

style A fill:#ff6b6b,stroke:#333,stroke-width:2px style B fill:#4ecdc4,stroke:#333,stroke-width:2px style C fill:#4ecdc4,stroke:#333,stroke-width:2px style D fill:#4ecdc4,stroke:#333,stroke-width:2px style E fill:#95e1d3,stroke:#333,stroke-width:2px ```

上面这个简单的图展示了5个节点之间的连接关系。节点 $v_1$ 连接到了 $v_2$、$v_3$、$v_4$，所以 $v_1$ 的度是3；节点 $v_5$ 只连接到 $v_4$，所以 $v_5$ 的度是1；而节点 $v_2$ 同时连接到 $v_1$ 和 $v_3$，度为2。

The diagram above shows the connections between 5 nodes. Node $v_1$ connects to $v_2$, $v_3$, and $v_4$, so its degree is 3; node $v_5$ only connects to $v_4$, so its degree is 1; and node $v_2$ connects to both $v_1$ and $v_3$, with degree 2.

边：关系的桥梁 | Edges: Bridges of Relationships

如果说节点是图的“实体”，那么边（Edge）就是连接这些实体的“桥梁”。边定义了节点与节点之间的关系，这种关系可以是单向的，也可以是双向的；可以是等价的，也可以包含权重信息。

If nodes are the "entities" of a graph, then edges are the "bridges" connecting these entities. Edges define the relationships between nodes—these relationships can be unidirectional or bidirectional; they can be equivalent or include weight information.

在数学表示中，一条边通常由两个节点构成的有序对或无序对表示。如果边连接节点 $u$ 和 $v$，我们可以用 $e = (u, v)$ 来表示这条边。在无向图中，$(u, v)$ 和 $(v, u)$ 表示同一条边；而在有向图中，$(u, v)$ 和 $(v, u)$ 可能代表两条不同的边——这正是有向图与无向图的核心区别之一。

In mathematical notation, an edge is typically represented by an ordered or unordered pair of two nodes. If an edge connects nodes $u$ and $v$, we can represent this edge as $e = (u, v)$. In an undirected graph, $(u, v)$ and $(v, u)$ represent the same edge; while in a directed graph, $(u, v)$ and $(v, u)$ may represent two different edges—this is one of the core differences between directed and undirected graphs.

边根据其性质可以分为多种类型。简单边（Simple Edge）是最基本的形式，表示两个节点之间存在某种关系。自环（Self-loop）是指边从一个节点出发，最终又回到同一个节点，即 $e = (v, v)$。自环在某些图模型中有特殊意义，例如在网页分析中，一个页面可能有指向自己的链接。多重边（Multi-edge）是指两个节点之间存在多条边，这种情况在交通网络中很常见——两座城市之间可能有多条不同的高速公路或航线连接。

Edges can be classified into various types based on their properties. A simple edge is the most basic form, representing the existence of some relationship between two nodes. A self-loop refers to an edge that starts from a node and eventually returns to the same node, i.e., $e = (v, v)$. Self-loops have special meaning in certain graph models—for example, in webpage analysis, a page may have a link pointing to itself. Multi-edges refer to multiple edges between two nodes, which is common in transportation networks—two cities may have multiple different highways or flight routes connecting them.

在实际应用中，边往往携带着丰富的信息。以物流网络为例，两个仓库之间的边可能包含运输成本、运输时间、货物容量等信息；在金融网络中，两个账户之间的边可能记录了转账金额、转账频率等数据；在知识图谱中，边的类型更是多种多样——“是...的父亲”、“位于”、“毕业于”等关系类型都通过不同类型的边来表达。

In practical applications, edges often carry rich information. Taking a logistics network as an example, the edge between two warehouses might contain information such as transportation cost, transportation time, and cargo capacity; in a financial network, the edge between two accounts might record data such as transfer amount and transfer frequency; in a knowledge graph, edge types are even more diverse—"is the father of," "is located in," "graduated from"—these relationship types are all expressed through different types of edges.

图的分类 | Classification of Graphs

有向图与无向图 | Directed and Undirected Graphs

图的最基本分类维度之一是方向性（Directionality）。根据边是否具有方向，图可以分为有向图（Directed Graph）和无向图（Undirected Graph）。

One of the most fundamental classification dimensions of graphs is directionality. Depending on whether edges have direction, graphs can be classified into directed graphs and undirected graphs.

无向图（Undirected Graph）是最直观的图类型。在无向图中，边没有方向性，仅表示两个节点之间存在某种联系。想象朋友关系：如果你和小明是朋友，那么这个关系是双向的——你认识小明，小明也认识你。这种对称的关系非常适合用无向图来表示。社交网络中的“互相关注”、道路网络中的“双向车道”、以及同学关系等，都属于无向关系的范畴。

An undirected graph is the most intuitive type of graph. In an undirected graph, edges have no directionality, merely indicating that some connection exists between two nodes. Imagine