数据结构笔记（七）——图

1. 图是由顶点的有穷非空集合和顶点之间边的集合组成，通常表示为：G（V，E），其中，G表示一个图，V是图G中顶点的集合，E是图G中边的集合。

2. 相关概念
   ·无向边：若顶点 vi 到 vj 之间的边没有方向，则称这条边为无向边，用无序偶对（vi, vj）来表示。
   ·无向图：如果图中任意两个顶点之间的边都是无向边，则称该图为无向图。
   ·有向边：若顶点 vi 到 vj 之间的边有方向，则称这条边为有向边，也称为弧，用有序偶<vi, vj>来表示， vi 称为弧尾， vj 称为弧头。
   ·有向图：如果图中任意两个顶点之间的边都是有向边，则称该图为有向图。
   ·简单图：不存在顶点到其自身的边，且同一条边不重复出现。
   ·无向完全图：任意两个顶点之间都存在边的无向图。含有n个顶点的无向完全图有 n ×（n-1）/ 2条边。
   ·有向完全图：任意两个顶点之间都存在方向互为相反两条弧的有向图。含有n个顶点的有向完全图有 n ×（n-1）条边。
   ·权：与图的边或弧相关的数，表示从一个顶点到另一个顶点的距离或耗费。
   ·网：带权的图。
   ·子图：假设有两个图G=（V，{E}）和G’=（V’，{E’}），如果V’ ⊆ V且E’ ⊆ E，则称G’为G的子图。

3. 图的顶点与边的关系
   ·（无向图的）邻接点：对于无向图G=（V，{E}），如果边（v，v’）∈E，则称顶点 v 和 v’ 互为邻接点，即 v 和 v’ 相邻接。边（v，v’）关联于顶点 v 和 v’ ，或者说 v 和 v’ 与顶点 v 和 v’ 相关联。
   ·（无向图的）度：顶点 v 的度是和 v 相关联的边的数目，记为TD（v）。
   ·（有向图的）邻接点：对于有向图G=（V，{E}），如果边（v，v’）∈E，则称顶点 v 邻接到顶点 v’ ，顶点 v’ 邻接自顶点 v 。弧<vi, vj>与顶点 v，v’ 相关联。
   ·（有向图的）度：以顶点 v 为头的弧的数目称为 v 的入度，记为ID（v）；以 v 为尾的弧的数目称为 v 的出度，记为OD（v）；顶点 v 的度为TD（v）=ID（v）+OD（v）。
   ·路径长度：路径上的边或弧的数目。
   ·回路：第一个顶点到最后一个顶点相同的路径称为回路或环。
   ·简单路径：序列中顶点不重复出现的路径称为简单路径。
   ·简单回路：除了第一个顶点和最后一个顶点之外，其余顶点不重复出现的回路，称为简单回路或简单环。

4. 连通图
   ·连通图：在无向图G中，如果从顶点 v 到顶点 v’ 有路径，则称 v 和 v’ 是连通的。如果对于图中任意两个顶点 vi，vj ∈ V， vi 和 vj 都是连通的，则称G是连通图。
   ·连通分量：无向图中的极大连通子图。
   ·强连通图：在有向图G中，如果对于每一对 vi，vj ∈ V、 vi ≠ vj，从 vi 到 vj 和从 vj 到 vi，都存在路径，则称G是强连通图。
   ·强连通分量：有向图中的极大强连通子图。
   ·生成树：一个连通图的生成树是一个极小的连通子图，它含有图中全部的n个顶点，但只有足以构成一棵树的n-1条边。
   ·有向树：如果一个有向图恰有一个顶点的入度为0，其余顶点的入度均为1，则是一棵有向树。
   ·生成森林：一个有向图的生成森林由若干棵有向树组成，含有图中全部顶点，但只有足以构成若干棵不相交的有向树的弧。

5. 图的存储结构
   ·邻接矩阵：用两个数组来表示图。一个一维数组存储图中顶点信息，一个二维数组（称为邻接矩阵）存储图中的边或弧的信息。
   ①无权图
   
   ·无向图的边数组是个对称矩阵。
   ·度：无向图顶点所在行或列的和；有向图顶点所在行与列的和（行表示出度；列表示入度）。
   ②加权图/网
   
   ·邻接表：数组与链表相结合。
   ①顶点用一个一维数组存储，顶点数组中，每个数据元素还需要存储指向第一个邻接点的指针。
   ②每个顶点v的所有邻接点构成一个线性表，由于邻接点的个数不定，所以用单链表存储，无向图称为顶点vi的边表，有向图则称为顶点vi作为弧尾的出边表。
   ·带权网还要在邻接点链表中加入权重。
   
   
   ·十字链表（有向图）

