（15 分）已知无向连通图 G 由顶点集 V 和边集

第1题

（15 分）已知无向连通图 G 由顶点集 V 和边集 E 组成|E|>0，当 G 中度为奇数的顶点个数 为不大于 2 的偶数时，G 存在包含所有边且长度为|E|的路径(称为 EL 路径)，设图 G 采用邻接 矩阵存储，类型定义如下：

Typedef struct{
                                    //图的定义 
int numVertices，numEdges; 
                                    //图中实际的顶点数和边数 
Char VertticesList[MAXV]; 
                                    //顶点表。MAXV 为已定义常量 
Int Edge[MAXV][MAXV];
                                    //邻接矩阵 
};MGraph;

请设计算法：int IsExistEL(MGraph G)，判断 G 是否存在 EL 路径，若存在，则返回 1，否则，返回 0，要求： 

（1）给出算法的基本设计思想。 

（2）根据设计思想采用 C 或者 C++语言描述算法，关键之处给出注释。 

（3）说明你所设计算法的时间复杂度和空间复杂度。

【答案解析】

（1）算法的基本设计思想

对于采用邻接矩阵存储的无向图，邻接矩阵每一行（列）中非零元素的个数为本行（列）对应顶点的度。可以依次计算连通图 G 中各顶点的度，并记录度为奇数的顶点个数，若个数为 0或 2，则返回 1，否则返回 0。

（2）算法实现

Int IsExistEL(MGraph G)
                   //采用邻接矩阵存储，判断图是否存在 EL 路径
{ int degree,i,j, count=0;
 for(i=0;I<G.numVertices;i++)
 { degree=0;
 for(j=0;j<G.numVertices;j++)
                   //依次计算各个顶点的度
 degree+=G.Edge[i][j];
 if(degree%2!=0)
 count++;   //对度为奇数的顶点计数
}
if（count ==0 || count == 2）
 return 1；  //存在 EL 路径，返回 1
else
 return 0；  //不存在 EL 路径，返回 0
}

（3）算法的时间复杂度和空间复杂度

本参考答案给出的算法的时间复杂度是 O（n^2），空间复杂度是 O（1）。