2.4.6. Очереди

Другой специальный тип списка - очередь (queue), где элементы вставляются с одного конца, называемого задним (rear), а удаляются с другого, переднего (front). Очереди также называют «списками типа FIFO» (аббревиатура FIFO расшифровывается как first-in-first-out: первым вошел - первым вышел). Операторы, выполняемые над очередями, аналогичны операторам стеков. Существенное отличие между ними состоит в том, что вставка новых элементов осуществляется в конец списка, а не в начало, как в стеках. Кроме того, различна устоявшаяся терминология для стеков и очередей.

1. NULLQUEUE(Q) очищает очередь Q, делая ее пустой. При реализации очереди на списке Q оператор NULLQUEUE(Q) эквивалентен NULLIST(Q).

2. FRONT(Q) - функция, возвращающая первый элемент очереди Q. Можно реализовать эту функцию с помощью операторов списка как RETRIEVE(FIRST(Q),Q).

3. ENQUEUE(x,Q) вставляет элемент x в конец очереди Q. С помощью операторов списка этот оператор можно выполнить следующим образом: INSERT(x, NEXT(LAST(Q),Q), Q).

4. DEQUEUE(Q) удаляет первый элемент очереди Q. C помощью операторов списка данный оператор записывается как DELETE(FIRST(Q),Q).

5. EMPTYQUEUE(Q) возвращает значение true тогда и только тогда, когда Q является пустой очередью. При реализации очереди на списке Q оператор EMPTYQUEUE(Q) эквивалентен EMPTYLIST(Q).

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

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

Пусть 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 и содержащее все его вершины.

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