给定任意非空有向图 G，输出 G 中所有 K 顶点的算法，并返回 K 顶点的个数。

已知优先图 G 采用邻接矩阵存储是，其定义如下

typedef struct {                    // 图的定义
    int numVertices, numEdges;      // 图中实际的顶点数和边数
    char VerticesList[MAXV];        // 顶点表，MAXV为已定义常量
    int Edge[MAXV][MAXV];           // 邻接矩阵
}MGraph;

将图中出度大于入度的顶点成为 K 顶点，如图，a 和 b 都是 k 顶点，

设计算法 int printVertices(MGraph G)对给定任意非空有向图 G，输出 G 中所有 K 顶点的算法，并返回 K 顶点的个数。

(1)给出算法的设计思想。

(2)根据算法思想，写出 C/C++描述，并注释。

思想：邻接矩阵表示的有向图，一行中1的格式是该行对应顶点的出度个数，一列中1的个数是该列对应的顶点的入度个数。开始时，count=0，来统计k结点的个数，对图中的每个结点，根据邻接矩阵来计算出度和入度的个数，若出度大于入度，则为k结点。

代码：

int printVertices(MGraph G){
int intdegree,outdegree,k,m,count=0;
for(k=0;k<G.numVertices;k++){
intdegree=0,outdegree=0;
for(m=0;m<G.numVertices;m++){//出度 
outdegree += G.Edge[k][m];
} 
for(m=0;m<G.numVertices;m++){//入度 
intdegree += G.Edge[m][k];
} 
if(outdegree>intdegree){//输出k顶点 
printf("%d",G.VerticesList[k]);
count++;//k顶点个数加1 
} 
}
return count;
}

原文地址：https://blog.csdn.net/m0_56332819/article/details/142858895

免责声明：本站文章内容转载自网络资源，如本站内容侵犯了原著者的合法权益，可联系本站删除。更多内容请关注自学内容网（zxcms.com）！