很楠不爱3

这个屌丝很懒，什么也没留下！

热门标签

数据结构 | 【图】考研相关结论与例题_拓补排序讨论是否可以通过选定一个入度为零的点作为出发点对一个有向图进行深度

作者：很楠不爱3 | 2024-02-06 21:15:29

踩

拓补排序讨论是否可以通过选定一个入度为零的点作为出发点对一个有向图进行深度

一、知识点

1）图的基本概念

1、图的定义

线性表可以是空表，树可以是空树，但图不可以是空图。
并非V和E的任何子集都能构成G的子图，因为这样的子集可能不是图，即E的子集中的某些边关联的顶点可能不在这个V的子集中。
极大连通子图是无向图的连通分量，极大即要求该连通子图包含其所有的边；
极小连通子图是既要保持图连通又要使得边数最少的子图。
如果图本来就不是连通的，那么每个子部分若包含它本身的所有顶点和边，则它就是极大连通子图。
图中有关路径的定义是由顶点和相邻顶点序偶构成的边所形成的序列。

连通：在无向图中，若从顶点v到顶点w有路径存在，则称v和w是连通的。若图G中任意两顶点都是连通的，那么图G为连通图，否则称为非连通图。
连通分量：无向图中的极大连通子图称为连通分量。
单独的顶点构成一个强连通分量。
强连通：这属于有向图的概念。若从顶点v到顶点w和从顶点w到顶点v之间都有路径，则称这两个顶点是强连通的。若图中任意两顶点都是强连通的，那么图G为强连通图。
强连通分量：有向图中的极大强连通子图称为有向图的强连通分量。

2、无向图的结点数、边数、度数、连通性、强连通性等性质之间的关系

含有n个顶点的无向图：
无向完全图有n(n - 1) / 2条边。
连通无向图的边的个数至少为 n-1。对于连通无向图，边至少构成一棵树的情形;
当有 $C_{n-1}^2+1$ 个边时，能确保是一个连通图。
无向图的全部顶点的度的和等于边数的2倍。

3、有向图的结点数、边数、度数、连通性、强连通性等性质之间的关系

含有n个顶点的有向图：
有向完全图有 n (n - 1) 条有向边。
强连通有向图的边的个数至少为 n 。对于强连通有向图，边最少构成一个单向环的情形。
有向图的全部顶点的入度之和与出度之和相等，并且等于 n 。（每条有向边都有一个起点和终点）
每个顶点的度最大可达 2n-2 。

4、对无向连通图做一次深度优先搜索，可以访问到所有顶点。

5、若有向图中存在拓扑序列，则该图不存在回路。

6、图的遍历就是从图中某一顶点出发访遍图中其余结点（错误，若图非连通）

7、环路：

最短路径首先是不允许有负环的，因为如果有负环，那在负环路径上的节点可以绕着负环无穷多圈从而。
那么可不可以有正环呢，答案是否定的，可以用反证法证明，如果有正环，那么显然去掉正环后的路径的权值肯定比带正环的路径更小。所以最短路径是不包含环路的，而且单源节点到所有节点的最短路径构成一颗最短路径树。

8、n个节点的二叉树数目：卡特兰数 $\frac{C_{2n}^{n}}{n+1}$

2）图的存储及其基本操作

1、邻接矩阵

无向图的邻接矩阵一定是对称矩阵（且唯一），可采用压缩存储。
空间复杂度O(n^2)，n为顶点数。
A^n：元素A[i][j]等于由顶点i到顶点j的长度为n的路径的数目。
在有向图的邻接矩阵中，0和无穷表示的都不是有向边。

2、邻接表存储

若G为无向图，则所需的存储空间为O(|V| + 2|E|)；
若G为有向图，则所需的存储空间为O(|V| + |E|)。
图的邻接表表示并不唯一。

3、十字链表（有向图）

顶点结点之间是顺序存储的。
在十字链表中，既容易找到vi为尾的弧，又容易找到vi为头的弧，因而容易求得顶点的出度和入度。

