连通问题-快速查找法

快速查找法

思想 ：节点列表中每个节点初始存放内容为本节点，运算时针对每对连通的节点node1和node2，遍历节点列表，取出节点中的内容，判断当前节点的内容是否和node1节点中的内容相等，如果相等，将当前节点中的内容置换成node2节点中的内容（因为node1和node2是连通的，而node中的内容是和node连通的，即node1中的内容和node1连通，node2中的内容和node2连通，那么node1的内容就和node2的内容是连通的）。如此上述步骤，遍历完所有连通节点对，这样所有连通的节点也就连接到相同的节点（这里称该节点为根节点）。

注解：node中存放的内容实际上是和node连通的另一个节点（初始是节点自己）

伪代码：

//节点连通信息

int[][] connnectNodes = {{1,2},{2,4},{0,8},{6,7},{7,3},{3,5},{9,1},{5,9}};

//节点中的内容----这里假设节点个数为10的情况

int[] nodesContext = {0,1,2,3,4,5,6,7,8,9};

for (  i = 0; i < connnectNodes.length; i++ )

{

       node1 = connnectNodes[i][0];

       node2 = connnectNodes[i][1];

     //如果两节点相同，可以减少后续不必要的遍历

      if( node1 == node2 )

    continue;

      tempContext = nodesContext[node1];//临时记录node1中的内容（在下列遍历中，node1的内容会满足修改条件而发生变化）

      for(  j = 0; j < nodesContext.length; j++ )

     {

    //判断当前节点的内容是否和node1节点中的内容相等，如果相等，将当前节点中的内容置换成node2节点中的内容

            if( nodesContext[j] == tempContext )

                nodesContext[j] = nodesContext[node2];

      }

}

代码执行过程数据变化情况：

connectNodes[0]    nodesContext(BEFORE)        nodesContext(AFTER)    tempContext    nodesContext[node2]

1,2                              0,1,2,3,4,5,6,7,8,9            0,2 ,2,3,4,5,6,7,8,9               1                        2

2,4                              0,2,2,3,4,5,6,7,8,9            0,4,4 ,3,4,5,6,7,8,9               2                        4

0,8                              0,4,4,3,4,5,6,7,8,9            8 ,4,4,3,4,5,6,7,8,9               0                        8

6,7                              8,4,4,3,4,5,6,7,8,9            8,4,4,3,4,5,7, 7,8,9               6                        7

7,3                              8,4,4,3,4,5,7,7,8,9            8,4,4,3,4,5,3,3 ,8,9               7                        3

3,5                              8,4,4,3,4,5,3,3,8,9            8,4,4,5 ,4,5,5,5 ,8,9               3                        5

9,1                              8,4,4,5,4,5,5,5,8,9            8,4,4,5,4,5,5,5,8,4               9                        4

5,9                              8,4,4,5,4,5,5,5,8,4            8,4,4,4 ,4,4,4,4 ,8,4               5                        4

算法的理解：

    节点数为N，连通对数为M时，算法需要执行的次数为M*N。可以看出，在每个连通对处理时，都遍历了一次节点列表，这中间有很多节点是不需要任何改变的（当节点数量越多时，这样无意义的动作就会越多）。