首页| JavaScript| HTML/CSS| Matlab| PHP| Python| Java| C/C++/VC++| C#| ASP| 其他|
购买积分 购买会员 激活码充值

您现在的位置是:虫虫源码 > 其他 > Ex8-4 汇点问题 &laquo 问题描述: 采用邻接矩阵表示一个具有n 个顶点的图时

Ex8-4 汇点问题 &laquo 问题描述: 采用邻接矩阵表示一个具有n 个顶点的图时

  • 资源大小:52 K
  • 上传时间:2021-12-20
  • 下载次数:0次
  • 浏览次数:1次
  • 资源积分:1积分
  • 标      签: laquo Ex 矩阵表示

资 源 简 介

Ex8-4 汇点问题 « 问题描述: 采用邻接矩阵表示一个具有n 个顶点的图时,大多数关于图的算法时间复杂性为 O(n2 ),但也有例外。例如,即使采用邻接矩阵表示一个有向图G,确定G 是否含有一个 汇(即入度为n-1,出度为0 的顶点),只需要O(n)计算时间。试写出其算法。 « 编程任务: 对于给定的有n个顶点的图G 的邻接矩阵,各顶点依次编号为1,2,…,n。试设计一 个O(n)时间算法,计算图G 的汇点。 « 数据输入: 由文件input.txt提供输入数据。文件的第1 行有1 个正整数n,表示图G 中顶点个数。 第2 行起每行n个数,共n行,给出图G 的邻接矩阵。 « 结果输出: 程序运行结束时,将计算出的汇点编号输出到output.txt中。当图G 没有汇点时输出0。 输入文件示例 输出文件示例 input.txt 5 0 0 1 1 1 1 0 1 1 1 0 0 0 0 0 1 0 1 1 1 0 1 1 0 0 output.txt 3

相 关 资 源

您 可 能 感 兴 趣 的

同 类 别 推 荐

VIP VIP