daniel 匆匆过客

IT博客 首页 新随笔 联系 聚合 管理
  3 Posts :: 0 Stories :: 7 Comments :: 0 Trackbacks

解答:(参考introduction to algrithms)
1,从任意节点s出发用深度优先遍历(或宽度优先遍历)遍历该图,若生成多棵树,则不是连通的。
2,反向图中所有的边。
3,   从节点s出发用深度优先遍历(或宽度优先遍历)遍历该图,若生成多棵树,则不是连通的,否则是强连通图。
理由:1保证了从s可以到达所有的节点。2,3说明从任意节点都可以到达s。任意节点i,j都是连通的因为
i~s,s~j。

posted on 2006-08-03 14:05 danielcheng 阅读(1547) 评论(0)  编辑 收藏 引用 所属分类: 练练手
只有注册用户登录后才能发表评论。