首页 > 试题广场 >

考虑下面的问题, 我们有一个计算机网络和一个双向连接表,每一

[问答题]
考虑下面的问题, 我们有一个计算机网络和一个双向连接表,每一个连接可将文件从一台计算机传送到另一台计算机,要将一个文件从网络上任意一台计算机发送到任意的另一台计算机中去,附加限制是该问题必须联机解决。考虑一种算法,在开始时把每一台计算机放入它自己的集合中。要求两台计算机可以传输文件当且仅当它们再同一个集合中。我们一次一个地读入链接,当我们读入某个链接 比如(u,v),测试是否u和v在同一个集合中,如果它们再同一个集合中则什么也不做,如果它们在不同的集合中那么将它们所在的两个集合合并。在算法的最后,所得到的图连通当且仅当恰好存在一个集合。
指出上面程序对下图的操作:(1,2),(3,4),(3,6),(5,7),(4,6),(2,4),(8,9),(5,8)。连通分支都是什么?

这道题你会答吗?花几分钟告诉大家答案吧!