连通性问题
问题描述
给定一个由类似p-q的整数对组成的序列，其中每个整数表示一个对象，p-q表示对象p连接到对象q，p和q之间是连通的。
假设对象之间的连通关系具有传递性：假设对象p和对象q之间是连通的，对象q和对象r之间是连通的，则对象p和对象r之间就是连通的。
要求：编写一个过滤序列中无关对的程序。
- 程序的输入是对象对
p-q， - 如果通过已经看到的数对之间的连通关系不能判断出对象p和对象q之间是连通的，则输出该对象对；
- 通过已经看到的数对之间的连通关系可以推断出对象p和对象q之间是连通的，则忽略该对象对，并提示继续输入下一个对象对；
- 输出两个对象之间的所有连接方式；
- M个连接能保证N个对象之间是连通的吗？
分析：
分析程序需要具备的功能：
程序需要具备的功能：
- 程序要记录其所看到的对象对；
- 程序要能判定一个新的对象对是否连通；
目标：将连通问题的求解过程变成如何定义表示抽象集合的数据结构，及开发高效利用这个数据结构的查找和合并算法。
分析程序执行的基本操作：
每当出现一个新的对象对时，
首先，需要判定该对象对是否表示一个新的连接；
然后，将该新的连接合并到已得到的对象的连通关系中，使其能够对新输入的对象对进行检查；
思路：
将这两个步骤封装成抽象操作，
- 查找操作
- 合并操作
网友评论