4、邻接多重表（无向图）

在邻接表中，容易求得顶点和边的各种信息，但在邻接表中求两个顶点之间是否存在边而对边执行删除等操作时，需要分别在两个顶点的边表中遍历，效率最低。

5、假设有n个顶点、e条边的有向图用邻接表表示，则删除与某个顶点v相关的所有边的时间复杂度为O(n + e)。

6、广度优先搜索中邻接表的时间复杂度为O(|V| + |E|)，我们可得：对于邻接表的时间复杂度的计算要从顶点数和边数两个角度考虑。

7、若邻接矩阵对角线以下（或以上）的元素全为0，则图中必然不存在环，即拓扑序列一定存在，但不能说明拓扑序列唯一。

3）图的遍历

1、广度优先搜索（BFS）

空间复杂度：O(|V|)
时间复杂度：邻接表：O(|V| + |E|) 邻接矩阵：O(|V|^2)
广度优先生成树
在广度遍历的过程中，我们可以得到一棵遍历树，称为广度优先生成树。
当各边权值相等时，BFS可用来解决单源最短路径问题

2、深度优先搜索（DFS）

时间空间复杂度类似于广度优先搜索。
对连通图调用DFS才能产生深度优先生成树，否则产生的将是深度优先生成森林。

对于给定图，基于邻接矩阵的遍历所得到的DFS序列和BFS序列是唯一的，
基于邻接表的遍历所得到的DFS序列和BFS序列是不唯一的。
邻接表存储的图的深度优先遍历算法类似于树的先序遍历，
而其广度优先遍历算法类似于树的按层次遍历。

3、图的遍历与图的连通性

非强连通分量一次调用BFS（G，i）或DFS（G，i）无法访问到该连通分量的所有顶点。

4、DFS（或BFS）可用来计算图的连通分量个数。—— 见例题

5、利用深度优先遍历可以判断图G中是否存在回路。

对于无向图来说，若深度优先遍历过程中遇到了回边，则必定存在环；对于有向图来说，这条回边可能是指向深度优先森林中另一棵生成树上的顶点的弧；但是，从有向图的某个顶点V出发进行深度优先遍历时，若在DFS(v)结束之前出现一条从顶点u到顶点v的回边，且u在生成树上是v的子孙，则有问图必定存在包含顶点v和顶点u的环。

4）图的应用

1、最小生成树

Prim算法的时间复杂度为O(|V|2)，适用于求解边稠密的图的最小生成树。
Kruskal算法的时间复杂度为O(|E|log|E|)，适合于边稀疏而顶点较多的图。

2、最短路径

Dijkatra算法的时间复杂度为O(|V|2)。不适用于带有边带有负权值的图。
Floyd算法的时间复杂度为O(|V|3)。允许图中有带负权值的边，但不允许有包含带负权值的边组成的回路。

3、拓扑排序

时间复杂度为O(|V| + |E|)。
若一个顶点有多个直接后继，则拓扑排序的结果通常不唯一。

4、关键路径

    在AOE网中仅有一个入度为0的点，也仅有一个出度为0的点。
    关键路径上的所有活动都是关键活动。
    网中的关键路径并不唯一，且对于有几条关键路径的网，只提高一条关键路径上的关键活动速度并不能缩短整个工程的工期。

5、深度优先遍历和拓扑排序可以判断出一个有向图是否有环。

6、

若一个有向图的顶点不能排成一个拓扑序列，则判定该有向图含有顶点数大于1的强连通分量。
若一个有向图具有有序的拓扑排序序列，则他的邻接矩阵必定为：三角（去掉拓扑，则填一般）
若用邻接矩阵存储有向图，矩阵中主对角线以下的元素均为零，则该图拓扑序列存在且可能不唯一。
由偏序得到全序的过程才叫拓扑排序，这样得到的序列才叫拓扑排序序列。
有向图的邻接矩阵为三角矩阵是该图拓扑序列存在（不存在环）的充要条件。

