完全图的分类和比较

完全图是图论中的一个基本概念。它指的是$n$个顶点之间全部连通，且除每个顶点连向自身外，每个顶点与其余$n-1$个顶点均有连边的无向图。本文将从分类和比较两个角度出发，对完全图进行分析。

一、分类

根据完全图的性质，我们将其可以分为以下两类：

1. 无向完全图

无向完全图是一种没有方向的无向图，其中$n$个顶点之间共有$\dfrac{n(n-1)}{2}$条无向边，如图1所示。

（图1 无向完全图）

2. 有向完全图

有向完全图是一种有方向的图，其中$n$个顶点之间共有$n(n-1)$条有向边，如图2所示。

（图2 有向完全图）

二、比较

在实际应用中，无向完全图和有向完全图具有不同的特点和作用。

1. 应用领域不同

无向完全图主要应用于无向图的相关问题，例如：最小生成树、最短路径、最大匹配等问题。而有向完全图则主要应用于有向图的相关问题，例如：强连通分量、最长路径、最小网络流等问题。

2. 存储方式不同

由于有向完全图边的个数比无向完全图多，在存储上有所不同。对于无向完全图，可以使用邻接矩阵或邻接表进行存储。而对于有向完全图，邻接表的存储方式比邻接矩阵更为常见，因为邻接表只需要存储有向边，可以节省存储空间。

3. 图的连通性不同

由于完全图中任意两个顶点之间都有边相连，因此无向完全图和有向完全图均为强连通图和弱连通图。但是，无向完全图的连通性更强，任意两个顶点之间的路径长度较短，更易于实现算法求解。而有向完全图的连通性相对较弱，需要通过增加边权或修改图结构等方式来使其具有更强的连通性。

4. 算法性能不同

在使用同一个算法时，无向完全图和有向完全图的算法性能也有所不同。例如，在使用Dijkstra算法求解最短路径问题时，由于无向完全图的边权都是非负数，每次选取距离源点最近的未访问顶点时时间复杂度是$O(n)$，总的时间复杂度为$O(n^2)$；而在有向完全图中，每次选取距离源点最近的未访问顶点时需要遍历所有的顶点，时间复杂度为$O(n^2)$，因此总的时间复杂度为$O(n^3)$。