6.8.Реализация очередей

При реализации очередей, как и при реализации стеков, используется реализация списков.

Если реализация списков осуществлена на массивах, то реализация оператора удаления первого элемента очереди DEQUEUE(Q)=DELETE(FIRST(Q),Q) не эффективна т.к. требует перемещения всех элементов очереди.

Аналогичная ситуация возникала при реализации стека на списке созданного на массиве. В случае стека перемещения всех элементов удалось избежать путем идентификации вершины стека последней позицией списка. Поступим аналогично и при реализации очереди. В результате удаление первого элемента очереди будет осуществляться за одно действие DEQUEUE(Q)=DELETE(LAST(Q),Q). Однако вставка элемента в конец очереди будет осуществляться путем перемещения всех элементов очереди - ENQUEUE(x,Q)=INSERT(x,FIRST(Q),Q).

Таким образом, простым изменением идентификации первого элемента нельзя добиться выполнение обоих операторов ENQUEUE(x,Q) и DEQUEUE(Q) за одно действие. Поэтому при реализации очереди на массивах используют так называемые циклические массивы. В циклическом массиве считается, что за последним элементом следует первый элемент. Такая связь является логической и организуется программным способом.

Предложите способ реализации очереди на циклическом массиве.

6.9.Графы и деревья

Понятия теории графов широко используются при формализации различных задач. Термин "граф" ввел Д.Кенег в 1936 г.

Пусть V - непустое множество, V^{2} - множество всех его двухэлементных подмножеств. Пара (V,E), где ЕV^{2}, называется графом или неориентированным графом.

Элементы множества V называют вершинами графа, а элементы множества E – ребрами графа.

Ориентированным графом (орграфом), называется пара (V,E), где EVV= {(v₁,v₂)|v₁V,v₂V}.

То есть в ориентированном графе важен порядок вершин составляющих ребро. В ориентированных графах вместо термина «ребро» используют термин «дуга». ¹

Далее, если речь идет о графе G=(V,E) множество вершин будем обозначать VG, а множество ребер (дуг) - EG.

Граф G можно представить в виде некоторой геометрической структуры, состоящей из двух множеств: множества точек (вершин) VG и отрезков (ребер) ЕG, которые соединяют некоторые пары точек из VG. Если указаны начало и конец ребра, то отрезок заменяют направленным отрезком.

Две вершины u и v называются смежными, если множество {u,v} является ребром (дугой), и не смежными в противном случае. Также, в этом случае говорят, что u и v являются концевыми вершинами ребра e={u,v}. Для дуги e=(u,v) концевую вершину u называют началом, a v - концом дуги.

Ребра (дуги) называются смежными, если они имеют общую концевую вершину.

Вершина v и ребро (дуга) е называются инцидентными, если v концевая вершина е, и не инцидентными в противном случае.

Ребро e={v,v} или дуга e=(v,v) называется петлей.

Ребра e₁={u,v},e₂={u,v},...,е_k={u,v} называются кратными.

Дуги e₁=(u,v),e₂=(u,v),...,е_k=(u,v) называются параллельными.

Цепью называется любая последовательность попарно различных ребер (дуг), такая, что соседние ребра (дуги) в ней смежны. В орграфе если в цепи учтена ориентация дуг, то она называется путем.

Если не требовать, чтобы ребра (дуги) в упомянутой последовательности были различны, то получим понятие маршрута (ориентированного маршрута).

Циклом называется цепь, у которой начальная и конечная вершины совпадают.

Контуром называется путь, у которого начальная и конечная вершины совпадают.

Граф называется связным, если для каждой пары вершин найдется соединяющий их маршрут.

Граф, который не содержит циклов, называется ациклическим.

Связный неориентированный ациклический граф называется деревом, множество деревьев называется лесом.

Граф Н называется подграфом (или частью) графа G, если VHVG, ЕНEG. Если Н - подграф графа G, то говорят, что Н содержится в G.

Покрывающим (или остовным) деревом графа G называется дерево, являющееся подграфом графа G и содержащее все его вершины.

Если каждому ребру (дуге) графа поставлено в соответствие одно или несколько чисел, то такой граф называется взвешенным.