连通区域标记－行程扫描算法 -- 等价对的处理过程
浏览数：15 /
时间：2015年06月08日
将等价对转换为若干个等价序列,比如有如下等价对: <1,2> <1,6> <3,7> <9,3> <8,1> <8,10> <11,5> <11,8> <11,12> <11,13> <11,14> <15,11>
经过等价对处理之后,应得到的等价序列为:
list1:1-2-5-6-8-10-11-12-13-14-15
list2:3-7-9
list3:4
主要思路:将1-15个点都看成图的节点,而等价对<1,2>说明节点1和2之间有通路,而且形成的图是无向图.我们需要遍历图,找到其中的所有连通图,主要采用的是图的深度优先遍历法,进行等价序列的查找.
如上图所示,从节点1开始查找,它有三个路径1-2,1-6,1-8;2和6后面没有路径,8后面有两个路径8-10,8-11;10后面没有路径,11后面有5条路径分别为11-5,11-12,11-13,11-14,11-15,到此,等价表1查找完毕.
等价表2是从3开始查找,它的后面有两条路径3-7,3-9.
等价表3只有一个孤立的点.
郑重声明：本站内容如果来自互联网及其他传播媒体，其版权均属原媒体及文章作者所有。转载目的在于传递更多信息及用于网络分享，并不代表本站赞同其观点和对其真实性负责，也不构成任何其他建议。
