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

9.4.2. Является ли граф связным?

9.4.2. Является ли граф связным?

Не все графы связные. Иногда нет способа «добраться из одной точки в другую», то есть между двумя вершинами нет никакого пути, составленного из ребер. Связность — это важное свойство графа, его надо уметь вычислять. В связном графе любая вершина достижима из любой другой.

Не будем объяснять принцип работы алгоритма, интересующийся читатель может найти описание в любой книге по дискретной математике. Но в листинге 9.4 приведена его реализация на Ruby.

class Graph
 def connected?
  x = vmax
  k = [x]
  l = [x]
  for i in 0..@max
   l << i if self[x,i]==l
  end
  while !k.empty?
   y = k.shift
   # Теперь ищем все ребра (y,z).
   self.each_edge do |a,b|
    if a==y || b==y
     z = a==y ? b : a
     if !l.include? z
      l << z
      k << z
     end
    end
   end
  end
  if l.size < @max
   false
  else
   true
  end
 end
end
mygraph = Graph.new([0,1], [1,2], [2,3], [3,0], [1,3])
puts mygraph.connected?  # true
puts mygraph.euler_path? # true
mygraph.remove 1,2
mygraph.remove 0,3
mygraph.remove 1,3
puts mygraph.connected?  # false
puts mygraph.euler_path? # false

В примере упомянут метод euler_path?, с которым мы еще не встречались. Он определен в разделе 9.4.4.

Можно было бы усовершенствовать этот алгоритм, так чтобы он находил все связные компоненты несвязного графа. Но мы не станем этого делать.

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