（一）图的定义与存储

1.图的定义

图G是由集合V和E构成的二元组，记作G=(V,E)，其中V是图中顶点的非空有限集合，E是图中边的有限集合。

• 有向图。若图中每条边都是有方向的，那么顶点之间的关系用<vi,vj>表示，从vi到vj有一条有向边（也称为弧）。
• 无向图。若图中的每条边都是无方向的，顶点vi和vj之间的边用(vi,vj)表示。
• 完全图。若一个无向图具有n个顶点，而每个顶点与其他n-1个顶点之间都有边，则称为无向完全图。
• 度、出度和入度。顶点v的度是指关联于该点的边的数目，记作D(v)；顶点的入度是以该顶点为终点的有向边的数目，记作ID(v)；顶点的出度是指以该顶点为起点的有向边的数目，记作OD(v)。
• 路径。指顶点vp到顶点vq的路径。
• 子图。若有两个图G=(V,E)和G'=(V',E')，如果V'属于V且E'属于E，则称G'为G的子图。
• 连通图与连通分量。如果无向图G中任意两个顶点都是连通的，则称其为连通图；无向图G的极大连通子图称为G的连通分量。
• 强连通图与强连通分量。有向图中的极大连通子图称为有向图的强连通分量。
• 网。边（或弧）带权值的图称为网。
• 有向树。如果一个有向图恰有一个顶点的入度为0，其余顶点的入度均为1，则是一棵有向树。

2.图的存储结构

图的存储结构分为有邻接矩阵表示法和邻接链表表示法两种。

（1）邻接矩阵表示法

邻接矩阵表示法是指用一个矩阵来表示图中顶点之间的关系。

对于具有n个顶点的图G=(V,E)，其邻接矩阵是一个n阶方阵，并且满足下图：

无向图的邻接矩阵是对称的，有向图的邻接矩阵不一定对称。

下图所示是有向图和无向图的邻接矩阵，分别为A和B：

有向图和无向图及其邻接矩阵

（2）邻接链表表示法

邻接链表表示法指的是为图的每个顶点建立一个单链表，第i个单链表中的结点表示依附于顶点vi的边（对于有向图是以vi为尾的弧）。

邻接链表的结点有表结点（或边结点）和表头结点两种类型。如下图所示：

表结点和表头结点

含义如下：

• adjvex：指示与顶点vi邻接的顶点的序号；
• nextarc：指示下一条边或弧的结点；
• info：存储与边或弧有关的信息，如权值等；
• data：存储顶点vi的名或其他有关信息；
• firstarc：指示链表中的第一个结点（邻接顶点）。

（二）图的遍历

图的遍历是指从某个顶点出发，沿着某条搜索路径对图中的所有顶点进行访问且只访问一次的过程。

图的遍历算法是求解图的连通性问题、拓扑排序及求关键路径等算法的基础。

1.深度优先搜索（DFS）

类似于树的先根遍历，在第一次经过一个顶点时就进行访问操作。

特点：尽可能先对纵深方向搜索，因此可以得到其递归遍历算法。

实质：对某个顶点查找其邻接点的过程，其耗费时间取决于所采用的存储结构。

若图使用邻接矩阵表示时，查找所有顶点的邻接点所需时间为O(n^2)；
若以邻接表为图的存储结构，则需要O(e)的时间复杂度查找所有顶点的邻接点，因此，当以邻接表作为存储结构时，深度优先搜索遍历图的时间复杂度为O(n+e)

2.广度优先搜索（BFS）

从图中某个顶点v出发，在访问了v之后依次访问v的各个未被访问过的邻接点，然后分别从这些邻接点出发依次访问它们的邻接点，直到图中所有已被访问的顶点的邻接点都被访问到。

特点：尽可能先进行横向搜索，即最先访问的顶点的邻接点也先被访问。

（三）生成树及最小生成树

1.生成树的概念

对于有n个顶点的连通图，至少有n-1条边，而生成树中恰好有n-1条边，所以连通图的生成树是该图的极小连通子图。
如下图所示：

一个无向图的生成树和非生成树

按照深度和广度优先搜索进行遍历将得到不同的生成树，分别称为深度优先生成树和广度优先生成树。
如下图所示：

图的搜索生成树

2.最小生成树

定义：对于连通网来说，边是带权值的，生成树的各边也带权值，因此把生成树各边的权值总和称为生成树的权，把权值最小的生成树称为最小生成树。

常用的最小生成树求解算法有普利姆算法和克鲁斯卡尔算法。

（1）普利姆算法

