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

§1. 概述

1. 定义：由定点集 V 和边集 E 组成，记为 G (V,E)

2. 注意：线性表、树可为空，但图不可为空。至少一个顶点。

3. 有向图：E 是有向边（简称弧）的有限集合。 $0≤e≤n (n-1)$

4. 无向图：E 是无向边（简称边）的有限集合。 $0≤e≤\frac {n (n-1)}{2}$

5. 简单图：满足 ① 不存在重复边，② 不存在定点到自身的边。

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

6. 无向完全图：任意两个顶点都存在边，$e=\frac {n (n-1)}{2}$

7. 有向完全图：任意两个顶点存在着方向相反的两条弧，$e=n (n-1)$

8. 连通：从顶点 V 到顶点 W 有路径存在，则称 V 与 W 连通。

9. 连通图：若图 G 中任意两个顶点都是连通的，称 G 为连通图，否则为非连通图。

10. 无向图中的极大连通图称为连通分量。

11. 强连通图（仅针对有向图），若从顶点 V 到顶点 W 和从顶点 W 到顶点 V 之间都有路径，则称这两个顶点强连通，则称。

12. 强联通分量（仅针对有向图），图中极大强连通子图称为有向图的强连通分量。

13. 生成树：连通图的生成树是包含图中全部顶点的一个极小连通子图。若图中顶点数为 $n$，则它的生成树有 $n-1$ 条边。

    对生成树：若砍去一条边则为非连通图，加上一条边为回路。

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

15.

• 无向图中，度为 $\sum_{i=1}^n TD (V_i)=2e$
• 有向图中，$TD (V_i)=ID (V)+OD (V)$
• $e$ 条边有向图，$\sum_{i=1}^n ID (V_i)=\sum_{i=1}^n OD (V_i)=e$

16. 稠密图与稀疏图：边数很少（$e＜nlog_2n$），称为稀疏图。

17. 路径：顶点 $v_0$ 到顶点 $v_q$ 之间的一条路径，即顶点序列 $v_1,v_2,v_3,……,v_n$。

18. 路径长度：路径上边的数目。

19. 回路：第一个顶点和最后一个顶点相同的路径。
    若一个图有 n 个顶点，且有大于 $n-1$ 条边，则此图一定有环。

20. 简单路径：在路径序列中，顶点不重复出现的路径。

21. 简单回路：除第一个顶点和最后一个顶点外，其余顶点不重复出现的回路。

22. 图的存储结构：邻接矩阵、邻接表、逆邻接表、十字链表、邻接多重表。（邻接多重表仅适用于存储无向图）。

§2. 邻接矩阵表示法

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

24. #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为顶点数

25. 无向图的邻接矩阵一定是对称矩阵（且唯一）。在世纪应用可以压缩存储（上 / 下三角矩阵）。

26. 无向图邻接矩阵第 $i$ 行（第 $j$ 列）非 0 元素的个数为第 $i$ 个顶点的度。

27. 有向图邻接矩阵第 $i$ 行（第 $j$ 列）非 0 元素的个数为第 $i$ 个顶点的出度（入度）。

28. 用临街矩阵法存储图，很容易确定图中任意两个顶点是否有边相连。但要确定途中有多少条便需按行、列对每个元素检测。

§3. 邻接表表示法

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

• 顶点表：

Data	firstarc
顶点域	头指针

• 边表：

adjVex	nextarc
邻接点域	指针域

31. ```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. 邻接多重表

39. 临接多重表：无向图的另一种链式存储结构。“数组（顶点）+ 边结点”

40. 容易求得顶点和边的各种信息，但在邻接表中求两个顶点是否存在边，或需对边执行删除等操作，需分别在两个顶点的边表遍历。

• 边

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

• 顶点

data	firstdye
	边

42. 示例

43. #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. 最小生成树

44. 最小生成树（MST）：图的极小连通子图，包含所有顶点和尽可能少的边。

45. 对最小生成树，砍去一条边构成非连通图，增加一条边则形成回路。

46. 性质：

    • 最小生成树不唯一
    • 权值之和为 1
    • 边数 = 顶点数 - 1

47. 普里姆 (Prim) 算法：

    1. 开始时，$U={v_0},TE=\varnothing$,
    2. 计算 $U$ 到某余顶点 $V-U$ 的最小代价，纳入 $U$，边纳入 $TE$
    3. 重复 2 知道 $U=V$

48. 克鲁斯卡尔 (Kruskal) 算法：“不够成环情况下，每次先选择最小边”，适用于边稀疏且顶点多的树，结果不唯一。

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

50. Dijkstra 算法（单源带权图）

    1. 初始化：用起点 $V$ 到该顶点 $w$ 的直接边（弧）初始化最短路径，否则设为 $\infty$，用 $dist []$ 记录，$dist [i]$ 处置 $arcs [VD][i]$；
    2. 从未求得最短路径的终点中选择长度最小终点 $V$，求 $V→U$ 最短路径；
    3. 修改最短路径：计算 $U$ 的邻接点的最短路径，若 $(V,\dots,U)+(u,v)<(V,\dots,W)$，以 $（V,\dots,V,W$ 代替；
    4. 重复 2,3，知道求出 $v$ 到其余所有结点的最短路径。

51. 若用邻接矩阵表示，则时间复杂度为 $O (|v|2)$。若求源点到其他所有结点最短路径，其时间复杂度为 $O (|v|^2)$。若找出所有结点对之间的最短距离，时间复杂度 $O (|v|^3)$.

52. Dijstra 算法不适用边上有负权值的图。

53. Floyd 算法。依次计算 $A^{(0)},A^{(1)},A^{(2)},\dots,A^{(n)}$。计算 $A^{(k)}_{ij}=\min {A^{(k-1)}}(i,j),A^{(k-1)}(i,k)+A^{(k-1)}(k,j)$

54. 时间复杂度 $O (|V|^3)$

§7. 其他

55. 拓扑排序：“每次删除入度为 0 的顶点并输出”

56. 有向无环图 (DAG)：一个有向图中不存在环

57. AOV 网：用有向边 $<V_i,V_j>$ 表示活动 $V_i$ 必须先于活动 $V_j$ 进行的一种关系，将这种有向图称为顶点表示活动的网络。

58. 关键路径：在带权有向图中，以顶点表示事件，有向边表示活动，边上的权值表示完成活动的开销（如：花费时间），则称这种有向图为用边表示活动的网络，简称为 AOE 网。