如何解决图连通性问题？

Question

最近，我在一次采访中遇到以下问题，但我无法回答，有人可以帮我找到解决问题的算法吗？我应采用哪种图形概念来解决它？

给出路由器的数量以及路由器之间的链接。编写一个算法以识别所有需要一直连接到网络的路由器

Input：6,5（其中6是路由器数，5是链接数）[（（1,2），（2,3），（3,4），（4,5），（6,3）]

输出：预期的返回值2 3 4

Answer 1

您的图形是图G {“ 1”-“ 2”“ 2”-“ 3”“ 3”-“ 4”“ 4”-“ 5”“ 6”-“ 3”}在GraphViz中产生

所以{2，3，4}是具有多个不同边缘的节点。

如果保证输入没有重复的边，那么任何在输入中出现多次的节点都是必需的。

如果不能保证输入的边没有重复，则必须为每个节点计算不同的边，并选择不只有一个离散边的节点。