有向无环图的拓扑序列唯一并不能唯一确定该图。
~~若有向无环图的拓扑序列唯一，则可以唯一确定该图。错误~~
~~若有向图的拓扑有序序列唯一，则图中每个顶点的入度和出度最多为1。错误~~

拓扑排序算法暂存入度为0的顶点，可以使用栈或者队列。
最短路径一定是简单路径。

二、习题

1、图的定义与存储结构

1、若具有n个顶点的图是一个环，则它有（）棵生成树。

【解析】因为n个顶点构成的环共有n条边，去掉其中任意一条便是一棵生成树，所以共有n种情况。

【答案】n

2、下列关于无向连通图特性的叙述中，正确的是（）。

Ⅰ．所有顶点的度之和为偶数

Ⅱ．边数大于顶点个数减1

Ⅲ．至少有一个顶点的度为1

【解析】每条边都连接了两个结点，在计算顶点的度之和时每条边都被计算了两次（出度和入度），故所有顶点的度之和为边数的两倍，I正确。n个顶点、n-1条边可以构成无向连通图，比如树，Ⅱ错误。顶点数为N（N≥1）的无向完全图中不存在度为1的顶点，画出一个环，这样每个顶点的度都为2 同时满足无向连通。Ⅲ错误。

【答案】仅一

3、若一个具有n个顶点，e条边的无向图是一个森林，则该森林必有多少棵树？

【解析】

设森林中有x棵树，把每棵树根连起来（需要用 x-1 条边连接）构成一棵新的树，也满足树的性质，因此有

连接后边的数目为 n - 1 = x - 1 + e，所以 x = n - e

【答案】n-e

4、如何对无环有向图中的顶点号重新安排使得该图的邻接矩阵中所有的1都集中到对角线以上？

【解析】有两种方法，如下：

方法一：

1>将顶点号的出度根据大小进行排序，出度最大的顶点编号为1，依次到出度最小的顶点编号为n。
2>调整，只要存在弧<i,j>,无论两个顶点出度的大小，都要使顶点i的序号在顶点j的序号前，（i<j）。

方法二：采用拓扑排序对顶点号重新安排。

5、假设有n个顶点，e条边的有向图用邻接表表示，则删除与某个顶点v相关的所有边的时间复杂度是？

【解析】O(n+e)

首先，删除顶点v邻接的边，O(n-1)。

然后遍历边表（剩余全部顶点表结点及其指向的边表），删除所有v的入边。O(n+e)

2、DFS与BFS

1、对于一个非连通无向图G，采用深度优先遍历访问所有顶点，在DFSTraverse函数(见考点讲解DFS部分)中调用DFS的次数正好等于（）。

A．顶点数

B．边数

C．连通分量数

D．不确定

【解析】

①现在要遍历的是一个<非连通>无向图

②DFS一次可以遍历一个完整的连通图

DFS（或BFS）可用来计算图的连通分量个数，因为一次遍历必然会将一个连通图中的所有顶点都访问到，而对于已经被访问的结点不在调用，故选择C。

连通分量的概念：极大连通子图，也就是“非连通图是由多少连通子图构成的”。

2、用DFS遍历一个无环有向图，并在DFS算法退栈返回时打印相应的顶点，则输出的顶点序列是( )。
A.逆拓扑有序    B.拓扑有序    C.无序的    D.无法确定

【解析】
DFS（深度优先遍历）是一个递归算法,在遍历的过程中,先访问的点被压入栈底（栈是先进后出）,再说：拓扑有序是指如果点U到点V有一条弧,则在拓扑序列中U一定在V之前.深度优先算法搜索路径恰恰是一条弧,栈的输出是从最后一个被访问点开始输出,最后一个输出的点是第一个被访问的点.所以是逆的拓扑有序序列

如果是队列：拓扑有序

如果是栈：逆拓扑有序

3、判断一个有向图是否存在回路，除了可以利用拓扑排序方法外，还可以利用（）

