> For the complete documentation index, see [llms.txt](https://xiuxin.gitbook.io/datastructre/llms.txt). Markdown versions of documentation pages are available by appending `.md` to page URLs; this page is available as [Markdown](https://xiuxin.gitbook.io/datastructre/tu/ji-ben-gai-nian.md).

# 基本概念

## 定义

  图G由顶点集V和边集E组成，记为 G = (V, E) ，其中 V（G）表示图G中顶点的有限非空集；E（G）表示图G中顶点之间的关系（边）集合。若 V = {v1,v2,...,vn}，则用|V|表示图G中顶点的个数，也称图G的阶，

$$
E = {（u,v）|u\in V,v\in V }
$$

用|E|表示图G中边的数。

## 有向图

  若 E 是有向边（弧）的有限集合时，则图G为有向图。弧是顶点的有序对，记为，其中v,w是顶点，v称为**弧尾**，w称为**弧头**， 称为**顶点v到w的弧**，也称v邻接到w，或w邻接自v。

![](https://xiuxin-1304803037.cos.ap-shanghai.myqcloud.com/有向图.jpg)

## 无向图

  若 E 是无向边（简称边）的有限集合时，则图G为无向图。便是顶点的无序对，记为（v，w）或（w，v），因为（v，w）= （w，v），其中v，w是顶点。可以说顶点w和顶点v互为邻接点。边（v，w）依附顶点w，v，或者说边（v，w）和顶点v，w相关联。

![](https://xiuxin-1304803037.cos.ap-shanghai.myqcloud.com/无向图.jpg)

## 简单图

  一个图G若满足：

1. 不存在重复边
2. 不存在顶点到自身的边

   则称图G为简单图。

## 多重图

  若图中某个结点之间的边数多于一条，又允许顶点通过同一条边和自己关联，则G为多重图。多重图的定义和简单图是相对的。

## 完全图（简单完全图）

 **在无向图中，若任意两个顶点之间都存在边，则称该图为无向完全图**。含有n个顶点的无向完全图有 n（n - 1）/ 2 条边。在有向图中，**若任意两个顶点之间都存在方向相反的两条弧，则称该图为有向完全图**。含有n个顶点的无向完全图有 n（n - 1）条边。

## 子图

  设有两个图 G = （V,E）和 G‘ = （v’，E'）,若 V' 是 V的子集，且 E’ 是 E 的子集，则称 G' 是 G 的子集。若有满足V（G‘）= V（G）的子图G’，则称其为G的**生成子图**。

## 连通、连通图和连通分量

  在无向图中，若从顶点v到顶点w有路径存在，则称v和w是连通的。**若图G中任意两个顶点都是连通的，则称图G为连通图**，否则称为非连通图。**无向图中的极大连通子图称为连通分量**。若有一个图中有 n 个顶点，并且边数小于 n - 1，则此图必是非连通图。**无向图中的极大连通子图称为连通分量。**若一个图有n个顶点，并且边数小于n-1，则此图必是非连通图。

  **注：极大连通子图 是 无向图的连通分量， 极大 即要求该连通子图包含所有的边；极小连通子图是 即要保持图连通又要使得 边数最少 的子图。**

![](https://xiuxin-1304803037.cos.ap-shanghai.myqcloud.com/无向图及连通分量.jpg)

## 强连通图、强连通分量

  在有向图中，若从顶点 v 到顶点 w 和从顶点w 到 顶点 v 之间都有路径，则称这两个顶点是**强连通**的。若图中任何一对顶点都是强连通的，则称此图为**强连通图**。 有向图中的极大强连通图称为有向图的**强连通分量**。

## 生成树、生成森林

  连通图的生成树是包含图中全部顶点的一个极小连通子图。若图中顶点数为n，则它的生成树含有 n - 1条边。对生成树而言，若砍去它的一条边，则会变成非连通图，若加上一条边则会形成一个回路。在非连通图中，连通分量的生成树构成了非连通图的生成森林。

## 顶点的度，入度和出度

  图中每个顶点的度定义为以该顶点为一个端点的边的个数。（树的结点的度 为 子结点个数 ）

  对于无向图，顶点v 的度是指依附于该顶点的边的条数。具有n个顶点，e条边的无向图中，无向图全部顶点的度的和等于边数的两倍。

  对于有向图，顶点的度分为 入度和出度；入度是以顶点为终点的有向边的数目，而出度是以顶点为起点的有向边的数目；顶点的度等于其入度和出度之和。 在具有n个顶点、e条边的有向图中，有向图的全部顶点的入度之和与出度之和相等，并且等于边数。

## 边的权 和 网

  一个图中，每个边都可以标上具有某种含义的数值，该数值称为边的权值。这种边上带有权值的图为带权图，也称网。

## 稠密图，稀疏图

  边数很少的图称为稀疏图，反之称为稠密图。稀疏和稠密是相对的，一般认为图的|E| < |V| log |V| 时，可以将图视为稀疏图。

## 路径、路径长度和 回路

  顶点Vp 到顶点 Vq 之间的一条路径是指顶点序列Vp，Vi，... ，Vq。路径上边的数目称为**路径长度**。第一个顶点和最后一个顶点相同的路径称为**回路或环**。若一个图有n个顶点，并且有大于 n - 1 条边，则此图一定有环。

## 简单路径，简单回路

  在路径序列中，顶点不出现重复的路径称为**简单路径**。除第一个顶点和最后一个顶点外，其余顶点不重复出现的回路称为**简单回路**。

## 距离

  从顶点U 出发到顶点V的最短路径若存在，则此路径的长度称为 从 U 到 V的距离。若从U 到 V根本不存在路径，则记该距离为无穷。

## 有向树

  一个顶点的入度为0，其余顶点的入度均为1的有向图，称为 有向树。