qq_37109173 2017-11-25 11:55 采纳率: 100%
浏览 2591
已采纳

关于有向图的连通问题

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

  • 写回答

2条回答 默认 最新

  • qq_37109173 2017-11-25 14:43
    关注

    保证，重点是要保证连通，最坏情况下

    本回答被题主选为最佳回答 , 对您是否有帮助呢?
    评论
查看更多回答(1条)

报告相同问题？