Глава 58
По графу шагом марш!
Ознакомившись с графами, вернемся к программисту Нику, который все ещё царапает прибрежный песочек. «Если бы, – бормочет Ник, – мне надо было попасть из страны «E» в страну «H», то я бы поехал так». И он прочертил жирные стрелки, ведущие к цели через узлы «F» и «G» (рис. 138). «Но это я сообразил, глядя на карту, а без карты можно блуждать вот так», – и нацарапал стрелки, показанные пунктиром.
Как растолковать компьютеру верный путь? Нужна свежая идея! Новое – это всего лишь забытое старое – почему-то вспомнилось ему. «А не построить ли тебе здесь империю, как ты сделал это в 49-й главе?» – шепнул Нику внутренний голос. И мысли программиста двинулись в этом направлении.
Друзья, что вы слышали о постройке нынешних империй? Ведь на дворе не лютое средневековье! К чему проливать кровь, если от желающих нет отбоя, и очередь на присоединение к империям не пустует? Очередь упомянута мною не зря, – она играет важную роль в будущем алгоритме. Кстати, алгоритм этот придумали не программисты, а политики. Судите сами, сейчас вместе с Ником мы последуем их примеру.
На рис. 139 показан граф в начале строительства «империи» (дальше я пишу это слово без кавычек). Условимся об окраске его узлов. Все страны континента (узлы) отнесем к трем категориям: 1) независимые страны, 2) страны, желающие присоединиться к империи и 3) страны, вошедшие в её состав. Независимые страны окрасим белым цветом, желающие присоединиться – серым, а присоединенные к империи – черным.
Откуда начать строительство? Пусть центром империи будет страна «E». Окрасим её серым цветом и поставим в очередь на присоединение. Можно сказать, что страна «E» – первый кандидат на включение в несуществующую пока империю.
Серому кандидату поставим жесткое условие: хочешь быть принятым в империю и почернеть? Тогда уговори своих белых соседей тоже стать в очередь на присоединение и перекраситься в серый цвет. Так, страну «E» примут в империю, когда кандидатами на присоединение станут царства «D» и «F», что и показано на рис. 140. Кандидат, выполнивший это условие, удаляется из очереди на присоединение и включается в империю – чернеет.
К слову сказать, строя империю, Ник постоянно думал о купцах. Жирными стрелками на графе он помечал их воображаемое движение, как если бы купцы шли вослед завоевателям.
Итак, страна «E» вошла в империю, а два её соседа – «D» и «F» – стали в очередь на присоединение (в каком именно порядке – «D», затем «F» или наоборот – неважно). От них требуют то же самое – уговорить своих белых соседей. Так, для присоединения страны «D» ей надо убедить стать в очередь страны «A» и «C». По мере выполнения этого условия страны-кандидаты чернеют и удаляются из очереди. После двух следующих присоединений (стран «D» и «F») граф и очередь изменятся так, как показано на рис. 141 и рис. 142. Здесь же стрелками показано и воображаемое продвижение купцов.
