> For the complete documentation index, see [llms.txt](https://docs.1l.lol/llms.txt). Markdown versions of documentation pages are available by appending `.md` to page URLs; this page is available as [Markdown](https://docs.1l.lol/graph-theory/graph-basics.md).

# 图的基本概念与存储

### 图的基本概念

图 `G = (V, E)` 由**顶点集 V** 和**边集 E** 组成。

* **有向图 / 无向图**：边是否有方向
* **带权图**：边带有权值
* **度**：无向图中与顶点相连的边数；有向图分**入度**和**出度**
* **路径 / 环**：顶点序列 / 首尾相连的路径

### 邻接矩阵

`g[i][j]` 表示 i 到 j 是否有边（或边权）：

```cpp
const int N = 1005;
int g[N][N];                 // 0 表示无边
g[u][v] = 1; g[v][u] = 1;    // 无向图
// 带权：g[u][v] = w;
```

* 优点：O(1) 判断两点是否相邻
* 缺点：空间 O(n²)，稀疏图浪费

### 邻接表（推荐）

```cpp
vector<int> adj[N];          // 无权
adj[u].push_back(v);
adj[v].push_back(u);         // 无向图

// 带权图
vector<pair<int,int>> adjw[N];  // (邻点, 边权)
adjw[u].push_back({v, w});
```

* 空间 O(n + m)，遍历某点的邻边效率高，是竞赛首选。

### 边集数组

把所有边存成 `(u, v, w)` 数组，适合 Kruskal 等按边处理的算法。

### 选择建议

| 场景            | 存储   |
| ------------- | ---- |
| 稠密图、频繁查边      | 邻接矩阵 |
| 稀疏图、遍历邻边      | 邻接表  |
| 按边排序（Kruskal） | 边集数组 |


---

# Agent Instructions
This documentation is published with GitBook. GitBook is the documentation platform designed so that both humans and AI agents can read, navigate, and reason over technical content effectively. Learn more at gitbook.com.

## Querying This Documentation
If you need additional information that is not directly available in this page, you can query the documentation by asking a question.

Perform an HTTP GET request on the following URL with the `ask` and `goal` query parameters:

```
GET https://docs.1l.lol/graph-theory/graph-basics.md?ask=<question>&goal=<user_goal>
```

`ask` is the immediate question: it should be specific, self-contained, and written in natural language.
`goal` is what the user is ultimately trying to achieve, the reason they need the answer. Sharing it helps GitBook give you a better, more relevant answer. A goal is most helpful when it describes the outcome the user wants rather than restating the question. For example, with `ask=how do I create an API token`, a goal like `automate deployments from our CI pipeline` lets GitBook tailor the answer to that use case.

The response will contain a direct answer to the question and relevant excerpts and sources from the documentation.

Use this mechanism when the answer is not explicitly present in the current page, you need clarification or additional context, or you want to retrieve related documentation sections.