考研笔记 | 数据结构 §6. 图

发表于 2018-05-19 分类于课业阅读次数：374 本文字数： 4k 阅读时长 ≈ 4 分钟

§1. 概述

定义：由定点集 V 和边集 E 组成，记为 G (V,E)
注意：线性表、树可为空，但图不可为空。至少一个顶点。
有向图：E 是有向边（简称弧）的有限集合。 $0 \leq e \leq n (n - 1)$
无向图：E 是无向边（简称边）的有限集合。 $0 \leq e \leq \frac{n (n - 1)}{2}$
简单图：满足 ① 不存在重复边，② 不存在定点到自身的边。

* 在数据结构中，讨论的均为简单图！（与之对应的是多重图）

无向完全图：任意两个顶点都存在边， $e = \frac{n (n - 1)}{2}$
有向完全图：任意两个顶点存在着方向相反的两条弧， $e = n (n - 1)$
连通：从顶点 V 到顶点 W 有路径存在，则称 V 与 W 连通。
连通图：若图 G 中任意两个顶点都是连通的，称 G 为连通图，否则为非连通图。
无向图中的极大连通图称为连通分量。
强连通图（仅针对有向图），若从顶点 V 到顶点 W 和从顶点 W 到顶点 V 之间都有路径，则称这两个顶点强连通，则称。
强联通分量（仅针对有向图），图中极大强连通子图称为有向图的强连通分量。
生成树：连通图的生成树是包含图中全部顶点的一个极小连通子图。若图中顶点数为 $n$ ，则它的生成树有 $n - 1$ 条边。
对生成树：若砍去一条边则为非连通图，加上一条边为回路。

度：边数
出度：“起点边数”
入度：“终点边数”

15.

无向图中，度为 $\sum_{i = 1}^{n} T D (V_{i}) = 2 e$
有向图中， $T D (V_{i}) = I D (V) + O D (V)$
$e$ 条边有向图， $\sum_{i = 1}^{n} I D (V_{i}) = \sum_{i = 1}^{n} O D (V_{i}) = e$

稠密图与稀疏图：边数很少（ $e ＜ n l o g_{2} n$ ），称为稀疏图。
路径：顶点 $v_{0}$ 到顶点 $v_{q}$ 之间的一条路径，即顶点序列 $v_{1}, v_{2}, v_{3}, \dots \dots, v_{n}$ 。
路径长度：路径上边的数目。
回路：第一个顶点和最后一个顶点相同的路径。
若一个图有 n 个顶点，且有大于 $n - 1$ 条边，则此图一定有环。
简单路径：在路径序列中，顶点不重复出现的路径。
简单回路：除第一个顶点和最后一个顶点外，其余顶点不重复出现的回路。
图的存储结构：邻接矩阵、邻接表、逆邻接表、十字链表、邻接多重表。（邻接多重表仅适用于存储无向图）。

§2. 邻接矩阵表示法

邻接矩阵法：一位数组存储顶点 + 二维数组存储图的边 + 顶点数 + 弧数

#define MaxVertexNum 100 // 顶点数目最大值
typedef char  VertexType; // 顶点数据类型
typedef int EdgeType; //带权图中边上权值的数据类型
typedef struct Graph{
	VertexType vex[MaxVertexNum]; //顶点表
	EdgeType Edge[MaxVertexNum][MaxVertexNum]; //矩阵边表
	int Vexnum,arcnum; //图中当前顶点数与弧数
}MGraph;//空间复杂度O(n²),n为顶点数

无向图的邻接矩阵一定是对称矩阵（且唯一）。在世纪应用可以压缩存储（上 / 下三角矩阵）。
无向图邻接矩阵第 $i$ 行（第 $j$ 列）非 0 元素的个数为第 $i$ 个顶点的度。
有向图邻接矩阵第 $i$ 行（第 $j$ 列）非 0 元素的个数为第 $i$ 个顶点的出度（入度）。
用临街矩阵法存储图，很容易确定图中任意两个顶点是否有边相连。但要确定途中有多少条便需按行、列对每个元素检测。

§3. 邻接表表示法

邻接表法：数组（弧尾顶点）+ 链表（邻接点）+ 个数

顶点表：

Data	firstarc
顶点域	头指针

边表：

adjVex	nextarc
邻接点域	指针域

