class Tree
# Предполагается, что определения взяты из предыдущего примера...
def to_s
"[" +
if left then left.to_s + "," else "" end +
data.inspect +
if right then "," + right.to_s else "" end + "]"
end
def to_a
temp = []
temp += left.to_a if left
temp << data
temp += right.to_a if right
temp
end
end
items = %w[bongo grimace monoid jewel plover nexus synergy]
tree = Tree.new
items.each {|x| tree.insert x}
str = tree.to_a * ","
# str is now "bongo,grimace,jewel,monoid,nexus,plover,synergy"
arr = tree.to_a
# arr равно:
# ["bongo",["grimace",[["jewel"],"monoid",[["nexus"],"plover",
# ["synergy"]]]]]
Отметим, что глубина вложенности получающегося массива равна глубине дерева с корнем в том узле, с которого мы начали обход. Чтобы получить плоский массив, можете воспользоваться методом flatten.
Графом называется множество вершин, произвольным образом соединенных друг с другом. (Дерево — частный случай графа.) Не будем слишком углубляться в эту тему, поскольку теория и терминология весьма сложны. Очень скоро мы перешли бы от информатики в область чистой математики.
И все же у графов есть немало практических приложений. Возьмите обычную дорожную карту, на которой города соединены скоростными магистралями, или печатную плату. То и другое удобно представлять в виде графов. Компьютерную сеть тоже можно описать в терминах теории графов, будь то локальная сеть из нескольких десятков машин или весь Интернет, насчитывающий миллионы узлов.
Под графом мы обычно понимаем неориентированный граф. Попросту говоря, в нем не проставлены стрелки на соединительных линиях; две вершины либо соединены, либо нет. Между тем в ориентированном графе (орграфе) могут быть «улицы с односторонним движением»; из того, что вершина x соединена с вершиной у, не следует, что верно и обратное. Наконец, во взвешенном графе ребрам можно назначать веса. Например, вес может выражать «расстояние» между вершинами. Мы ограничимся только этими основными видами графов; интересующегося читателя отсылаем к многочисленным учебникам информатики и математики.
В Ruby, как и во многих других языках, граф можно представить разными способами, например в виде настоящей сети взаимосвязанных объектов или в виде матрицы, в которой хранятся ребра графа. Мы рассмотрим оба способа и на примерах покажем, как можно манипулировать графами.
9.4.1. Реализация графа в виде матрицы смежности
Нижеприведенный пример основан на двух предыдущих. В листинге 9.3 неориентированный граф реализован в виде матрицы смежности с помощью класса ZArray (см. раздел 8.1.26). Это нужно для того, чтобы новые элементы по умолчанию получали значение 0. Также мы унаследовали классу TriMatrix (см. раздел 8.1.7), чтобы получить нижнетреугольную матрицу.
Листинг 9.3. Матрица смежности
class LowerMatrix < TriMatrix
def initialize
@store = Zarray.new
end
end
class Graph
def initialize(*edges)
@store = LowerMatrix.new
@max = 0
for e in edges
e[0], e[1] = e[1], e[0] if e[1] > e[0]
@store[e[0],e[1]] = 1
@max = [@max, e[0], e[1]].max
end
end
def [](x,y)
if x > y
@store[x,y]
elsif x < y
@store[y,x]
else
0
end
end
def []=(x,y,v)
if x > y
@store[x,y]=v
elsif x < y
@store[y,x]=v
else
0
end
end
def edge? x,y
x,y = y,x if x < y
@store[x,y]==1
end
def add x,y
@store[x,y] = 1
end
def remove x,y
x,y = y,x if x < y
@store[x,y] = 0
if (degree @max) == 0
@max -= 1
end
end
def vmax
@max
end
def degree x
sum = 0
0.upto @max do |i|
sum += self[x,i]
end
sum
end
def each_vertex
( [email protected]).each {|v| yield v}
end
def each_edge
for v0 in [email protected]
for v1 in 0..v0-1
yield v0, v1 if self[v0,v1]==1
end
end
end
end
mygraph = Graph.new{[1,0],[0,3],[2,1],[3,1],[3,2])
# Напечатать степени всех вершин: 2 3 2 3.
mygraph.each_vertex {|v| puts mygraph.degree(v)}
# Напечатать список ребер.
mygraph.each_edge do |a,b|
puts "(#{a},#{b})"
end
# Удалить одно ребро.
mygraph.remove 1,3
# Напечатать степени всех вершин: 2 2 2 2.
mygraph.each_vertex {|v| p mygraph.degree v}
Отметим, что приведенная выше реализация не допускает ребер, ведущих из некоторого узла в него же. Кроме того, два узла могут быть соединены только одним ребром.
Мы позволяем задать начальный состав ребер, передавая пары в конструктор. Кроме того, можно добавлять и удалять ребра, а также проверять наличие ребра между двумя вершинами. Метод vmax возвращает вершину с наибольшим номером. Метод degree вычисляет степень указанной вершины, то есть количество исходящих из нее ребер.
Наконец, имеются два итератора each_vertex и each_edge, которые позволяют перебрать все вершины и все ребра соответственно.
9.4.2. Является ли граф связным?
Не все графы связные. Иногда нет способа «добраться из одной точки в другую», то есть между двумя вершинами нет никакого пути, составленного из ребер. Связность — это важное свойство графа, его надо уметь вычислять. В связном графе любая вершина достижима из любой другой.
Не будем объяснять принцип работы алгоритма, интересующийся читатель может найти описание в любой книге по дискретной математике. Но в листинге 9.4 приведена его реализация на Ruby.
Листинг 9.4. Выяснение того, является ли граф связным
class Graph
def connected?
x = vmax
k = [x]
l = [x]
for i in [email protected]
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.
Можно было бы усовершенствовать этот алгоритм, так чтобы он находил все связные компоненты несвязного графа. Но мы не станем этого делать.
9.4.3. Есть ли в графе эйлеров цикл?
Нет такой отрасли математики, сколь угодно абстрактной, которая со временем не нашла бы применения в реальной жизни.
Николай Лобачевский
Иногда нужно знать, есть ли в графе эйлеров цикл. Термин связан с математиком Леонардом Эйлером, который основал область топологии, занимающуюся этим вопросом. (Графы, обладающие таким свойством, называют иногда уникурсивными, поскольку их можно нарисовать не отрывая карандаша от бумаги и не проходя дважды по одному и тому же ребру.)
В немецком городе Кенигсберг был остров посередине реки. С двумя берегами остров связывало семь мостов. Горожане хотели знать, можно ли обойти город так, чтобы побывать на каждом мосту ровно один раз и вернуться в исходную точку. В 1735 году Эйлер доказал, что это невозможно. Эта классическая задача стала первой проблемой теории графов.
Как часто бывает в жизни, решение кажется простым, когда оно найдено. Оказалось, что для существования в графе эйлерова цикла необходимо и достаточно, чтобы все вершины имели четную степень. Вот короткий код, проверяющий выполнение этого свойства:
