如果任何节点最多有 2 条边，是否可以更快地确定是否形成循环？
首先，没有作业。
问题是这样的：
An undirected unweighted graph has N nodes.
Any node can have at most 2 edges to different nodes.
I need to know whether at least a cycle is formed.
输入：
M pairs of integers, as edges.
There can be duplicates, like "2 3" and "3 2".
The data may be invalid, for example: "1 2" "1 3" "1 4". The program needs to detect this.
我的方法（太慢）：
0.1) A set for edges to detect duplicates. (C++ e.g.: std::set<int>)
0.2) A map for nodes to count how many edges from each node. (std::map<int,int>)
0.3) A list for links. A link is a set of connected nodes. (std::list<std::set<int> >)
1) Read in an edge, and change the edge to ascending order, e.g.: "3 2" -> "2 3".
2.1) If the edge has already be "drawn", skip and go to 1);
2.2) If either vertex has already got 2 edges, invalid!
2.3) Otherwise, check whether either of the nodes has already been in a link.
3.1) If neither, create a new link and add to the list.
3.2) If only one, add the single one to the link.
3.3) If both,
3.3.1) If in the same link, a cycle has been formed!
3.3.2) If not, merge two links.
请推荐一个更快的算法，以及该算法的数据结构。谢谢。
First of all, no homework.
Here is the problem:
An undirected unweighted graph has N nodes.
Any node can have at most 2 edges to different nodes.
I need to know whether at least a cycle is formed.
Input:
M pairs of integers, as edges.
There can be duplicates, like "2 3" and "3 2".
The data may be invalid, for example: "1 2" "1 3" "1 4". The program needs to detect this.
My approach (too slow):
0.1) A set for edges to detect duplicates. (C++ e.g.: std::set<int>)
0.2) A map for nodes to count how many edges from each node. (std::map<int,int>)
0.3) A list for links. A link is a set of connected nodes. (std::list<std::set<int> >)
1) Read in an edge, and change the edge to ascending order, e.g.: "3 2" -> "2 3".
2.1) If the edge has already be "drawn", skip and go to 1);
2.2) If either vertex has already got 2 edges, invalid!
2.3) Otherwise, check whether either of the nodes has already been in a link.
3.1) If neither, create a new link and add to the list.
3.2) If only one, add the single one to the link.
3.3) If both,
3.3.1) If in the same link, a cycle has been formed!
3.3.2) If not, merge two links.
Please recommend a faster algorithm, and the data structures for the algorithm. Thank you.
如果你对这篇内容有疑问，欢迎到本站社区发帖提问 参与讨论，获取更多帮助，或者扫码二维码加入 Web 技术交流群。
绑定邮箱获取回复消息
由于您还没有绑定你的真实邮箱，如果其他用户或者作者回复了您的评论，将不能在第一时间通知您！
发布评论
评论（3）
无向图的标准算法是简单地对其运行深度优先搜索，保持跟踪当前路径上的节点。如果你遇到一个被访问过的节点，那么你就有了一个循环。
The standard algorithm for an undirected graph is to simply run a depth first search on it, keeping track of the nodes on the current path. If you run into a visited node, then you have a cycle.
由于每个节点最多有 2 个关联边，因此删除具有 0 个边的所有节点，然后重复删除仅具有单个关联边（以及相应边）的任何节点。如果有一个循环，您将到达一个阶段，其中没有可以删除的节点，但仍然会留下节点。如果没有循环，那么您将在删除所有节点后终止。
编辑：处理可能无效的输入并更明确地了解底层数据结构。
当读取数据时，会建立一个由节点 ID 索引的数据结构，并且对于每个索引条目，包含与该节点相关的节点列表。 [即，当读入每条边时，需要创建两个条目，每个条目对应一个条目。]当数据进入时，删除重复项并发现是否有任何节点与太多边相关联。这是线性的。
保留具有单个入射边的节点列表。在算法的每个步骤中，您从此列表中选择任何节点，并在删除边缘后将其链接到的节点放入此列表中（如果需要）。 [如果节点已经在列表中，您可以将其删除或修改上一步以忽略从列表中获取的任何没有更多关联边的边。]
一条边最多添加到列表中一次，并且每个迭代从该列表中删除一条边。因此是线性的。
Since each node has at most 2 incident edges, remove any nodes with 0 edges and then repeatedly remove any node that has only a single incident edge (and the corresponding edge). If you have a cycle you will reach a stage where there are no nodes that you can remove, but there will still be nodes left. If there is no cycle then you will terminate having removed all the nodes.
Edit: To deal with possibly invalid input and to be more explicit about the underlying data-structure.
As the data is read in build up a data-structure that is indexed by node ID and, for each indexed entry, contains a list of the nodes incident to that node. [I.e. as each edge is read in there are two entries to be made, one for each of the nodes.] As the data comes in remove duplicates and spot if any node is incident to too many edges. This is linear.
Keep a list of nodes with a single incident edge. At each step in the algorithm you pick any node from this list and, having removed the edge put the node to which it is linked in this list (if necessary). [If a node was already in the list you can either remove it or modify the previous step to just ignore any edges, taken from the list, that have no more incident edges.]
An edge is added at most once to the list and each iteration removes an edge from that list. Hence linear.
您可以选择 Prim 或 Kruskal 的算法来创建最短生成树。基本上，他们都试图在不创建电路的情况下将权重最小的边添加到新树中。您只需稍微修改算法，以便在创建电路时，只需破坏程序即可。
如果我没记错的话（e：边缘），它们都以 O(e log e) 的形式运行，但它可能会快得多，因为你可以很早就中断。
You can pick Prim's or Kruskal's algorithms for creating shortest spanning trees. Basically they both attempt to add edges of least weight to a new tree while not creating a circuit. You just have to modify the algorithm a tad so that in the event of a circuit creation, then you just break the procedure.
They both run as O(e log e) if I remember right (e: edges), but it'll likely be much faster as you can break of very early.