Программирование на языке Ruby, Фултон Хэл

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

на обложку

Фултон Хэл

Шрифт:

И все же у графов есть немало практических приложений. Возьмите обычную дорожную карту, на которой города соединены скоростными магистралями, или печатную плату. То и другое удобно представлять в виде графов. Компьютерную сеть тоже можно описать в терминах теории графов, будь то локальная сеть из нескольких десятков машин или весь Интернет, насчитывающий миллионы узлов.

Под графом мы обычно понимаем неориентированный граф. Попросту говоря, в нем не проставлены стрелки на соединительных линиях; две вершины либо соединены, либо нет. Между тем в ориентированном графе (орграфе) могут быть «улицы с односторонним движением»; из того, что вершина 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

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

def [](x,y)

if x > y

@store[x,y]

elsif x < y

@store[y,x]

else

end

def []=(x,y,v)

if x > y

@store[x,y]=v

elsif x < y

@store[y,x]=v

else

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

def vmax

@max

end

def degree x

sum = 0

0.upto @max do |i|

sum += self[x,i]

end

sum

end

def each_vertex

(0..@max).each {|v| yield v}

end

def each_edge

for v0 in 0..@max

for v1 in 0..v0-1

yield v0, v1 if self[v0,v1]==1

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. Является ли граф связным?

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