|
|
|
|
|
图G是由两个集合V和E构成的二元组，记作G=(V,E)，其中V是图中顶点的非空有限集合，E是图中边的有限集合。从数据结构的逻辑关系来看，图中任一顶点都有可能与图中其他顶点有关系，而图中所有顶点都有可能与某一顶点有关系。在图中，数据结构中的数据元素用顶点表示，数据元素之间的关系用边表示。
|
|
|
|
（1）有向图。若图中每条边都是有方向的，则称G为有向图。顶点间的关系用<vi，vj>表示，它说明从vi到vj的一条有向边（也称为弧），vi是有向边的起点，称为弧尾；vj是有向边的终点，称为弧头。
|
|
|
|
（2）无向图。若图中的每条边都是无方向的，则顶点vi和vj之间的边用(vi,vj)表示。
|
|
|
|
（3）无向完全图。若一个无向图具有n个顶点，而每一个顶点与其他n-1个顶点之间都有边，则称之为无向完全图。显然，含有n个顶点的无向完全图共有n(n-1)/2条边。
|
|
|
|
（4）有向完全图。有n个顶点的有向完全图中弧的数目为n(n-1)，即任何两个不同顶点之间都有方向相反的两条弧存在。
|
|
|
|
（5）度、入度和出度。顶点的度是指关联于该顶点的边的数目，记为D(v)。若G为有向图，顶点的度表示该顶点的入度和出度之和。顶点的入度是指以该顶点为终点的有向边的数目，而顶点的出度是指以该顶点为起点的有向边的数目，分别记为ID(v)和OD(v)。无论是有向图还是无向图，顶点数n、边数e与各顶点的度之间有
|
|
|
|
|
|
（6）路径。在无向图G中，从顶点vp到顶点vq的路径是指存在一个顶点序列vp，vi1，vi2，…，vin，vq，使得(vi1,vp)，(vi1,vi2)，…，(vin,vq)均属于E(G)。
|
|
|
|
（7）子图。对于两个图G=(V,E)和G'=(V',E')，如果V'是V的子集，E'是E的子集，则称G'为G的子图。
|
|
|
|
（8）连通图。在无向图G中，若从顶点vi到顶点vj有路径，则称顶点vi和顶点vj是连通的。如果无向图G中任意两个顶点都是连通的，则称其为连通图。无向图G的极大连通子图称为G的连通分量。
|
|
|
|
（9）强连通图。在有向图G中，如果对于每一对顶点vi，vj且vi≠vj，从顶点vi到顶点vj和从顶点vi到顶点vi都存在路径，则称图G为强连通图。也就是说，如果V(G)中任意两个不同的顶点vi和vj，都存在从vi到vj以及从vj到vi的路径，则称G是强连通图。
|
|
|
|
|
|
（11）生成树。一个连通图的生成树是一个极小的连通子图，它包含图中的全部顶点，但只有构成一棵树的n-1条边。
|
|
|
|
（12）有向树和生成森林。如果一个有向图恰有一个顶点的入度为0，其余顶点的入度均为1，则是一棵有向树。有向图的生成森林由若干棵有向树组成，含有图中全部顶点，但只有足以构成若干棵不相交的有向树的弧。
|
|
|
|
|
|
|
|
对于具有n个顶点的图G(V,E)来说，其邻接矩阵是一个n阶方阵，且满足
|
|
|
|
|
|
由邻接矩阵的定义可知，无向图的邻接矩阵是对称的，有向图的邻接矩阵就不一定对称了。借助邻接矩阵易判定任意两个顶点之间是否有边（或弧）相连，并且容易求得各个顶点的度。
|
|
|
|
|
|
|
|
|
|
邻接链表指的是为图的每个顶点建立一个单链表，第i个单链表中的节点表示依附于顶点vi的边（对于有向图是以vi为尾的弧）。邻接链表中的节点有表节点和表头节点两种类型。
|
|
|
|
|
|
|
|
|
|
从图G中任一个顶点v出发，深度优先遍历（DFS）的算法步骤如下。
|
|
|
|
|
|
（2）访问p顶点，并使p指向与p顶点相邻接的且尚未被访问过的顶点。
|
|
|
|
（3）若p不空，则重复步骤（2）；否则执行步骤（4）。
|
|
|
|
（4）沿着刚才访问的次序、方向回溯到一个尚有邻接顶点且未被访问过的顶点，并使p指向这个未被访问的邻接顶点，然后重复步骤（2），直至所有的顶点均被访问为止。
|
|
|
|
这个算法的特点是尽可能先对纵深方向搜索，因此可以很容易得到其遍历的递归算法。
|
|
|
|
深度优先遍历图的过程实质上是对某个顶点查找其邻接节点的过程，其耗费的时间取决于所采用的存储结构。当图用邻接矩阵表示时，查找所有顶点的邻接点所需时间为O(n2)。若以邻接表作为图的存储结构，则需要O(e)的时间复杂度查找所有顶点的邻接点。因此，当以邻接表作为存储结构时，深度优先搜索遍历图的时间复杂度为O(n+e)。
|
|
|
|
|
|
广度优先遍历（BFS）的遍历过程是：假设从图中某一个顶点v出发，在访问v之后依次访问v的各个未被访问过的邻接点，然后分别从这些邻接点出发依次访问它们的邻接点，并使"先被访问的顶点的邻接点"先于"后被访问的顶点的邻接点"被访问，直至图中所有已被访问过的顶点的邻接点都被访问到。若此时还有未被访问的顶点，则另选其中一个作为起点，重复上述过程，直至图中所有的顶点都被访问到为止。
|
|
|
|
广度优先遍历图的特点是尽可能先进行横向搜索，即最先访问的顶点的邻接点亦先被访问。
|
|
|
|
|
|
|
|
设图G=(V,E)是个连通图，当从图中任一个顶点出发遍历图G时，将边集E(G)分为两个集合，即A(G)和B(G)。其中A(G)是遍历时所经过的边的集合，B(G)是遍历时未经过的边的集合。G1=(V,A)是图G的子图，称子图G1为连通图G的生成树。
|
|
|
|
图的生成树不是唯一的。选择不同的存储方式，从不同的顶点出发，可以得到不同的生成树。对于非连通图而言，每个连通分量中的顶点集和遍历时走过的边集一起构成若干棵生成树，把它们称为非连通图的生成树森林。
|
|
|
|
|
|
对于连通网来说，边是带权值的，生成树的各边也带权值，如果把生成树各边的权值总和称为生成树的权，则把权值最小的生成树称为最小生成树。
|
|
|
|
构造生成树有多种算法，其中多数算法利用了最小生成树的MST性质：假设G=(V,E)是一个连通图，U是顶点集V的一个非空子集。若(u,v)是一条最小权值的边，其中u∈U,v∈V-U，则必存在一棵包含边(u,v)的最小生成树。
|
|
|
|
①普里姆算法。它的时间复杂度为O(n2)，与图中的边数无关，因此该算法适合于求边稠密的网中的最小生成树。
|
|
|
|
②克鲁斯卡尔算法。它的时间复杂度为O(elog2e)，与图中的顶点数无关，因此该算法适合于求边稀疏的网的最小生成树。
|
|
|
|
|
|
|
|
在有向图中，若一顶点表示活动，用有向边表示活动之间的优先关系，则称这样的有向图为以顶点表示活动的网，简称AOV网。
|
|
|
|
在AOV网中不应出现有向环。不存在回路的AOV网称为有向无环图或DAG图。检测的方法是对有向图构造其从顶点开始的拓扑有序序列，若图中所有顶点都在它的拓扑有序序列中，则该AOV网中必定不存在环。
|
|
|
|
|
|
拓扑排序是将AOV网中所有顶点排成一个线性序列，该序列满足：若在AOV网中从顶点vi到vj有一条路径，则在该线性序列中，顶点vi必然在顶点vj之前。拓扑排序即指对AOV网构造拓扑序列的操作。
|
|
|
|
|
|
（1）在AOV网中选择一个入度为零的顶点且输出它。
|
|
|
|
|
|
（3）重复上述两步，直至网中不存在入度为零的顶点为止。
|
|
|
|
若在AOV网中考察各顶点的出度，并按下列步骤进行排序，则称为逆拓扑排序。
|
|
|
|
（1）在AOV网中选择一个没有后继的顶点且输出它。
|
|
|
|
（2）从网中删除该顶点，并删去所有到达该顶点的弧。
|
|
|
|
（3）重复上述两步，直至网中不存在出度为零的顶点为止。
|
|
|
|
|
|
|
|
若在带权有向图G中以顶点表示事件，以有向边表示活动，边上的权值表示该活动持续的时间，则这种带权有向图称为用边表示活动的网，简称AOE网。
|
|
|
|
|
|
|
|
从源点到汇点的路径中，长度最长的路径称为关键路径。关键路径上的所有活动均是关键活动。如果任何一项关键活动没有按期完成，则会影响整个工程的进度，而提高关键活动的速度可以缩短整个工程的工期。假设在n个顶点的AOE网中，顶点v0表示源点，顶点vn-1表示汇点，则计算关键活动及关键路径时可引入以下术语。
|
|
|
|
.顶点事件的最早发生时间ve(j)。它是指从源点v0到vj的最长路径长度（时间）。
|
|
|
|
.顶点事件的最晚发生时间v1(i)。它是指在不推迟整个工程完成日期的前提下，事件vi所允许的最晚发生时间。
|
|
|
|
.活动的最早开始时间e(k)。表示活动ak最早可开工时间。
|
|
|
|
.活动的最晚开始时间l(k)。它是指在不推迟整个工程完成日期的前提下，允许该活动最晚开始的时间。
|
|
|
|
|
|
|
|
单源点最短路径是指给定带权有向图G和源点v，求从v到G中其余各顶点的最短路径。迪杰斯特拉提出了按路径长度递增的次序产生最短路径的算法。
|
|
|
|
|
|
若每次以一个顶点为源点，重复执行迪杰斯特拉算法n次，便可求得网中每一对顶点之间的最短路径。弗洛伊德提出了求最短路径的算法，该算法在形式上要简单一些。
|
|
|
