已知无向连通图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。要求:
⑴ 给出算法的基本设计思想。
⑵ 根据设计思想，采用C或C++语言描述算法，关键之处给出注释。
⑶ 说明你所设计算法的时间复杂度和空间复杂度。
思想：从任意顶点开始深度优先遍历，每当该顶点与其他顶点存在一条边时，该顶点的度数加1，以此完成对所有顶点度的统计，最终要求度为奇数的顶点个数为0或者2。并且要求在遍历的过程中统计连通分量的个数，要求该图为连通图，则连通分量个数为1。
代码：
int countoddDegree==0 //统计度为奇数的顶点个数void DFS(MGraph G,int v,bool visited[]) {visited[v]==true;//访问该顶点int degree=0;//记录顶点的度for(int i=0;i<G.numvertices;++i){if(G.edges[v][i]!=0){//存在边 degree++;//度数+1 if(visited[i]==false){//顶点i还未被访问 DFS(G,v,visited);//深度优先i }}} if(degree%2==1){//度为奇数 countoddDegree++}
}
//以深度优先的方式来验证图是否为连通图
DFSTraverse(MGraph G,int &numConnected){//统计访问情况bool *visited = (bool*)malloc(sizeof(bool)*G.numVertices);for(int v=0;v<G.numVertices;++v){//初始化visited数组 visited[v]=false;} for(int v=0;v<G.numVertices;++v){if(visited[v]==false){//未被访问，进行深度优先 numConnected++;// 统计连通分量的个数 +1DFS(G,v,visited);}} free(visited);
}
//判断是否存在EL路径
int isExistEL(MGraph G){int numConnected = 0;//统计连通分量的个数 DFSTraverse (G,numConnected);//连通分量为1表示图为连通的，度为奇数的顶点个数为0或者2 return numConnected==1&&(countoddDegree==0 ||countoddDegree==2) ? 1:0;
} 时间复杂度O（n^2），空间复杂度O（n）
