【数据结构】——图简答题模板

前言

关于二叉树和图的知识点比较多，并且考试中也非常针对性地考察，需要多加思考和熟练背诵相关知识点。

一、图的定义

1、什么是无向图？什么是有向图？

答：按照图中的边是否有方向性，可以分为有向图和无向图，即一个图的前驱和后继关系没有区别，则为无向图；而一个图的前驱和后继关系有区别，则为有向图。

二、连通图及强连通图

（一）连通图的定义

1、什么是连通图？什么是强连通图？

答：连通图指的是无向图，强连通图指的是有向图。在无向图中，任意两个结点都是连通的（任意两个结点之间有路径），则该图为连通图；而在一个有向图中，任意两个不同的顶点都存在相互之间的路径，则称为强连通图。

（二）连通分量和强连通分量

1、简述什么是连通分量和强连通分量？

答：无向图的极大连通子图称为连通分量，类似，有向图的极大强连通子图称为强连通分量。

（三）连通图的边的个数

1、具有n个顶点的连通图，至少有多少条边？至多有多少条边？

答：一个含有n个顶点的无向连通图，构成一棵树时图中边数最少，有n-1条边；而当无向完全图时图中边数最多，有n(n-1)/2条边。

三、图的遍历

（一）图的深度优先遍历思想

1、说明图的深度优先遍历算法思想。

答：图的深度优先遍历（DFS）需要借助栈来遍历：
①首先，选取图中某一顶点v_i作为起始点访问；
②任意选取一个与v_i邻接的顶点，且该顶点未被访问，一直重复下去，直到图中所有与v_i连通的顶点都被访问到；【可概括为由起始顶点开始，沿着一条路径尽可能深入地搜索图，直到无法再继续下去】
③若还有顶点未被访问到，则另外选取一个未被访问的顶点再次作为起始点，回溯到上一个未访问的顶点，重复以上步骤，直至图中所有结点被访问。

（二）图的广度优先遍历思想

1、说明图的广度优先遍历算法思想。

答：图的广度优先搜索（BFS）需要借助到队列来遍历：
①首先，选取图中某一顶点v_i作为出发点，访问后将其入队并标记为已访问（使用队列用于避免重复访问，存放已经访问过的各邻接顶点）；
②依次访问与v_i邻接的顶点，即当队列不为空时检查出队顶点的所有邻接顶点，访问未被访问的邻接顶点并将其入队，重复该过程；【可概括为由起始顶点开始，按照广度优先的顺序逐层遍历与当前顶点相邻的顶点将其访问】
③当队列为空时跳出循环，即所有已被访问的顶点的邻接顶点均被访问到，则此时遍历完成。

（三）图的遍历思想判断连通图

1、如何利用图的遍历算法来判断一个图是否是连通图？

答：两种遍历算法都可以用于判断图的连通性，图的深度优先遍历和广度优先遍历中，若在遍历中，所有的顶点都被访问到，则图是连通的，否则，图是不连通的。

四、图的存储结构

（一）图的存储结构的定义

1、图有哪两种常用的存储结构？另外还有哪些存储结构？

答：图的常用存储结构有邻接矩阵和邻接表，另外还有十字链表、邻接多重表等等。

图的邻接矩阵用于表示顶点之间的相邻关系，其中通过一个一维数组存储顶点，一个二维数组存储顶点之间的相邻关系，一个顶点数为n的图的邻接矩阵是n×n（n行n列）；邻接表采用顺序存储结构和链式存储结构来存储图，对于图中每个顶点vi，将所有邻接于vi的顶点连成一个单链表，即这个单链表就称为顶点vi的邻接表，另外还需将所有顶点的邻接表放进数组中，通过邻接表存储图所用的空间大小取决于图的顶点数和边的个数，顶点数n决定了顶点表的空间大小，边的个数决定了边表结点的空间大小。

（二）存储结构的选择

1、求有向图中每个顶点的入度和出度，采用哪种存储结构更为方便？为什么？

答：邻接矩阵，因为有向图的邻接矩阵中，第i行非零元素的个数和第i列非零元素的个数对应该顶点的出度OD(vi)和入度ID(vi)，又由于有向图中度等于出度和入度之和，即顶点vi的度为其邻接矩阵中第i行和第i列的非零元素的个数之和。而若采用邻接表，则需要遍历一个链表，才能求有向图中每个顶点的入度和出度。

（三）邻接矩阵的优缺点

1、简述图的邻接矩阵存储结构的优缺点。

答：优点是可以很方便地从矩阵中通过值等于0或1来判断两个顶点是否存在边；另外还可以便于计算每个顶点的度，对于无向图，行之和为顶点的度，而对于有向图，行之和为顶点出度，列之和为顶点入度，即顶点的度为第i行和第i列的非零元素的个数之和。

