题7

题7

题目

【2021 统考真题】已知无向连通图 由顶点集 和边集 组成, ,当 中度为奇数的顶点个数为不大于 2 的偶数时, 存在包含所有边且长度为 的路径 (称为 EL 路径)。设图 采用邻接矩阵存储, 类型定义如下:

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. 说明你所设计算法的时间复杂度和空间复杂度。

分析

题41
题3

解

1. 算法的基本设计思想

本算法题属于送分题, 题干已经告诉我们算法的思想。对于采用邻接矩阵存储的无向图, 在邻接矩阵的每一行 (列) 中, 非零元素的个数为本行 (列) 对应顶点的度。可以依次计算连通图 中各顶点的度,并记录度为奇数的顶点个数,若个数为 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) 。