Нахождение заданных ребер в графе - PullRequest
Новая
       37

Нахождение заданных ребер в графе

0 голосов
/ 26 апреля 2018

У меня есть неориентированный граф, который имеет некоторое количество узлов и ребер.

Каждый из узлов имеет определенный цвет, а каждый из ребер имеет определенный тип, определяемый цветом узлов, к которым он подключается:

  • Ребро, соединяющее красный и синий узел, имеет тип красно-синий.
  • Поскольку график не является ненаправленным: red-blue == blue-red.

Мне поручено написать алгоритм, который найдет все ребра, которые «изолированы».

Кромка изолируется, если расстояние между исходным ребром и следующим ребром того же типа, что и исходное, составляет не менее 2 ребер.

Каков наилучший способ сделать это? Скорее всего, это можно решить с помощью поиска в ширину / глубину, но я не могу найти способ связать их с этой конкретной проблемой

1 Ответ

0 голосов
/ 26 апреля 2018

Я почти уверен, что это сработает, но не уверен насчет сложности 

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
...