首页 > 试题广场 >

判定任意两个顶点Vi和Vj之间是否有长度为m的路径相连

[单选题]
用相邻矩阵 A 表示图，A[i][j] = 1 表示 Vi 和 Vj 之间有边相连，A[i][j] = 0 表示无边相连。要判定任意两个顶点 Vi 和 Vj 之间是否有长度为 m 的路径相连，则只要检查（ ）的第 i 行第 j 列的元素是否为零即可。 
  • A
  • A^m
  • Am-1
  • mA
查看答案及解析
添加回答
推荐
啥头像 啥
顺着clocean的思路接着写
”长度为m的路径“应该是从 Vi起经过m-1个点到达Vj

编辑于 2016-03-06 12:47:02 回复(3)
第六次破晓头像 第六次破晓
此题中长度为m的路径不是指权为m，表示两个结点间是否有m条边连接。要注意理解题意，理解清题意后易得A的m次幂
发表于 2017-01-06 01:08:17 回复(0)
ZhangFinder头像 ZhangFinder
m不是权吗？
发表于 2016-09-08 12:38:21 回复(1)
huixieqingchun头像 huixieqingchun
长度为m的路径，表示两个结点间是否有m条边连接。要注意理解题意。
发表于 2016-05-08 14:24:22 回复(0)
clocean头像 clocean
开始可能理解错了，”长度为m的路径“应该是从Vi起经过m个点到达Vj。那么问题就明确了，相邻矩阵就是表示两个点之间是否有边。相邻矩阵相乘就是表示经过2次可达的点集合。m次可达就 A^m 次了。写的有点简单，还请有耐心大神细致分析。
发表于 2015-09-06 11:22:42 回复(3)
小西行飞头像 小西行飞
我还以为m是权
发表于 2016-10-13 15:43:30 回复(0)
Simon..头像 Simon..
<p>王道书217页</p><p><br></p><p>设图G的邻接矩阵为A，A^n的元素A^n[i][j]等于顶点i到顶点j的长度为n的路径数目。</p>
发表于 2020-11-26 20:00:05 回复(0)
牛客679724957号头像 牛客679724957号
相邻矩阵中的元素为1代表有路径，为0代表没用路径，一直路径的长度为m，所以矩阵为m个A矩阵相乘以
发表于 2021-09-12 10:05:04 回复(0)
谱乐头像 谱乐
这道题什么意思啊 A怎么又能当数来用了呢

发表于 2018-05-23 21:12:43 回复(1)
雨山四村村民头像 雨山四村村民
这题是离散数学的知识，A矩阵的m次幂就包含了两点之间长度为m的路径信息，是几就代表有几条路径
发表于 2025-02-17 15:42:08 回复(0)
牛客641747号头像 牛客641747号
这题的题面本来就有问题吧。直观理解会是需要权值。但是又没写权值是多少。
没权值怎么算长度呢？这个权值应该也没有默认值的。题目中只写了节点i和j相连时邻接矩阵用1标出。
发表于 2024-11-06 11:09:21 回复(0)
辉小歌头像 辉小歌
题目描述不清 题目应该问的是i和j有边的话，边的权值是不是m A［i］［j］异或m如果为0 则说明边的权值为m.（补充，这题目描述不清拉黑即可dog）。
发表于 2022-08-21 14:47:33 回复(0)
小白1001头像 小白1001
离散老师教过，真心觉得可以先学离散与线代后再弄数据结构。
发表于 2022-05-05 20:52:21 回复(0)
ddssddgg头像 ddssddgg
题目意思没弄懂服了。。
发表于 2022-04-25 21:07:46 回复(0)
JiaRu666头像 JiaRu666
补充一个应用：社交网络中的n度人脉，例如QQ推荐可能认识的人，一方面是度数尽量低，另一方面是路径尽量多
发表于 2019-05-13 20:16:08 回复(0)
BernardLowe头像 BernardLowe
我也以为是权呢！
发表于 2016-11-24 21:05:32 回复(0)
陋室头像 陋室
数据结构图里的Floyd算法，可以算出每个点之间的最短路径，时间复杂度是O（n^3），相对应的Dijkstra算法时间复杂度O(n^2)，建议大家都去学一下。
编辑于 2015-09-07 10:18:35 回复(1)
提交观点

问题信息

图
来自：C++入门级笔试题合集（一）
难度：
17条回答 14624浏览

热门推荐

相关试题

扫一扫，把题目装进口袋

求职之前，先上牛客

扫描二维码，进入QQ群

扫描二维码，关注牛客公众号