qq_37109173
qq_37109173
2017-11-25 11:55

关于有向图的连通问题

  • 算法
  • 有向图
  • 连通
  • 数据结构

有n个顶点的有向图,至少需要多少条弧才能保证是连通的。我看了有个学长写的答案是n,我觉得n不可能正确。我的想法是要保证连通,得是n-1个点构成一个有向图的强连通图,那么弧数就是(n-1)*(n-2) 再将剩下的那个节点与这个强连通图相连,那么问题来了,这个时候是该加一条有向弧,还是该加两条有向弧呢?

  • 点赞
  • 回答
  • 收藏
  • 复制链接分享

2条回答