6.1.1 基本概念

1. 树的定义及基本术语

(1) 图(Graph)。图G是由两个集合V(G)和E(G)组成的，记为G=(V，E)。

其中：V(G)是顶点的非空有限集。

　　　E(G)是边的有限集合，边是顶点的无序对或有序对。

(2) 有向图。有向图G是由两个集合V(G)和E(G)组成的。

其中：V(G)是顶点的非空有限集。

　　　E(G)是有向边(也称弧)的有限集合，弧是顶点的有序对，记为〈v，w〉，v，w是顶点，v为弧尾，w为弧头。

(3) 无向图。无向图G是由两个集合V(G)和E(G)组成的。

其中：V(G)是顶点的非空有限集。

　　　E(G)是边的有限集合，边是顶点的无序对，记为(v,w)或(w,v)，并且(v，w)=(w，v)。

(4) 有向完全图。n个顶点的有向图最大边数是n(n-1)。

(5) 无向完全图。n个顶点的无向图最大边数是n(n-1)/2。

(6) 权。与图的边或弧相关的数。

(7) 网。带权的图。

(8) 子图。如果图G(V，E)和图G＇(V＇，E＇)满足：

①V＇⊆V，

②E＇⊆E，

则称G＇为G的子图。

(9) 顶点的度。

无向图中，顶点的度为与每个顶点相连的边数。

有向图中，顶点的度分成入度与出度。

① 入度：以该顶点为头的弧的数目。

② 出度：以该顶点为尾的弧的数目。

(10) 路径。路径是顶点的序列V={v_i0，v_i1，…，v_in}，满足(v_ij-1，v_ij)∈E或〈v_ij-1，v_ij〉∈E，(1＜j≤n)。

(11) 路径长度。沿路径边的数目或沿路径各边权值之和。

(12) 回路。第一个顶点和最后一个顶点相同的路径。

(13) 简单路径。序列中顶点不重复出现的路径。

(14) 简单回路。除了第一个顶点和最后一个顶点外，其余顶点不重复出现的回路

(15) 连通。从顶点V到顶点W有一条路径，则说V和W是连通的。

(16) 连通图。图中任意两个顶点都是连通的。

(17) 连通分量。非连通图的每一个连通部分。

(18) 强连通图。有向图中，如果对每一对v_i，v_j∈V，v_i≠v_j，从v_i到v_j和从v_j到v_i都存在路径，则称G是强连通图。

2. 图的存储表示

(1) 数组表示法(邻接矩阵)

用两个数组分别存储数据元素(顶点)的信息和数据元素之间的关系(边或弧)的信息。

以二维数组表示有n个顶点的图时，需存放n个顶点信息和n²个弧信息的存储量。图的邻接矩阵定义为方阵A：用A[i][j]描述顶点v_i与v_j之间是否有边相连。

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

借助于邻接矩阵容易判定任意两个顶点之间是否有边(或弧)相连，并容易求得各个顶点的度。对无向图，顶点v_i的度是邻接矩阵中第i行(或第i列)的元素之和，即

TD（v_i)A[i][j]n=MAX_VERTEX_NUM)。

对有向图，第i行的元素之和为顶点的出度OD(vi)，第j列的元素之和为顶点的入度ID(vj)。

网的邻接矩阵元素定义为：

图的数组表示法适合于边稠密的图。

(2) 邻接表

邻接表是图的一种链式存储结构，在邻接表中，对图中每个顶点建立一个单链表，第i个单链表中的结点表示依附于顶点v_i的边(对有向图是以顶点v_i为尾的弧)。

若无向图有n个顶点、e条边，则它的邻接表需n个头结点和2e个表结点。在边稀疏(e≪n(n-1)/2)的情况下，用邻接表表示图比用邻接矩阵节省存储空间。

在无向图的邻接表中，第i个链表中的结点个数恰好为顶点vi的度。而在有向中第i个链表中的结点个数只是顶点vi的出度，为求入度，必须遍历整个邻接表。为了便于确定顶点的入度或以顶点为头vi的弧，可以建立逆邻接表，即对每个顶点vi建立一个以vi为头的边的链接表。

