在图中查找特定边-Java 学习之路

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

每个节点都具有一定的颜色，每个边缘都是某种类型，由它连接到的节点的颜色决定：

连接红色和蓝色节点的边缘为红蓝色 .
由于图表是无向的： red-blue == blue-red .

我的任务是编写能够找到所有“孤立”边缘的算法 .

当原始边缘和与原始边缘相同类型的下一个边缘之间至少有2个边缘距离时，边缘被隔离 .

最好的方法是什么？最有可能的是它可以使用广度/深度优先搜索来解决，但我无法找到将它们连接到这个特定问题的方法

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

回复于 2024-04-20T20:46:34+08:00

在图中查找特定边

1 回答

相关问题