百分求助：一道数据结构+算法的题。求围观求解决

有n个结点，序号分别为0，1，……，n-1。一组数（p，q）表示结点p和q之间的连通操作，连同具有自反，对称和传递性。输入多个连通操作，依次对每个操作判断，如果两个结点已经连通，则会输出0；否则，连通两个结点，并输出1。
例如，有10个结点，输入(4,3),(3,8),(6,5),(9,4),(2,1),(8,9),(5,0),(7,2),(6,1),(1,0),(6,7),(2,5),(4,9)以上的输入会输出1111111111100。
编写函数string connect(points)实现上述功能，参数points表示一组连通操作，数据结构自己定义，返回值string是输出结果。

7 个解决方案

#1

增加人气，自己先顶上！
这是一道面试题，当时就这道题没做出来！

#2

图的算法，为了简单，直接使用邻接矩阵，然后深度优先搜索，判断结点是否连通

#3

天意是否可以定义一个二维数组A[p][q] 遍历  A[p][q]的值表示连通操作的值 

#4

引用 3 楼 Jax_zhong 的回复:

天意是否可以定义一个二维数组A[p][q] 遍历  A[p][q]的值表示连通操作的值

找本数据结构的书，直接看图那一张，理解前面几个部分就可以做这个题了，我虽然懂，但是讲起来，不是一时半会就能明白的，有了方向，也需要自己努力

#5

引用 4 楼 Inhibitory 的回复:

引用 3 楼 Jax_zhong 的回复:
天意是否可以定义一个二维数组A[p][q] 遍历  A[p][q]的值表示连通操作的值
找本数据结构的书，直接看图那一张，理解前面几个部分就可以做这个题了，我虽然懂，但是讲起来，不是一时半会就能明白的，有了方向，也需要自己努力

是的。多谢！

#6

如1楼所说，这个是图，而且是 无向图，相对来讲比较简单。

首先内存中构造图模型，遗憾的是Java并没有自带图的结构，所以要自己简单设计下：一般来说用二维数组是最简单的了，但是不合适规模比较大的。

图模型建立完毕后剩下的事情非常简单，要么用：深度优先搜索，要么用广度优先搜索。

如果不记得怎么回事，就想想树的遍历算法，把源节点当作树根，然后做深度优先或广度优先遍历来搜索目标节点；注意图是可以无限循环的，所以终止条件要设计好。

#7

感谢楼上2位大牛Q
谢谢楼下继续补充@