(13分)对于有向图，如果一个顶点的出度大于入度，则这

第1题

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

typedef struct{
int numVertex, numEdge;//顶点数，边数
char VertexList[MAXV];//顶点表
int Edge[MAXV][MAXV];//邻接矩阵
}MGraph;

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

(1)说明算法思想(占5-6分)

(2)用C/C++实现算法(占7-8分)

[参考答案]

(1)算法思想：遍历有向图中所有顶点，并统计各顶点的出度和入度，输出出度大于入度的KJ页点，并使用变量 count 累计顶点的总数。

计算顶点i的出度: 遍历邻接矩阵的i行元素，即 Edge[i][0]~Edge[i][numVertex-1]，统计非零元素个数，即为顶点i的出度

计算顶点i的入度：遍历邻接矩阵的i列元素，即Edge[0][i]~ Edge[numVertex-1][i]，统计非零元素个数，即为顶点i的入度

(2)算法实现：

int printVertices (MGraph G){
    int count =0;//K顶点的总数
    for (int i=0; i<G.numVertex; i++){
        int outDegree = 0;//顶点i的出度
        int inDegree = 0;//顶点i的入度
        for (int j=0;j<G.numVertex; j++)
            if (G.Edge[i][j]>0)  outDegreet+;
        }
        for (int j=0;j<G.numVertex; j++)
            if (G.Edge[j][i]>0)  outDegreet+;//循环两次方便理解
        }
        if (outDegree > inDegree) [//顶点i的出度大于入度
            printf ("c\n"，G.VertexList[i]);//输出顶点i
            count++;//累加K顶点总数
        }
     }
     return count;//返回x顶点总数
}