数据结构
2021-41
已知无向连通图G由顶点集V和边集E组成，|E|>0，当G中度为奇数的顶点个数不大于2的偶数时，G存在包含所有边且长度为|E|的路径（称为EL路径）。设图G采用邻接矩阵存储，类型定义如下：
typedef struct {
int numVertices, numEdges; // 图的定义
char VerticesList[MAXV]; // 顶点表。MAXV为已定义常量
int Edge[MAXV][MAXV]; // 邻接矩阵
} MGraph;请设计算法 int IsExistEL(MGraph G)，判断 G 是否存在 EL 路径，若存在，则返回1，否则返回0。要求：
1）给出算法的基本设计思想。
2）根据设计思想，采用 C 或 C++语言描述算法，关键之处给出注释。
3）说明你所设计算法的时间复杂度和空间复杂度。
答案
（1）基本设计思想：统计图中度数为奇数的顶点个数。若该个数为0或2，则存在包含所有边且长度为|E|的路径（即欧拉路径），返回1；否则返回0。
（2）算法描述（C/C++语言）：
int IsExistEL(MGraph G) {
int degree, i, j, count = 0;
for (i = 0; i < G.numVertices; i++) {
degree = 0; // 初始化记录度的变量
for (j = 0; j < G.numVertices; j++) {
degree = degree + G.Edge[i][j]; // 记录各点的度
}
if (degree % 2 != 0)
count++; // 度为奇数的顶点计数
}
if (count == 0 || count == 2) // 度为奇数的点数量是0或2
return 1;
else
return 0;
}（3）时间复杂度：O(n²)，其中n为顶点数（numVertices）。空间复杂度：O(1)，仅使用常数额外空间。