在 Graph 中，存在一个三角带问题。基本上，我们有一组相邻的三角形，我们希望将每个三角形视为一个新顶点，如果两个新顶点后面的两个三角形有一条共同的边，那么它们之间就会有一条边。
我的问题是关于读取每个三角形并为它们构建新的条形图。
例如，我们有这些三角形（A、B 和 C）：
A - 0, 1, 3
B - 1、2、3
C - 2、3、4
所以 A 和 B 有一个共同的边缘，B 和 C 也是如此。新的条带从 A 到 B，然后到 C。
好的。我认为这里的关键之一是，每次阅读一个新三角形时，我们都想知道哪些三角形与新三角形有共同边。
一个愚蠢的方法是我们只扫描所有旧三角形并将它们的三个顶点与新的顶点进行比较，如果两个顶点匹配，则存在邻接。
一种更好的方法（在 The Algorithm Design Manual中描述）是每次我们为每个三角形顶点创建一个列表时。该列表包含通过顶点的所有三角形。比如上面的三角形，顶点0有{A}的列表，顶点1有{A,B}的列表等等。所以当一个新的三角形来的时候，我们只需要检查3个顶点并尝试找到哪些旧三角形与新三角形有两个共同顶点。
这里有一些问题：
更好的方式是线性的吗？如何定义这种阅读和构建图的“线性”？例如，以更好的方式，一个新三角形需要遍历 3 个旧三角形列表。这足够线性吗？我认为它是线性的，因为它最多只能读取所有旧三角形。但是如果我的想法是真的，那么愚蠢的方式也是线性的，对吧？所以我想我可能错了，但很困惑。
会有更好的方法吗？算法设计手册要求这是一种消费税，即使在最坏的情况下，消费税也要求纯线性算法。
我对更好方法的解决方案是，我不是为每个顶点构建一个列表，而是为每个边构建一个列表。一个顶点可以有许多三角形通过，但是如果有一条边，则最多有两个三角形通过，假设所有三角形的边不相互交叉并且最多合并（共同）。
然后每条边都有一个最多包含两个项目的列表。而对于一个新出现的三角形，它最多需要检查 3 个边。我认为这比上面更好的方法更好。
我对吗？还是我更好的方法是纯粹的最佳线性解决方案？