第 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) 说明你所设计算法的时间复杂度和空间复杂度。
[tag_link]
1）算法的基本设计思想本算法题属于送分题，题干已经告诉我们算法的思想。对于采用邻接矩阵存储的无向图，在邻接矩阵的每一行（列）中，非零元素的个数为本行（列）对应顶点的度。可以依次计算连通图 G 中各顶点的度，并记录度为奇数的顶点个数，若个数为 0 或 2，则返回 1，否则返回 0。
2）算法实现
int isExistEL(MGraph G) {
// 统计度为奇数的定点个数
int count = 0;
for (int v = 0; v < numVertices; v++) {
// 该顶点的度
int degree = 0;
for (int e = 0; e < numEdges; e++) {
if (Edge[v][e] == 1) {
degree++;
}
}
if (degree % 2 == 1) {
count++;
}
}
if (count == 0 || count == 2) {
return 1;
}
return 0;
}
3）时间和空间复杂度算法需要遍历整个矩阵，所以时间复杂度为O(n2)，空间复杂度为O(1)。