问问天笔记
数据结构 第 6 / 9 篇

第六章 图

4,601 字约 12 分钟

一 图的定义和基本术语

填空题

  1. 图形结构简称为图，图G由两个集合V和E组成，定义为G=（V，E），其中V是顶点的有限非空集合，E是由V中顶点偶对表示的边的集合。通常，V（G）和E（G）分别表示图G的顶点集合和边集合。E（G）也可以为空集，即图G只有顶点而没有边。
  2. 图分为有向图和无向图两种。对于一个图G，若每条边都是有方向的，则称该图为有向图。在有向图中，一条有向边是由两个顶点组成的有序对，通常用尖括号表示。对于一个图G，若每条边都是没有方向的，则称该图为无向图。在一个无向图中，边均是顶点的无序对，通常用圆括号表示。

单选题，解答题，图的常用术语如下：

  1. 出边，入边，起点和终点，<vi, vj>就表示一条有向边，此边称为顶点vi的一条出边，顶点vj的一条入边；称vi为起始端点（或起点），vj为终止端点（或终点）。
  2. 弧，弧头和弧尾，在有向图中，一条有向边是由两个顶点组成的有序对，通常用尖括号表示。有向边又称为弧，边的起点称为弧尾，边的终点称为弧头。
  3. 端点和邻接点，在无向图中，若存在一条边（vi，vj），则称顶点vi，vj为该边的两个端点，并称它们互为邻接点，或称vi，vj相邻接。在有向图中，若<vi，vj>是一条边，则称顶点vi邻接到vj，顶点vj邻接于顶点vi。
  4. 无向完全图和有向完全图，通常用n表示图中的顶点数，用e表示图中边或弧的数目，并且在下面的讨论中不考虑顶点到自身的边，即若（vi，vj）或<vi，vj>是E（G）的一条边，则要求vi != vj。因此对于无向图，e的取值范围是0～n(n-1)/2。我们将具有n(n-1)/2条边的无向图称为无向完全图。同理，对于有向图，e的取值范围是0～n(n-1)，称具有n(n-1)条边或弧的有向图为有向完全图。
  5. 入度，出度和顶点的度，在无向图中，顶点v的度定义为以该顶点为一个端点的边的数目，记为D(v)。对于有向图G，顶点v的度分为入读度ID(v)和出度OD(v)。入度是以该顶点为终点的入边数目。出度是以该顶点为起点的出边数目，该顶点的度等于其入度和出度之和。一般地，如果顶点vi的度为D(vi)，那么，不管是有向图或是无向图，顶点数n，边数e和度数之间有如下关系：
e=1/2∗[∑i=1n D(vi) ]e = 1/2 *[ \sum_{i=1}^\frac n\ D(v_i) \ ]
  1. 路径和路径长度，在无向图G中，若存在一个顶点序列vp, vi1, vi2, …, vim, vq, 使得（vp， vi1）,（vi1，vi2），…, （vim， vq）均属于E(G)，则称顶点vp到vq存在一条路径。如果G是有向图，则路径也是有向的。路径长度是指一条路径上经过的边的数目。
  2. 简单路径和回路（环），若一条路径上除了起点和终点可以为同一个顶点外，其余顶点均不相同的路径称为一条简单路径。若一条简单路径上的起点和终点为同一个顶点，则称该路径为回路或环。
  3. 连通，连通图和连通分量，在无相同G中，如果从顶点vi到顶点vj有路径，则称vi和vj是连通的。若图G中任意两个顶点vi和vj都是连通，则称G为连通图。无向图的极大连通子图称为连通分量。
  4. 强连通图和强连通分量，在有向图G中，如果对任意两个顶点vi和vj都连通，即从vi到vj和从vj到vi都存在路径，则称图G是强连通图。有向图的极大连通子图称作有向图的强连通分量。
  5. 权，带权图和网络，若在一个图的每条边上标上某种数值，该数值称为改变的权。边上带权的图称为带权图，带权的连通图称为网络，其权值往往是具有某种意义的数。

