当前位置: 首页 > article >正文

给定任意非空有向图 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;
}


http://www.kler.cn/a/353828.html

相关文章:

  • PHP进阶-在Ubuntu上搭建LAMP环境教程
  • 道品科技智慧农业与云平台:未来农业的变革之路
  • nodejs的降级
  • Android 系统签名 keytool-importkeypair
  • Flask返回浏览器无乱码方法
  • Chrome访问https页面显示ERR_CERT_INVALID,且无法跳过继续访问
  • 通过API进行Milvus实例配置
  • Android摄像头Camera2和Camera1的一些总结
  • 百万字文本内容搜索Java实现方案
  • springboot项目多个数据源配置 dblink
  • 牛客编程初学者入门训练——BC19 牛牛的对齐
  • git clone --single-branch 提升效率
  • electron-vite_8修改版本号和出品公司名称
  • 【Golang】Go语言中的反射原理解析与应用实战
  • ssm资产管理信息系统+vue
  • 组合式API有什么好处
  • 【React】父组件如何调用子组件的方法
  • netron安装(windows linux)
  • 通过阿里云Milvus和通义千问快速构建基于专属知识库的问答系统
  • ProteinMPNN中蛋白质特征提取
  • python的多线程和多进程
  • 【vue+printJs】前端打印, 自定义字体大小, 自定义样式, 封装共享样式
  • 【Flutter】Dart:函数
  • esp32 开发需要那些开发语言
  • paypal php 实现详细攻略
  • 4 登录接口实现(Vue3+Spring boot+mysql)