algorithm - 在图中查找特定边

Question

我有一个无向图，它有一些节点和边。

每个节点都有特定的颜色，每条边都有特定的类型，由它连接的节点的颜色决定:

• 连接红色和蓝色节点的边是红-蓝类型。
• 由于图是无向的:red-blue == blue-red。

我的任务是编写算法来找到所有“孤立”的边。

当原始边与与原始边类型相同的下一条边之间至少有 2 个边的距离时，一条边是孤立的。

执行此操作的最佳方法是什么？它很可能可以使用广度/深度优先搜索来解决，但我无法找到将它们与这个特定问题联系起来的方法

Answer 1

我很确定这会奏效，不确定复杂性

For each node n:
    For each edge (n, n2) e:
        n.colors[edgeColor(e)] += 1
For each node n:
    n.colors2 = n.colors.copy()
    For each edge (n, n2) e:
        n.colors2 = mergeSum(n.colors2, n2.colors)
For each edge (n, n2) e:
   if n.colors2[edgeColor(e)] == 2 and n2.colors2[edgeColor(e)] == 2:
       isolated edge