以一个顶点集合U={u0}作为初态，不断寻找与U中顶点相邻且代价最小的边的另一个顶点，扩充U集合直到U=V时为止。

普利姆算法构造最小生成树的过程如下图所示：

普利姆算法构造最小生成树的过程

普利姆算法的时间复杂度为O(n^2)，该算法适合求边稠密的网的最小生成树。

（2）克鲁斯卡尔算法

令最小生成树的初始状态为只有n个顶点而无边的非连通图，图中每个顶点自成一个连通分量。选择其代价最小的边，若该边依附的顶点落在非连通图中不同的连通分量上，则将此边加入到非连通图中，否则舍去此边而选择下一条代价最小的边。依此类推，直到非连通图中所有顶点都在同一连通分量上为止。

克鲁斯卡尔算法构造最小生成树的过程如下图所示：

克鲁斯卡尔算法构造最小生成树的过程

克鲁斯卡尔算法的时间复杂度为O(eloge)，该算法适合求边稀疏的网的最小生成树。

（四）拓扑排序和关键路径

1.AOV网

定义：在有向图中，若以顶点表示活动，用有向边表示活动之间的优先关系，则称这样的有向图为以顶点表示活动的网（AOV网）。

在AOV网中，若从顶点vi到顶点vj有一条有向路径，则顶点vi是vj的前驱，顶点vj是vi的后继。

在AOV网中不应该出现优先环。

2.拓扑排序及其算法

拓扑排序是将AOV网中的所有顶点排成一个线性序列的过程。

一般情况下，假设AOV图代表一个工程计划，则AOV网的一个拓扑排序就是一个工程顺利完成的可行方案。

对AOV网进行拓扑排序的方法如下：

• 在AOV网中选择一个入度为0的顶点且输出它；
• 从网中删除该顶点及与该顶点有关的所有弧；
• 重复上面两步，直到网中不存在入度为0的顶点为止。

3.AOE网

定义：若在带权有向图G中以顶点表示事件，以有向边表示活动，以边上的权值表示该活动持续的时间，则这种带权有向图称为用边表示活动的网（AOE网）。

通常在AOE网中列出了完成预定工程计划所需进行的活动、每项活动的计划完成时间、活动开始或结束的事件以及这些事件和活动间的关系，从而可以分析该项工程是否实际可行并估计工程完成的最短时间，以及影响工程进度的关键活动；进一步可以进行人力、物力的调度和分配，以达到缩短工期的目的。

在用AOE网表示一项工程计划时，

• 顶点：某些活动已经完成，某些活动可以动工的标志；
• 顶点发出的边表示活动可以开始。

入度为0的开始顶点，称为源点；出度为0的结束顶点，称为汇点。

在AOE网中不应存在有向回路，否则整个工程无法完成。

4.关键路径和关键活动

从源点到汇点的路径中，长度最长的路径称为关键路径。

关键路径上的所有活动均是关键活动。

如果任何一项关键活动没有按期完成，就会影响整个工程的进度。引入顶点事件的最早、最晚发生事件，活动的最早、最晚开始时间等概念，来说明关键路径和关键活动。

（1）顶点的最早发生时间

顶点的最早发生时间ve(j)，是指从源点v0到汇点vj的最长路径长度（时间）。这个时间决定了所有从vj发出的弧所表示的活动能够开工的最早时间。

顶点最早发生时间的计算方法为：

顶点最早发生时间

（2）顶点的最晚发生时间

顶点事件最晚发生事件vl(i)，是指在不推迟整个工期的前提下，事件vi的最晚发生时间。

对于一个工程来说，计划用几天时间完成是可以从AOE网求得，其数值就是汇点的最早发生时间，而这个时间也是最晚发生时间。其他顶点事件的最晚发生时间应从汇点开始，逐步向源点方向递推才能得到。

顶点最晚发生时间的计算公式为：

顶点最晚发生时间

（3）活动的最早开始时间

活动最早开始时间e(k)，是指弧<i,j>所表示的活动ak最早可开工时间。（e(k) = ve(i)）

活动的最早开始时间等于事件的最早发生时间。

（4）活动的最晚开始时间

活动最晚开始时间l(k)，是指在不推迟整个工期的前提下，该活动的最晚开始时间。

（五）最短路径

1.单源点最短路径

定义：单源点最短路径，是指给定带权有向图G和源点v0，求从v0到G中其余各顶点的最短路径。

2.每对顶点间的最短路径

若每次以一个顶点为源点，重复执行迪杰斯特拉算法n次，便可求得网中每一对顶点之间的最短路径。