在邻接表上容易求任一顶点的第一个邻接点和下一个邻接点。

(3) 十字链表

十字链表是将有向图的邻接表和逆邻接表结合起来得到的一种链表。在十字链表中，对应于有向图中每一条弧有一个结点，对应于每个顶点也有一个结点。在十字链表中容易求得顶点的出度和入度。

(4) 邻接多重表

邻接多重表是无向图的另一种链式存储结构。在邻接表中，每一条边(vi,vj)有两个结点，分别在第i个和第j个链表中，给某些操作带来不便。在邻接多重表中，所有依附于同一顶点的边串联在同一链表中，由于每条边依附于两个顶点，则每个边结点同时连接在两个链表中。邻接多重表和邻接表的差别在于同一条边在邻接表中用两个结点表示，而在邻接多重表中只有一个结点。

3. 图的遍历

图的遍历的定义：从图中某一顶点出发访遍图中其余顶点，且使每一个顶点仅被访问一次。

(1) 深度优先搜索DFS(Depth_First Search)

遍历过程描述为：从图中某个顶点v₀出发，访问此顶点，然后依次从v₀的未被访问的邻接点出发，深度优先遍历图，直到图中所有和v₀有路径相通的顶点都被访问到，若此时图中尚有顶点未被访问，则另选图中一个未曾被访问的顶点作始点，重复上述过程，直到图中所有顶点都被访问到为止。

从描述可见，图的深度优先搜索是一个递归过程。深度优先遍历图的过程，实质上是对每个顶点查找其邻接点的过程。若用邻接矩阵作存储结构，则时间复杂度为O(n²)，若用邻接表作存储结构，则时间复杂度为O(n+e)。

(2) 广度优先搜索BFS(Breadth_First Search)

遍历过程描述为：从图中某顶点v₀出发，在访问v₀之后依次访问v₀的各个未曾访问过的邻接点，然后分别从这些邻接点出发广度优先遍历图，直到图中所有已被访问的顶点的邻接点都被访问到，若此时图中尚有顶点未被访问，则另选图中一个未曾被访问的顶点作起始点，重复上述过程直到图中所有顶点都被访问到为止。广度优先遍历图的过程是以v₀为始点，由近及远依次访问和v₀连通且路径长度为1,2,…的顶点。

广度优先搜索和深度优先搜索的时间复杂度相同，不同之处在于对顶点访问的顺序不同。

4. 最小(代价)生成树MST

最小生成树的性质：假设N=(V，{E})是一个连通网，U是顶点集V的一个非空子集，若(u，v)是一条具有最小权值(代价)的边，其中u∈U,v∈V-U，则必存在一棵包含边(u，v)的最小生成树。

普里姆(Prim)算法和克鲁斯卡尔(Kruskal)算法是两个利用最小生成树性质构造最小生成树的算法。

(1) 普里姆(Prim)算法。假设N=(V，{E})是连通网，TE是N上最小生成树中边的集合。算法从U={u₀}(u₀∈V)，TE={}开始，重复执行下述操作：在所有u∈U，v∈V-U的边(u，v) ∈E中找一条代价最小的边(u₀，v₀)并入集合TE，同时v₀并入U，直至U=V为止。此时TE中必有n-1条边，则T=(V，{TE})为N的最小生成树。

(2) 克鲁斯卡尔(Kruskal)算法。假设N=(V，{E})是连通网，则令最小生成树的初始状态为只有n个顶点而无边的非连通图T=(V，{})，图中每个顶点自成一个连通分量。在E中选择代价最小的边，若该边依附的顶点落在T中不同的连通分量上，则将此边加入到T中，否则舍去此边而选择下一条代价最小的边。依次类推，直至T中所有顶点都在同一连通分量上为止。

普里姆算法的时间复杂度为O(n²)(与网中边数无关)，适用于求边稠密的网的最小生成树。而克鲁斯卡尔算法的时间复杂度为O(eloge),适用于求边稀疏的网的最小生成树。

