我遇到了一个关于图表的问题。 让我们定义一个耙图。
A n-vertex graph is a rake when it meets certain conditions:
- there is a vertex of degree 1 in the graph
- this vertex is connected to a vertex of degree 2
- this second vertex is connected to another vertex of degree n-2 other vertices may or may not be connected to each other.
我得到了一个包含 n 个顶点的图的邻接矩阵。我的任务是检查给定矩阵表示的图形是否为“rake”。问题是必须在线性时间内完成。
我什么都试过了。当你有邻接表时这很容易做到，但我如何使用给定的矩阵让它花费 O(n) 时间？
最佳答案
好吧，我似乎找到了答案!确实有一个线性时间算法可以解决这个问题，因为我提出的这个问题在科学界被称为检查一个图是否是蝎子图!
在这里您可以找到我一直在寻找的算法。 http://www.cs.cornell.edu/courses/cs681/2007fa/Handouts/scorpion.pdf
感谢您的帮助!
关于algorithm - 仅在给定邻接矩阵的情况下在线性时间内检查图形属性，我们在Stack Overflow上找到一个类似的问题： https://stackoverflow.com/questions/20154189/