算法-连通性问题

连通性问题

问题描述

给定一个由类似p-q的整数对组成的序列，其中每个整数表示一个对象，p-q表示对象p连接到对象q，p和q之间是连通的。

假设对象之间的连通关系具有传递性：假设对象p和对象q之间是连通的，对象q和对象r之间是连通的，则对象p和对象r之间就是连通的。

要求：编写一个过滤序列中无关对的程序。

• 程序的输入是对象对p-q，
• 如果通过已经看到的数对之间的连通关系不能判断出对象p和对象q之间是连通的，则输出该对象对；
• 通过已经看到的数对之间的连通关系可以推断出对象p和对象q之间是连通的，则忽略该对象对，并提示继续输入下一个对象对；
• 输出两个对象之间的所有连接方式；
• M个连接能保证N个对象之间是连通的吗？

分析：
分析程序需要具备的功能：

程序需要具备的功能：

• 程序要记录其所看到的对象对；
• 程序要能判定一个新的对象对是否连通；

目标：将连通问题的求解过程变成如何定义表示抽象集合的数据结构，及开发高效利用这个数据结构的查找和合并算法。

分析程序执行的基本操作：

每当出现一个新的对象对时，
首先，需要判定该对象对是否表示一个新的连接；
然后，将该新的连接合并到已得到的对象的连通关系中，使其能够对新输入的对象对进行检查；

思路：
将这两个步骤封装成抽象操作，

1. 查找操作
2. 合并操作