（一）图的定义与存储
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次，便可求得网中每一对顶点之间的最短路径。
网友评论