2023年的专业408算法题

0 结果

1 题目

对于一个有向图，如果一个顶点的出度大于入度，则这个顶点称为K顶点。有向图用邻接矩阵存储，数据结构定义如下：

typedef struct {
    int numVertices, numEdges;//顶点数、边数
    char VerticesList[MAXV];//顶点表
    int Edge[MAXV][MAXV];//邻接矩阵
}MGraph;

要求实现函数int printVertices(MGraph G)，输出有向图中所有K顶点，并返回K顶点的总数。

要求：

（1）说明算法思想；
（2）用C/C++实现算法 。

2 思路

遍历有向图的所有顶点，并统计各顶点的入度（矩阵第i行元素个数）和出度（矩阵第i列的元素个数），输出出度大于入度的K顶点，使用count变量统计K顶点的总数。

3 实现

举例的图（摘自《王道》）：

#include<iostream>
#include <vector>
const int MAXV = 6;//例c取值：6  例a取值：4

typedef struct {
    int numVertices, numEdges;//顶点数、边数
    char VerticesList[MAXV];//顶点表
    int Edge[MAXV][MAXV];//邻接矩阵
}MGraph;

int printVertices(MGraph G){
    int count = 0;//K顶点总数
    for (int i = 0; i < G.numVertices; ++i) {
        int in_degree = 0, out_degree = 0;
        for (int j = 0; j < G.numVertices; ++j) {
            if(G.Edge[i][j] > 0) out_degree++;
        }
        for (int j = 0; j < G.numVertices; ++j) {
            if(G.Edge[j][i] > 0) in_degree++;
        }
        if(out_degree > in_degree){
            count++;
            std::cout<<"K顶点为："<<G.VerticesList[i]<<"\n";
        }
    }
    return count;
}


int main(){
    MGraph G;

    //例a：
//    for (int i = 0; i < 4; ++i) {
//        for (int j = 0; j < 4; ++j) {
//            G.Edge[i][j] = 0;
//        }
//    }
//    G.Edge[0][1] = 1;
//    G.Edge[0][2] = 1;
//    G.Edge[2][3] = 1;
//    G.Edge[3][0] = 1;
//    G.numVertices = 4;
//    G.numEdges = 4;
//    G.VerticesList[0] = '1';
//    G.VerticesList[1] = '2';
//    G.VerticesList[2] = '3';
//    G.VerticesList[3] = '4';

    //例c
    for (int i = 0; i < MAXV; ++i) {
        for (int j = 0; j < MAXV; ++j) {
            G.Edge[i][j] = 0;
        }
    }
    G.Edge[0][1] = 5;
    G.Edge[1][2] = 4;
    G.Edge[2][0] = 8;
    G.Edge[2][5] = 9;
    G.Edge[3][2] = 5;
    G.Edge[3][5] = 6;
    G.Edge[4][3] = 5;
    G.Edge[5][0] = 3;
    G.Edge[5][4] = 1;
    G.numVertices = 6;
    G.numEdges = 9;
    G.VerticesList[0] = '1';
    G.VerticesList[1] = '2';
    G.VerticesList[2] = '3';
    G.VerticesList[3] = '4';
    G.VerticesList[4] = '5';
    G.VerticesList[5] = '6';

    std::cout<<printVertices(G)<<"\n";

    return 0;
}

附录

408历年真题算法题解析