考研笔记

板子：邻接矩阵上统计度数（2021、2023）

邻接矩阵里，第 行非零元素的个数是顶点 的出度，第 列非零元素的个数是入度。无向图的矩阵是对称的，行里的个数就是度。两年的真题都是用两重循环数一数。

代码

int IsExistEL(MGraph G) {                    // 2021：无向连通图中，度为奇数的顶点有 0 个或 2 个时返回 1
    int odd = 0;                             // 度为奇数的顶点个数
    for (int i = 0; i < G.numVertices; i++) {
        int deg = 0;                         // 顶点 i 的度
        for (int j = 0; j < G.numVertices; j++)
            if (G.Edge[i][j] != 0) deg++;    // 数第 i 行里有几条边
        if (deg % 2 == 1) odd++;
    }
    return (odd == 0 || odd == 2) ? 1 : 0;   // 原题：「不大于 2 的偶数」，0 也算
}
 
int printVertices(MGraph G) {                // 2023：输出所有出度大于入度的顶点（K 顶点），返回个数
    int cnt = 0;
    for (int i = 0; i < G.numVertices; i++) {
        int outd = 0, ind = 0;
        for (int j = 0; j < G.numVertices; j++) {
            if (G.Edge[i][j] != 0) outd++;   // 第 i 行：从 i 出发的边，算出度
            if (G.Edge[j][i] != 0) ind++;    // 第 i 列：指向 i 的边，算入度
        }
        if (outd > ind) {                    // 严格大于
            printf("%c ", G.VerticesList[i]);
            cnt++;
        }
    }
    return cnt;
}
 
void degreeAL(ALGraph &G, int outd[], int ind[]) {   // 邻接表：扫一遍所有边表，同时求出度和入度
    for (int i = 0; i < G.vexnum; i++) outd[i] = ind[i] = 0;
    for (int i = 0; i < G.vexnum; i++)
        for (ArcNode *p = G.vertices[i].firstarc; p != NULL; p = p->nextarc) {
            outd[i]++;                       // 这条边从 i 出发
            ind[p->adjvex]++;                // 指向 adjvex
        }
}

复杂度：两道真题都是时间 、空间 ；邻接表版时间 、空间 （不算结果数组）。

考场答案要点

  • 2021（EL 路径）：原题已经给出判断条件（度为奇数的顶点个数是不大于 2 的偶数），不需要自己证明。设计思想写成：「遍历邻接矩阵，求每个顶点的度（第 行非零元素个数），统计度为奇数的顶点个数，个数为 0 或 2 就返回 1，否则返回 0」。
  • 2023（K 顶点）：设计思想写成：「对每个顶点 ，第 行非零元素个数为出度，第 列非零元素个数为入度，出度大于入度就输出该顶点并计数」。
  • 两题的函数原型都是按值传 MGraph G，照题目写即可。

关键边界

位置为什么
行是出、列是入Edge[i][j] != 0 表示有一条 的边。所以看第 行得到从 出发的边，看第 列得到指向 的边
2021 判据写 odd == 0 或 odd == 2原题说「不大于 2 的偶数」，0 个也满足（此时存在欧拉回路）
2023 用 outd > ind原题要求出度大于入度，相等的顶点不算
数边写 != 0真题是 0/1 矩阵。写成「非零就计数」，换成带权矩阵时也不会把权值当成边数加进去

易错点

  • 邻接表求入度要扫描全部边表，这是教材专门强调的一点：求出度只看自己的边表，求入度就得看所有顶点的边表。
  • 无向图的每条边在矩阵里出现两次。求边数时只数上三角，或者把总数除以 2。

链接

反向链接