```c
#define MaxVertexNum 100
typedef struct ArcNode {// 边表结点
int adjVex;
struct ArcNode *next;// 指向下一条弧的指针
InfoType info;// 网的边权值
}ArcNode;
typedef struct VNode{
VertexType data;
ArcNode *first;
}VNode,AdjList[MaxVertexNum];
typedef struct{
AdjList vertices;
intVexnum arcnum;
}ALGroph


32. 若G为无向图，则所需存储空间为$O(|V|+2|e|)$，  
      若为有向图，则所需存储空间为$O(|V|+|e|)$，  
      前者的2是因为无向图中每条边出现了两次。
33. 对于稀疏图，适用于邻接表存储，节约存储空间。
34. 在邻接表中，给定顶点能容易的找到领边，反之矩阵不行（$O(n)$）  
      在邻接矩阵中，可以快速查找两个顶点是否存在边。
35. 在有向图的邻接表表示中，求给定节点出度仅需计算其邻接表中结点个数，但入度需要遍历整个邻接表。因此有逆邻接表表示，不唯一。

# §4.十字链表表示法

36. 
   - 弧结点

| tailVex | headVex | hlinx | tlink | info |
| :-----: | :-----: | :---: | :---: | :--: |
|   尾域    |   头域    | 弧头相同  | 弧尾相同  |      |

   - 顶点结点

| data | fitstin | fistout |
| :--: | :-----: | :-----: |
|      |         |         |
37. 示例 ![示例][6.2]

38. ```c
    #define MaxVertexNum 100
    typedef struct ArcNode{		//边表结点
        int tailVex,headVex;	//头尾节点
        struct ArcNode	*hlink,*tlink;	//指向弧头相同与弧尾相同节点
        //InfoType info;	//相关信息指针
    }ArcNode;
    typedef struct VNode{   //顶点表结点
        VertexType data;    //顶点信息
        ArcNode *firstin,*firstout;  //指向第一条弧与出弧
    }VNode;
    typedef struct{ //邻接表
        VNode *list[MaxVertexNum];
        int Vexnum,arcnum;  //顶点数与弧数
    }GlGraph;

§5. 邻接多重表

临接多重表：无向图的另一种链式存储结构。“数组（顶点）+ 边结点”
容易求得顶点和边的各种信息，但在邻接表中求两个顶点是否存在边，或需对边执行删除等操作，需分别在两个顶点的边表遍历。

mark	ivex	ilink	jvex	jlink	info
标志域（是否遍历）		下一顶点 ivex 边		下一顶点 jvex 边

顶点

data	firstdye
	边

示例

#define MaxVertexNum 100
typedef struct ArcNode{
    bool Mark;  //访问标记
    int ivex,jvex;  //指向弧结点
    struct ArcNode *ilink,*jlinkl   //分别指向两个结点下一条边
    //InfoType info;	//相关信息指针
}ArcNode
typedef struct VNode{   //顶点表结点
    VertexType data;    //顶点信息
    ArcNode *firstedge  //指向第一条弧与出弧
}VNode;
typedef struct{ //邻接表
    VNode adjmulist[MaxVertexNum];
    int Vexnum,arcnum;  //顶点数与弧数
}GlGraph;

§6. 最小生成树

最小生成树（MST）：图的极小连通子图，包含所有顶点和尽可能少的边。
对最小生成树，砍去一条边构成非连通图，增加一条边则形成回路。
性质：
- 最小生成树不唯一
- 权值之和为 1
- 边数 = 顶点数 - 1
普里姆 (Prim) 算法：
1. 开始时， $U = v_{0}, T E = \emptyset$ ,
2. 计算 $U$ 到某余顶点 $V - U$ 的最小代价，纳入 $U$ ，边纳入 $T E$
3. 重复 2 知道 $U = V$
克鲁斯卡尔 (Kruskal) 算法：“不够成环情况下，每次先选择最小边”，适用于边稀疏且顶点多的树，结果不唯一。

算法	普里姆	克鲁斯卡尔
时间复杂度	$O (n^{2})$	$O(
特点	只与顶点个数 n 有关	只与边数 e 有关
	与边数 e 无关	与顶点个数 n 无关
	适用于稠密图	适用于稀疏图

Dijkstra 算法（单源带权图）
1. 初始化：用起点 $V$ 到该顶点 $w$ 的直接边（弧）初始化最短路径，否则设为 $\infty$ ，用 $d i s t []$ 记录， $d i s t [i]$ 处置 $a r c s [V D] [i]$ ；
2. 从未求得最短路径的终点中选择长度最小终点 $V$ ，求 $V \to U$ 最短路径；
3. 修改最短路径：计算 $U$ 的邻接点的最短路径，若 $(V, \dots, U) + (u, v) < (V, \dots, W)$ ，以 $（ V, \dots, V, W$ 代替；
4. 重复 2,3，知道求出 $v$ 到其余所有结点的最短路径。
若用邻接矩阵表示，则时间复杂度为 $O (| v | 2)$ 。若求源点到其他所有结点最短路径，其时间复杂度为 $O (| v |^{2})$ 。若找出所有结点对之间的最短距离，时间复杂度 $O (| v |^{3})$ .
Dijstra 算法不适用边上有负权值的图。
Floyd 算法。依次计算 $A^{(0)}, A^{(1)}, A^{(2)}, \dots, A^{(n)}$ 。计算 $A_{i j}^{(k)} = min A^{(k - 1)} (i, j), A^{(k - 1)} (i, k) + A^{(k - 1)} (k, j)$
时间复杂度 $O (| V |^{3})$

§7. 其他

拓扑排序：“每次删除入度为 0 的顶点并输出”
有向无环图 (DAG)：一个有向图中不存在环
AOV 网：用有向边 $< V_{i}, V_{j} >$ 表示活动 $V_{i}$ 必须先于活动 $V_{j}$ 进行的一种关系，将这种有向图称为顶点表示活动的网络。
关键路径：在带权有向图中，以顶点表示事件，有向边表示活动，边上的权值表示完成活动的开销（如：花费时间），则称这种有向图为用边表示活动的网络，简称为 AOE 网。