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

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

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

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

Листинг 9.4. Выяснение того, является ли граф связным

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.

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