A 求关键路径的方法
B 求最短路径的Dijkstra方法
C 深度优先遍历算法
D 广度优先遍历算法

【解析】

A:有争议。求关键路径的前提是无环图。在求关键路径前就需要进行判断是否有环。

B:逐个获得某结点的最短路径。如果存在回路会怎么样?不会怎么样，照样是在排除/采用路径而已。

C:深度优先遍历：如果在遍历过程中欲访问结点已在栈中，则证明有回路。

利用深度优先遍历可以判断图G中是否存在回路。对于无向图来说，若深度优先遍历过程中遇到了回边，则必定存在环；对于有向图来说，这条回边可能是指向深度优先森林中另一棵生成树上的顶点的弧；但是，从有向图的某个顶点V出发进行深度优先遍历时，若在DFS(v)结束之前出现一条从顶点u到顶点v的回边，且u在生成树上是v的子孙，则有问图必定存在包含顶点v和顶点u的环。

D:广度优先遍历：遍历过程中无法检测环，因为是广度优先，形成环的路径是没有被考虑进遍历过程的。

【答案】C （dfs）

3、图的应用

1、下面哪一方法可以判断出一个有向图是否有环（回路）：（）

A.深度优先遍历

B.拓扑排序

C.求最短路径

D.求关键路径

【解析】

Ⅰ：可以判断。在遍历过程中如果遇到要访问的结点已在栈中就是有环。

［深度优先遍历］的概念：
假定每一个点都没被访问过。从起点开始，找邻接的点。
对每个点，只要存在有向的路径，查找就可以继续，顺藤摸瓜（同时把经过的点给标记成“已访问”）。一旦遇到“已访问”就表示，有环路。

Ⅱ：拓扑是求是判断是否有回路的正统。找不到拓扑序列必定有环。

对于有向图的拓扑排序,

1、计算图中所有点的入度，把入度为0的点加入栈

2、如果栈非空：取出栈顶顶点a，输出该顶点值，删除该顶点

3、从图中删除所有以a为起始点的边，如果删除的边的另一个顶点入度为0，则把它入栈

4、如果图中还存在顶点，则表示图中存在环；否则输出的顶点就是一个拓扑排序序列

Ⅲ：求最短路径本身是不需要有环无环的条件的，因此自然无法判断。

Ⅳ：有争议。求关键路径的前提是无环图。在求关键路径前就需要进行判断是否有环。

【答案】AB

2、以下关于拓扑排序的说法中错误的是（）
I. 如果某有向图存在环路，则该有向图一定不存在拓扑排序
II. 在拓扑排序算法中，为暂存入度为零的顶点可以使用栈，也可以使用队列
III. 若有向图的拓扑有序序列唯一，则图中每个顶点的入度和出度最多为1

【解析】

Ⅰ：没问题。拓扑与有环不可兼得。

Ⅱ：没问题，只要入度为0，以什么样的顺序（栈or队列）都没问题。

Ⅲ：不正确。因为是有向图的原因，所以出入度不可能单1。

【答案】III

3、下列关于图的说法中，正确的是（）。

Ⅰ．(有向图中顶点V的度等于其邻接矩阵中第v行中1的个数

Ⅱ．无向图的邻接矩阵一定是对称矩阵，有向图的邻接矩阵一定是非对称矩阵

Ⅲ．在图G的最小生成树G1中，可能会有某条边的权值超过未选边的权值

IV．如果有向无环图的拓扑序列唯一，则可以唯一确定该图

【解析】

Ⅰ．有向图的度=出度+入度。邻接矩阵第v行中1的个数=出度。不完整。

Ⅱ．无向图的邻接矩阵一定是对称矩阵v，但是有向图的邻接矩阵不一定是非对称矩阵!

Ⅲ．没问题。如果这个选项不对的话，就意味着最小生成树一定是权值最小的n-1条边构成?

IV．拓扑序列唯一，并不能直接画出来图。直接最简例子即可得。