首页 > 试题广场 >

要连通具有 n 个顶点的有向图，最少需要（）条边。

[单选题]
要连通具有 n 个顶点的有向图，最少需要（）条边。 
  • n+l
  • n-l
  • 2n
  • n
查看正确选项
添加回答
arrnos头像 arrnos
答案应该是 D
发表于 2017-02-28 14:04:46 回复(2)
卸不下的喜欢头像 卸不下的喜欢
连通有向图的最短边数情况为收尾相连成环的情况，边数为n;
连通无向图的最短边数情况为所有节点连成一条链的情况，边数为n-1;
发表于 2017-08-31 00:57:06 回复(0)
侯卿头像 侯卿
注意，有向图的话，连通＝所有节点成环，不然怎么走的通。
发表于 2018-04-09 07:57:50 回复(0)
美团到店招聘头像 美团到店招聘
答案是不是错了？
连通n个结点的有向图，至少需要n条边。
连通n个结点的无向图，至少需要n-1条边。
发表于 2017-02-18 08:52:22 回复(1)
黏黏糖头像 黏黏糖
无向图，A与B连通只需要1条边即可，n个顶点连通需要n-1条边；
有向图中，A与B连通需要A->B，B与A连通也要B->A，则n个顶点连通需要n条边。
发表于 2017-05-09 10:40:26 回复(2)
anqierman头像 anqierman
1.有向图，连通=所有结点连成一个环，需要n条边
2.无向图，连通=所有结点连成一条链，需要n-1条边
发表于 2019-08-31 16:44:39 回复(0)
我是超越迷妹了😘头像 我是超越迷妹了😘
哎，是有向图！！！思维定式了
发表于 2017-09-12 10:52:07 回复(0)
正营头像 正营
A
发表于 2016-12-25 01:25:34 回复(0)
提交观点

问题信息

图
上传者：牛100
难度：
8条回答 12278浏览

热门推荐

相关试题

扫一扫，把题目装进口袋

求职之前，先上牛客

扫描二维码，进入QQ群

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