缺点是空间复杂度较高，对于n个顶点的有向图需要n²个存储单元来存储，而对于n个顶点的无向图通过压缩存储只需要n(n-1)/2个存储单元来存储，两个的空间复杂度均为O(n²)，特别是对于稀疏图来说浪费存储空间。

（四）邻接表的优缺点

1、简述图的邻接表存储结构的优缺点。

答：优点是空间利用率高，对于稀疏图（边数相对较少的图）来说，邻接表可以有效地节省存储空间，其中每个顶点只需要存储其相邻顶点的信息；由于是一种链式数据结构，所以可以很方便地添加或删除顶点；另外，其查找效率高，通过链式结构，每个顶点都有一个链表存储其相邻顶点的信息，只需遍历该链表即可找到所有相邻顶点，而在邻接矩阵中，需要扫描整行或整列才能找到所有相邻顶点。

缺点是需要额外的空间存储边信息，每个顶点都需要存储其相邻顶点的信息，需要额外的空间；由于需要遍历邻接表中的所有边才能判断出，需要花费较高的时间复杂度，所以无法直接判断两个顶点是否存在边；另外，由于每个顶点的相邻顶点信息存储在链表中，需要遍历该链表才能计算出该顶点的度。

（五）邻接多重表的定义

1、简述图的邻接多重表的定义及该存储结构解决了哪些问题？

答：该存储结构对于无向图，将一条边的两个顶点存放在边表结点中，而将邻接于同一个顶点的边串联在顶点表结点中，即邻接多重表，它是邻接表的改进方法。这种存储方式解决了邻接表在存储无向图时同一条边要存储两次的问题，即一条边只需一个结点来记录，避免了同一条边的重复存储，提高了空间存储效率。

（六）十字链表的定义

1、简述图的十字链表的定义及该存储结构解决了哪些问题？

答：该存储结构对于有向图，中图的每个顶点都有两个链表，一个是以该顶点为起点的弧，另一个是以该顶点为终点的弧，将邻接表和逆邻接表结合起来，同时存储每个顶点的出度和入度，从而很方便地找到有向图顶点的入度和出度信息。

五、图的应用

（一）普里姆算法（Prim）

1、简述最小生成树的Prim算法的基本步骤。

答：每次从图中任取一个顶点与当前加入的树中顶点集合距离最近的顶点，并将该顶点和相应的边加入树，直到所有顶点都并入树中，得到最小生成树。

（二）克鲁斯卡尔算法（Kruskal）

1、简述Kruskal算法求最小生成树的思想。

答： 一个含n个顶点的图，克鲁斯卡尔算法的思想是将图的所有边对应的权值按照从小到大的顺序依次开始选取，若选取的某边与先前的树构成回路，则舍去，一直进行下去，直到所有顶点被访问到，当生成树的边的个数为n-1时为止，即可得到最小生成树。

（三）最短路径

1、Dijkstra算法和Floyd算法两者求解最短路径区别是什么？

答：①求解目的不同，Dijkstra算法适用于图中某源点到其他顶点的最短路径问题，而Floyd算法适用于图中任意两点之间的最短路径问题；
②时间复杂度不同，对于图G=（V，E），其中|V|表示图中顶点的数量，Dijkstra算法的时间复杂度为O(|V|²)，而Floyd算法的时间复杂度为O(|V|³)。

（四）拓扑排序

1、简述拓扑排序的步骤。

答：对于一个AOV网进行拓扑排序，其步骤如下：
1、从网中找选择一个没有前驱，即入度ID(v)=0的顶点；
2、删除该顶点且删除由该顶点的所有起始边（出度的边），并将该顶点输出；
3、重复(1)和(2)步骤，直至AOV网为空或不存在没有前驱的结点为止；
4、最后得到一个序列，即拓扑排序。

2、通过对AOV网进行拓扑排序得到的序列可以有多个，说法对吗？为什么？

答：正确，AOV网的拓扑排序的序列不止一个，也可以有多个，是由于当网中有多个入度为0的顶点时，进行拓扑排序，从而得到的序列不止一种。

（五）关键路径

1、简述关键路径的求解过程。

答：关键路径的求解步骤如下：
1、根据所给的图，求得该图的拓扑有序序列和逆拓扑有序序列；
2、通过得到的序列，先对事件，求得每个事件的最早发生时间和最迟发生时间；
3、根据(2)得到的结果，再对活动，求得每个活动的最早发生时间和最迟发生时间；
4、根据(3)得到的结果，找到最早发生时间和最迟发生时间相同的活动，就得到了关键活动，由关键活动连成的路径即为关键路径。