①顶点表：firstin表示入边表头指针，指向该顶点的入边表中的第一个结点；firstout表示出边表头指针，指向该顶点的出边表中的第一个结点。

②边表：tailvex是指弧起点在顶点表的下标；headvex是指弧终点在顶点表中的下标；headlink是指入边表指针域，指向终点相同的下一条边；taillink是指边表指针域，指向起点相同的下一条边。如果是网，还可以再增加一个weight域来存储权值。

·邻接多重表（无向图）：ivex和jvex是与某条边依附的两个顶点在顶点表中下标；ilink 指向依附顶点ivex的下一条边；jlink 指向依附顶点jvex的下一条边。

6. 边集数组：由两个一维数组构成。一个是存储顶点的信息；另一个是存储边的信息，边数组每个数据元素由一条边的起点下标、终点下标和权组成。
   

7. 图的遍历：从图中某一顶点出发访遍图中其余顶点，且使每一个顶点仅被访问一次。
   ·深度优先遍历DFS（类似树的前序遍历）
   ①对于连通图，从图中某个顶点v出发，访问此顶点，然后从v的未被访问的邻接点出发深度优先遍历图，直至图中所有和v有路径相通的顶点都被访问到。
   ②对于非连通图，只需要对它的连通分量分别进行深度优先遍历，即在先前一个顶点进行一次深度优先遍历后，若图中尚有顶点未被访问，则另选图中一个未曾被访问的顶点作起始点，重复上述过程，直至图中所有顶点都被访问到为止。
   （对于n个顶点e条边的图，使用邻接矩阵需要O（n^2）时间，使用邻接表需要O（n+e）时间）
   ·广度优先遍历BFS（类似树的层序遍历）

8. 最下生成树：构造连通网的最小代价生成树。
   ·普里姆（Prim）算法：假设N=（P{E}）是连通网，TE是N上最小生成树中边的集合。算法从U={u0}（u0∈V），TE={}开始，重复执行下述操作：在所有u0∈U，v∈V-U的边（u，v）∈E中找一条代价最小的边（u0，v0）并入集合TE，同时v0并入U，直至U=V为止。此时TE中必有n-1条边，则T=（V{TE}）为N的最小生成树。
   （时间复杂度O（n^2），适用于稠密图）
   ·克鲁斯卡尔（Kruskal）算法：假设N=（V，{E}）是连通网，则令最小生成树的初始状态为只有n个顶点而无边的非连通图T={V，{}}，图中每个顶点自成一个连通分量。在E中选择代价最小的边，若该边依附的顶点落在T中不同的连通分量上，则将此边加入到T中，否则舍去此边而选择下一条代价最小的边。依次类推，直至T中所有顶点都在同一连通分量上为止。
   （时间复杂度O（e loge），适用于稀疏图）

9. 最短路径：两顶点之间经过的边上权值之和最少的路径。路径上的第一个顶点是源点，最后一个顶点是终点。
   ·迪杰斯特拉（Dijkstra）算法：时间复杂度O（n^2）。
   ·弗洛伊德（Floyd）算法：时间复杂度O（n^3）。

10. 拓扑排序
    ·AOV网：在一个表示工程的有向图中，用顶点表示活动，用弧表示活动之间的优先关系，这样的有向图为顶点表示活动的网称为AOV网。
    ·拓扑序列：设G=（V，E）是一个具有n个顶点的有向图，V中的顶点序列v1，v2，……，vn，满足若从顶点 vi 到 vj 有一条路径，则在顶点序列中顶点 vi 必在顶点 vj 之前。
    ·对AOV网进行拓扑排序的基本思路：从AOV网中选择一个入度为0的顶点输出，然后删去此顶点，并删除以此顶点为尾的弧，继续重复此步骤，直到输出全部顶点或者AOV网中不存在入度为0的顶点为止。
    ·时间复杂度：O（n+e）。

11. 关键路径
    ·路径上各个活动所持续的时间之和称为路径长度，从源点到汇点具有最大长度的路径叫关键路径，在关键路径上的活动叫关键活动。
    ·事件的最早发生时间etv：顶点vk的最早发生时间。（P[k]为所有到达顶点vk的弧的集合）
    
    ·事件的最晚发生时间ltv：顶点vk的最晚发生时间，即每个顶点对应的事件最晚需要开始的时间，超出此时间将会延误整个工期。（S[k]为所有从顶点vk出发的弧的集合）
    
    ·活动的最早开工时间ete：弧ak的最早发生时间。
    ·活动的最晚开工时间lte：弧ak的最晚发生时间，即不推迟工期的最晚开工时间。
    ·时间复杂度：O（n+e）。