二 图存储结构

填空题，解答题

邻接矩阵是表示图形中顶点之间相邻关系的矩阵。设G = （V，E）是具有n个顶点的图，则G的邻接矩阵是具有如下定义的n阶方阵：

1 若（vi，vj）或<vi, vj>是E(G)的边

A[i][j] =

0 若（vi, vj）或<vi, vj>不是E（G）的边

解答题

邻接表是图的一种链式存储结构，这种存储表示法类似于树的孩子链表表示法。邻接表中每一个表结点有两个域：其一为邻接点域adjvex，用以存放与顶点vi相邻接的顶点vj的序号j；其二为指针域next，用来将邻接表的所有结点链在一起。如果要表示边上的权值，那么就要再增设一个数据域。另外，为每个顶点vi的邻接表设置一个具有两个域的表头结点：一个域是顶点信息域vertext，另一个则是指针域（指向邻接表）link，它是vi的邻接表的头指针。为了便于随机访问任一顶点的邻接表，需要把这n个表头用一个一维数组存储起来，这个数组（向量）就构成了图的邻接表的表示，其中第i个分量存储vi邻接表的表头指针。这样，图G就可以由这个表头数组来表示和存取。

填空题

将无向图邻接表称为边表，将有向图的邻接表称为出边表，将邻接表的表头向量称为顶点表。

单选题

图的邻接表表示不是唯一的，这是因为再每个顶点的邻接表中，各边结点的链接次序可以是任意的，其具体链接次序与边的输入次序和生成算法有关。

三 图的遍历

解答题

深度优先搜索（Depth First Search, DFS）遍历类似于树的前序（先根）遍历。假设初始状态是图中所有顶点都未曾访问过，则可从图G中任选一个顶点v为初始出发点，首先访问出发点v，并将其标记为已访问过；然后依次从v出发搜索v的每个邻接点w，若w未曾访问过，则以w作为新的出发点出发，继续进行深度优先遍历，直到图中所有和v有路径相通的顶点都被访问到；若此时图中仍有顶点未被访问，则另选一个未曾访问的顶点作为起点，重复上述过程，直到图中所有的顶点都被访问到为止。

填空题

对于图的深度优先搜索遍历，若采用邻接矩阵表示，其算法的时间复杂度为O(n**2)，若采用邻接表表示，其时间复杂度为O(n+e)。

解答题

广度优先搜索(Breadth First Search, BFS)遍历类似于树的按层次遍历。其基本思想是啊：首先访问出发点vi，接着依次访问vi的所有未被访问过的邻接点vi1，vi2, vi3, vit并标记为已访问过，然后再按照vi1, vi2, …, vit的次序，访问每一个顶点的所有未曾访问过的顶点并均标记为已访问过，依次类推，直到图中所有和初始出发点vi有路径相通的顶点都被访问过为止。

填空题

对于图的广度优先搜索遍历，若采用邻接矩阵表示，其算法时间复杂度为O(n**2)，若采用邻接法表示，其时间复杂度为O(n+e)。

四 图的生成树和最小生成树

填空题

在图论中，常常将树定义为一个无回路的连通图。一个连通图G的一个子图如果是一棵包含G的所有顶点的树，则该子图称为G的生成树。生成树是连通图的包含图中所有顶点的一个极小连通子图（边最少）。一个图的极小连通子图恰为一个无回路的连通图。也就是说，若图中任意添加一条边，就会出现回路；若在图中去掉任意一条边都会使之成为非连通图。因此，一棵具有n个顶点的生成树有仅有n-1条边，但是n-1条边的图不一定是生成树。

解答题

我们把生成树各边的权值总和称为该树的权，把权值最小的生成树称为图的最小生成树（Mininum Spanning Tree, MST）。MST性质：假设N=(V, {E})是一个连通网，U是顶点集V的一个非空子集，若（u, v）是一条具有最小权值的边，其中u属于U，v属于V-U，则必存在一棵包含（u, v）的最小生成树。

