Книга: Программирование на языке Ruby

9.4.4. Есть ли в графе эйлеров путь?

9.4.4. Есть ли в графе эйлеров путь?

Эйлеров путь и эйлеров цикл — разные вещи. Слово «цикл» подразумевает, что нужно вернуться в исходную точку. А наличие пути предполагает, что нужно лишь посетить каждую вершину ровно один раз. В следующем фрагменте демонстрируется это различие:

class Graph
 def euler_path?
  return false if !connected?
  odd=0
  each_vertex do |x|
   if degree(x) % 2 == 1
    odd += 1
   end
  end
  odd <= 2
 end
end
mygraph = Graph.new([0,1],[1,2],[1,3],[2,3],[3,0])
flag1 = mygraph.euler_circuit? # false
flag2 = mygraph.euler_path?    # true

Оглавление книги

Похожие страницы

Генерация: 0.566. Запросов К БД/Cache: 3 / 0
поделиться
Вверх Вниз