# 图

## 1. 图的定义

表示“多对多”的关系

包含：

* 一组顶点：通常用 $$V(Vertex)$$ 表示顶点集合
* 一组边：通常用 $$E(Edge)$$ 表示边的集合
  * 边是顶点对： $$(v, w) \in E$$ ，其中 $$v, w \in V$$&#x20;
  * 有向边 $$\<v, w>$$ 表示从 $$v$$ 指向 $$w$$ 的边（单行线）
  * 不考虑重边和自回路

## 2. 抽象数据类型定义

* **类型名称：**&#x56FE; $$(Graph)$$&#x20;
* **数据对象集合：** $$G(V, E)$$ 由一个**非空**的有限顶点集合 $$V$$ 和一个有限边集合 $$E$$ 组成
* **操作集：**&#x5BF9;于任意图 $$G \in Graph$$ ，以及 $$v \in V, e \in E$$&#x20;
  * `Graph Create()` ：建立并返回空图；
  * `Graph InsertVertex(Graph G, Vertex v)` ：将 $$v$$ 插入 $$G$$ ；
  * `Graph InsertEdge(Graph G, Edge e)` ：将 $$e$$ 插入 $$G$$ ；
  * `void DFS(Graph G, Vertex v)` ：从顶点 $$v$$ 出发深度优先遍历图 $$G$$ ；
  * `void BFS(Graph G, Vertex v)` ：从顶点 $$v$$ 出发宽度优先遍历图 $$G$$ ；
  * `void ShortestPath(Graph G, Vertex v, int Dist[])` ：计算图 $$G$$ 中顶点 $$v$$ 到任意其它顶点的最短距离；
  * `void MST(Graph G)` ：计算图 $$G$$ 的最小生成树；
  * $$\cdots \cdots$$&#x20;

## 3. 图的表示

### 3.1 邻接矩阵

邻接矩阵 $$G\[N]\[N]$$ ： $$N$$ 个顶点从 0 到 N-1 编号

$$G\[i]\[j]=\left{ \begin{aligned} 1 ，  &若 \<v\_i, v\_j> 是 G 中的边 \ 0  ， &否则  \end{aligned} \right.$$&#x20;

![](https://4108944334-files.gitbook.io/~/files/v0/b/gitbook-legacy-files/o/assets%2F-M8pwc1tpjc8KTzIQRni%2F-MCCu_fLUVLHr1cl2inr%2F-MCCvqjJS4TXGu9EtRGp%2Fimage.png?alt=media\&token=9d93a7c7-aa7e-4097-9d65-83b989b350ba)

**对于无向图的存储，省一半空间的方法**

![](https://4108944334-files.gitbook.io/~/files/v0/b/gitbook-legacy-files/o/assets%2F-M8pwc1tpjc8KTzIQRni%2F-MCCu_fLUVLHr1cl2inr%2F-MCCw5UKeYWL1woz254n%2Fimage.png?alt=media\&token=a2b123dc-7a8f-4c82-8922-1698617c023b)

**优点：**

* 直观、简单、好理解
* 方便检查任意一对顶点间是否存在边
* 方便找任一顶点的所有“邻接点”（有边直接相连的顶点）
* 方便计算任一顶点的“度”（从该点出发的边数为“出度”，指向该点的边数为“入度”）
  * 无向图：对应行（或列）非0元素的个数
  * 有向图：对应行非0元素的个数是“出度”；对应列非0元素的个数是“入度”

**缺点：**

* 浪费空间
  * 稀疏图（点很多而边很少）有大量无效元素
  * 稠密图（特别是完全图）还是很合算的
* 浪费时间：统计稀疏图中一共有多少边

### 3.2 邻接表

邻接表： $$G\[N]$$ 为指针数组，对应矩阵每行一个链表，只存非0元素

![](https://4108944334-files.gitbook.io/~/files/v0/b/gitbook-legacy-files/o/assets%2F-M8pwc1tpjc8KTzIQRni%2F-MCCxesBr_itYyL9Il1V%2F-MCCxxflyuldYZ3Rf7m3%2Fimage.png?alt=media\&token=9d33e678-1ea1-492e-9f29-c77d8a93f2fe)

**一定要足够稀疏才合算**

**优点：**

* 方便找任一顶点的所有“邻接点”
* 节约稀疏图的空间
  * 需要 N 个头指针 + 2E 个结点（每个结点至少 2 个域）
* 方便计算任一顶点的“度”？
  * 对于无向图：是的
  * 对于有向图：只能计算“出度”；需要构造“逆邻接表”（存指向自己的边）来计算“入度”

**缺点：**

* 不方便计算任意一对顶点间是否存在边

## 4. 图的一些概念

* **连通：**&#x5982;果从 $$V$$ 到 $$W$$ 存在一条 （无向）路径，则称 $$V$$ 和 $$W$$ 是连通的
* **路径：** $$V$$ 到 $$W$$ 的路径是一系列顶点 $${ V, v\_1, v\_2, \cdots , v\_n, W }$$ 的集合，其中任一对相邻的顶点间都有图中的边。路径的长度是路径中的边数（如果带权，则是所有边的权重和）。如果 $$V$$ 到 $$W$$ 之间的所有顶点都不同，则称简单路径
* **回路：**&#x8D77;点等于终点的路径
* **连通图：**&#x56FE;中任意两顶点均连通
* **连通分量：**&#x65E0;向图的极大连通子图
  * **极大顶点数：**&#x518D;加1个顶点就不连通
  * **极大边数：**&#x5305;含子图中所有顶点相连的所有边
* **强连通：**&#x6709;向图中顶点 $$V$$ 和 $$W$$ 之间存在双向路径，则称  $$V$$ 和 $$W$$ 是强连通的
* **强连通图：**&#x6709;向图中任意两顶点均强连通
* **强连通分量：**&#x6709;向图的极大强连通子图