填空题

常用的构造最小生成树的算法只有两种，即普里姆算法和克鲁斯卡尔****算法。

解答题

  1. 普里姆（Prime）算法的基本思想是：假设G=（V，G）是一个具有n个顶点的连通网，T=（U，TE）是G的最小生成树，其中U是T的顶点集，TE是T的边集，U和TE的初始值均为空。算法开始时，首先从V中任取一个顶点（假定取v1），将它并入U中，此时U={v1}。然后只要U是V的真子集（即U包含于V）， 就从那些一个端点已在T中，另一个端点仍在T外的所有边中，找一条最短（即权值最小）边，假定为（vi, vj）,其中vi 属于 U，vj属于V-U，并把该边（vi，vj）的顶点vj分别并入T的边集TE和顶点集U，如此进行下去，每次往生成树里并入一个顶点和一条边，直到n-1次后把所有n个顶点都并入到生成树T的顶点集中，此时U=V，TE中中包含有n-1条边，T就是最后得到的最小的生成树。
  2. 克鲁斯卡尔（Kruskal）算法的基本思想是：假设G=（V，E）是一个具有n个顶点的连通网，T=(U, TE)是G的最小生成树，U的初始值等于V，即包含有G中的全部顶点。T的初始状态是只含有n个顶点而无边的森林T=（V，&）。算法开始时，将图G中的边按照权值从小到大的顺序依次选取E中的边（u, v），若选取的边使生成树T不形成回路，则把它并入TE中，保留作为T的一条边；若选取的边使生成树T形成回路，则将其舍弃，如此进行下去直到TE中包含n-1条边为止，此时的T记为最小生成树。

五 最短路径

解答题

  1. 单源最短路径问题：从某个源点 S属于V 到G中其余各顶点的最短路径。对于求多源点的最短路径问题，可以用每个顶点作为源点调用一次单源最短路径问题算法予以解决。
  2. 迪杰斯特拉（Dijkstra）算法求最短路径的实现思想是：设有向图G=（V，E），其中V={1,2,3,..,n}，cost是表示G的邻接矩阵，cost[i][j]表示有向边<i, j>的权。若不存在有向边<i, j>，则cost[i][j]的权为无穷大（假定取值为32767）。设S是一个集合，其中的每个元素表示一个顶点，从源点到这些顶点的最短距离已经求出。设顶点v1为源点，集合S的初态只包含顶点v1。数组dist记录从源点到其他各顶点当前的最短距离，其初始值为dist[i]=cost[v1][i]，i=2,…,n。从S之外的顶点集合V-S中选出一个顶点w，使dist[w]的值最小。从源点到达w只通过S中的顶点，把w加入集合S中并调整dist中记录的从源点到V-S中每个顶点v的距离，即从原来的dist[v]和dist[w]+cost[w][v]中选择较小的值作为新的dist[v]。重复上述过程，直到S中包含V中其余顶点的最短路径。

六 拓扑排序

填空题

  1. 通常，我们把用顶点表示活动，边表示活动间先后关系的有向无环图（Directed Acyclic Graph, DAG）称为顶点活动网，简称AOV网。
  2. 对于一个有向无环图（DAG），若将G中所有顶点排成一个线性序列，使得图中任意一对顶点u和v，若<u, v>属于E（G），则u在线性序列中出现在v之前，这样的线性序列称为拓扑序列。

解答题，拓扑排序思想描述如下

  1. 在有向图中选一个没有前趋（入度为零）的顶点，且输出之。
  2. 从有向图中删除该顶点及其与该顶点有关的所有边。
  3. 重复执行上述两个步骤，直到全部顶点都已输出或图中剩余的顶点中没有前趋（入度为零）顶点为止。
  4. 输出剩余的无前趋结点。