5. 有向无环图及其应用

一个无环的有向图称为有向无环图(Directed Acycline Graph)简称DAG图。有向无环图是描述含有公共子式的表达式的有效工具，也是描述一项工程或系统的进行过程的有效工具。

(1) 拓扑排序

拓扑排序就是由某个集合上的一个偏序得到该集合上的一个全序的操作。

用顶点表示活动，用弧表示活动间的优先关系的有向图称为顶点表示活动的网(Activity On Vertex Network),简称AOV网。对给定的AOV网应首先判定网中是否存在环。检测的办法是对有向图构造其顶点的拓扑有序序列，若网中所有顶点都在它的拓扑有序序列中，则该AOV网中必定不存在环。拓扑排序算法如下：

① 在有向图中选一个没有前趋的顶点且输出之；

② 从图中删除该顶点和所有以它为尾的弧。

重复以上两步，直至全部顶点均已输出，或者当前图中不存在无前趋的顶点为止。后一种情况则说明有向图中存在环。

该算法的时间复杂度为O(n+e)。注意到，拓扑排序结果不一定唯一。

也可利用深度优先搜索进行拓扑排序拓扑排序。

(2) 关键路径

与AOV网对应的是AOE网(Activity On Edge)即边表示活动的网。AOE网是一个带权的有向无环图，其中顶点表示事件(Event)，弧表示活动，权表示活动持续的时间。通常，AOE网可用来估算工程的完成时间。

路径长度最长的路径叫做关键路径。最早开始时间等于最迟开始时间的活动称为关键活动。关键路径上的所有活动都是关键活动，提前完成非关键活动并不能加快工程的进度。

求关键路径的时间复杂度为O(n+e)。

只有在不改变网的关键路径的情况下，提高关键活动的速度才有效。若网中由几条关键路径，必须同时提高几条关键路径上的活动速度才能缩短整个工程。

6. 最短路径

(1) 从某个源点到其余各顶点的最短路径

迪杰斯特拉(Dijkstra)的按路径长度递增的次序产生最短路径的算法。算法描述为：

① 假设用带权的邻接矩阵arcs来表示带权有向图，arcs[i][j]表示弧＜v_i,v_j＞上的权值。若＜v_i,v_j＞不存在，则置arcs[i][j]为∞。S为已找到从出发的最短路径的终点的集合，它的初始状态为空集。那么，从出发到图上其余各顶点(终点)v_i可能达到的最短路径长度的初值为：

D[i]=arcs[Locate Vex(G,v)[i] v_v∈V

② 选择v_j，使得

D[j]=min{D[i] | ∈V-S}

v_j就是当前求得的一条从出发的最短路径的终点。令v

S=S∪{j}

③ 修改从v出发到集合V-S上任一顶点v_k可达的最短路径长度。如果

D[j]+arcs[j][k]＜D[k]

则修改D[k]为D[k]=D[j]+arcs[j][k]

④重复操作(2)、(3)共n-1次。由此求得从到图上其余各顶点的最短路径是依路径长度递增的序列。

v

算法时间复杂度是O(n²)。

(2) 每一对顶点之间的最短路径

方法一：每次以一个顶点为源点，重复执行迪杰斯特拉算法n次，便可求得每一对顶点之间的最短路径。总的执行时间为O(n³)。

方法二：弗洛伊德(Floyd)算法。其执行时间也是O(n³)。弗洛伊德算法描述如下：

定义n阶方阵序列：D^(-1)，D⁽⁰⁾，D⁽¹⁾，…，D^(k)，…，D^(n-1)

其中：

　　D^(-1)[i][j]=arcs[i][j]

　　D^(k)[i][j]=min{D^(k-1)[i][j],D^(k-1)[i][k]+D^(k-1)[k][j] }， 0≤k≤n-1

D^(k)[i][j]是从v_j到v_i的中间顶点的序号不大于k的最短路径长度，D

(n-1)[i][j] 是从v_i到v_j的最短路径的长度。