数据结构
2023-41
已知有向图G采用邻接矩阵存储，类型定义如下：
typedef struct {
int numVertices, numEdges;
char VerticesList[ MAXV ];
int Edge[ MAXV ][ MAXV ];
} MGraph;将图中出度大于入度的顶点称为 K 顶点。例如在题 41 图中，顶点 a 和 b 为 K 顶点。
请设计算法：int printVertices(MGraph G)，对给定的任意非空有向图 G，输出 G 中所有的 K 顶点，并返回 K 顶点的个数。要求：
1）给出算法的基本设计思想。
2）根据设计思想，采用 C 或 C++ 语言描述算法，关键之处给出注释。
答案
(1) 算法的基本设计思想
遍历有向图G的邻接矩阵，对每个顶点计算出度和入度。出度为该顶点对应行中非零元素个数，入度为该顶点对应列中非零元素个数。若出度大于入度，则输出该顶点并计数。最后返回K顶点的个数。
(2) 算法实现（C/C++）
int printVertices(MGraph G){
int indegree, outdegree, k, m, count = 0;
for (k = 0; k < G.numVertices; k++) {
indegree = outdegree = 0;
for (m = 0; m < G.numVertices; m++) { // 计算出度
outdegree += G.Edge[k][m];
}
for (m = 0; m < G.numVertices; m++) { // 计算入度
indegree += G.Edge[m][k];
}
if (outdegree > indegree) {
printf("%c", G.VerticesList[k]);
count++;
}
}
return count; // 返回K顶点的个数
}