Обход графа, Алгоритм Форда – Фалкерсона и т.д. и т.п (Дискретная математика)

Посмотреть архив целиком

Обход графов в ширину и глубину

Описание алгоритма

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

Структура данных T является своего рода вспомогательным буфером, в который временно помещаются обойденные вершины (это необходимо для обхода смежных с ними вершин). Данная структура может являться стеком (в случае поиска в глубину) или очередью (в случае поиска в ширину).

Стек – это структура данных, в которой первый помещенный в нее элемент извлекается последним. Очередь – это структура данных, в которой первый помещенный в нее элемент извлекается первым.

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

1 – вершина отмечена (пройдена);

0 – вершина не отмечена.

Рассмотрим, как осуществляется обход поэтапно:

  1. Обнуление массива X. До начала обхода все вершины являются неотмеченными.

  2. Выбирается некоторая произвольная вершина v, с которой будет начинаться обход.

  3. Вершина v помещается в структуру Т и отмечается в массиве Х как пройденная (X [v] := 1).

  4. Из структуры T извлекается вершина (обозначим её u). Эта вершина является пройденной. Таким образом, именно на этом этапе мы выделяем обойденные вершины.

  5. По списку смежности Г поочередно выбираются все вершины смежные с v (обозначим вершину смежную с v w) и если они не были раннее отмечены (то есть, если X [w] = 0), то они помещаются в структуру Т и отмечаются.

Если в структуре T находятся какие-либо вершины, то осуществляется переход к п. 4. Если же нет, то обход графа G (V, E) закончен.

Пример

Обход графа в глубину:

Рассмотрим на примере обход графа G (V, E) (рис. 1).

Рис. 1

Список смежности ( Г )

1 – 2, 4

2 – 1, 3, 4

3 – 2, 4

4 – 1, 2, 3

  1. Обнулим массив X.

X:

1

2

3

4


0

0

0

0


  1. Начнем обход с первой вершины (v = 1).

  2. Поместим вершину 1 (v = 1) в структуру T и отметим ее в массиве X как пройденную.

T:

1





X:

1

2

3

4

1

0

0

0



  1. Извлекаем из структуры T вершину 1 (v = 1), т.е. вершина 1 пройдена.

T:






  1. Затем помещаем вершины, смежные с первой (v = 1) и еще не отмеченные в массиве X, в структуру T и отмечаем их в массиве X.

T:

2

4




X:

1

2

3

4

1

1

0

1



  1. Извлекаем из структуры T вершину 4 (v = 4), т.е. вершина 4 пройдена.

T:

2





  1. Затем помещаем вершины, смежные с четвертой (v = 4) и еще не отмеченные в массиве X (v = 2 и v = 3), в структуру T и отмечаем их в массиве X.

T:

2

3




X:

1

2

3

4

1

1

1

1



  1. Извлекаем из структуры T вершину 3 (v = 3), т.е. вершина 3 пройдена.

T:

2





  1. Все вершины, смежные с третьей, уже отмечены в массиве X, поэтому ничего не помещаем в структуру T.

  2. Извлекаем из структуры T вершину 2 (v = 2), т.е. вершина 2 пройдена.

T:






  1. Все вершины, смежные со второй, уже отмечены в массиве X, поэтому ничего не помещаем в структуру T.

  2. Структура T пуста. Обход вершин графа закончен: 1 – 4 – 3 – 2.


Обход графа в ширину:

Рассмотрим на примере обход графа G (V, E) (рис. 2).

Рис. 2

Список смежности ( Г )

1 – 2, 4

2 – 1, 3, 4

3 – 2, 4

4 – 1, 2, 3

  1. Обнулим массив X.

X:

1

2

3

4


0

0

0

0


  1. Начнем обход с первой вершины (v = 1).

  2. Поместим вершину 1 (v = 1) в структуру T и отметим ее в массиве X как пройденную.

    T:

    1





    X:

    1

    2

    3

    4


    1

    0

    0

    0


  3. Извлекаем из структуры T вершину 1 (v = 1), т.е. вершина 1 пройдена.

T:






  1. Затем помещаем вершины, смежные с первой (v = 1) и еще не отмеченные в массиве X, в структуру T и отмечаем их в массиве X.

    T:

    2

    4




    X:

    1

    2

    3

    4


    1

    1

    0

    1


  2. Извлекаем из структуры T вершину 2 (v = 2), т.е. вершина 2 пройдена.

T:

4





  1. Затем помещаем вершины, смежные со второй (v = 2) и еще не отмеченные в массиве X (v = 3), в структуру T и отмечаем их в массиве X.

    T:

    4

    3




    X:

    1

    2

    3

    4


    1

    1

    1

    1


  2. Извлекаем из структуры T вершину 4 (v = 4), т.е. вершина 4 пройдена.

    T:

    3




  3. Все вершины, смежные с четвертой, уже отмечены в массиве X, поэтому ничего не помещаем в структуру T.

  4. Извлекаем из структуры T вершину 3 (v = 3), т.е. вершина 3 пройдена.

T:






  1. Все вершины, смежные с третьей, уже отмечены в массиве X, поэтому ничего не помещаем в структуру T.

  2. Структура T пуста. Обход вершин графа закончен: 1 – 2 – 4 – 3.

На практике обход в глубину можно использовать, в частности, для получения ориентированного дерева из неориентированного. Рассмотрим это на примере.


Пример получения ориентированного дерева

Исходное дерево представлено на рис. 3. Наша цель – посредством обхода исходного дерева в глубину получить ориентированное дерево с корнем v и списком смежности Г’.

Рис. 3

Список смежности ( Г )

1 – 2, 3

2 – 1, 4, 5

3 – 1

4 – 2

5 – 2, 6, 7, 8

6 – 5

7 – 5

8 – 5

  1. Обнулим массив X.

X:

1

2

3

4

5

6

7

8

0

0

0

0

0

0

0

0


  1. Пусть корнем будет вершина 5 (v = 5). Поместим вершину 5 в структуру T и пометим ее как пройденную в массиве Х.

T:

5










X:

1

2

3

4

5

6

7

8

0

0

0

0

1

0

0

0

  1. Затем извлекаем из структуры Т вершину 5 (v = 5) и помещаем смежные с ней вершины (ранее не пройденные) в Т, отметим их в массиве X.


T:

2

6

7

8







X:

1

2

3

4

5

6

7

8

0

1

0

0

1

1

1

1


  1. Начинаем формировать список смежности ориентированного дерева (Г’). Для этого берем вершину v и выписываем из списка смежности исходного графа (Г) вершины, совпадающие с вершинами, находящимися в структуре Т (это будут вершины, смежные с v), то есть

Г’: 5 – 2, 6, 7, 8;

  1. Затем извлекаем из структуры Т вершину 8 (v = 8). Дополняем список смежности Г’ восьмой вершиной. У нее нет смежных вершин.

T:

2

6

7







Г: 5 – 2, 6, 7, 8; 8 – ;

  1. Затем извлекаем из структуры Т вершину 7 (v = 7). Дополняем список смежности Г’.

T:

2

6








Г: 5 – 2, 6, 7, 8; 8 – ; 7 – ;

  1. Затем извлекаем из структуры Т вершину 6 (v = 6). Дополняем список смежности Г’.

T:

2









Г’: 5 – 2, 6, 7, 8; 8 – ; 7 – ; 6 – ;

  1. Затем извлекаем из структуры Т вершину 2 (v = 2). В структуру Т вносим номера вершин, смежных с вершиной 2 (ранее не пройденных). Дополняем список смежности Г’.

T:

1

4









X:

1

2

3

4

5

6

7

8

1

1

0

1

1

1

1

1

Г: 5 – 2, 6, 7, 8; 8 – ; 7 – ; 6 – ; 2 – 1, 4;

  1. Извлекаем из структуры Т вершину 4 (v = 4). Дополняем список смежности Г’.

T:

1









Г: 5 – 2, 6, 7, 8; 8 – ; 7 – ; 6 – ; 2 – 1, 4; 4 – ;

  1. Извлекаем из структуры Т вершину 1 (v = 1). Дополняем список смежности Г’. Помещаем смежные с ней вершины (ранее не пройденные) в Т.

T:

3









X:

1

2

3

4

5

6

7

8

1

1

1

1

1

1

1

1

Г’: 5 – 2, 6, 7, 8; 8 – ; 7 – ; 6 – ; 2 – 1, 4; 4 – ; 1 – 3;

  1. Извлекаем из структуры Т вершину 3 (v = 3). Дополняем список смежности Г’.

T:










Г: 5 – 2, 6, 7, 8; 8 – ; 7 – ; 6 – ; 2 – 1, 4; 4 – ; 1 – 3; 3 – ;

  1. Структура Т пуста. Обход графа закончен. Получили следующий список смежности ориентированного дерева (Г’):

1 – 3

2 – 1, 4

3 –

4 –

5 – 2, 6, 7,8

6 –

7 –

8 –

Задания

Задание 1. Построить из исходного неориентированного дерева ориентированное методом обхода в глубину из первой вершины.


1.



2.





3.



4.



5.



6.

Задание 2. Построить из исходного неориентированного дерева ориентированное методом обхода в глубину из третьей вершины.


7.

8.

9.


10.

11.


12.

Задание 3. Построить из исходного неориентированного дерева ориентированное методом обхода в глубину из второй вершины.

13.




14.

15.

16.

17.




18.

Задание 4. Построить из исходного неориентированного дерева ориентированное методом обхода в глубину из четвертой вершины.


19.


20.

21.


22.

23.


24.


Задание 5. Построить из исходного неориентированного дерева ориентированное методом обхода в глубину из первой вершины.


25.

26.

27.



28.

29.


30.

Алгоритм ТэррИ

Описание алгоритма

Алгоритм Тэрри – алгоритм поиска маршрута в связном графе G (V,E), соединяющего заданные вершины v и w. Исходя из вершины v и осуществляя последовательный переход от каждой достигнутой вершины к смежной ей вершине, всегда можно найти маршрут в связном графе G (V,E), соединяющий заданные вершины v и w. Переход от вершины к вершине согласно алгоритму осуществляется по следующим правилам:

  1. при проходе ребра необходимо всякий раз отмечать направление, в котором оно было пройдено;

  2. исходя из некоторой вершины v, нужно всегда следовать по тому ребру, которое не было пройдено или было пройдено в противоположном направлении;

  3. для всякой вершины v, отличной от v, необходимо отмечать пометкой «х» первое заходящее ребро, если вершина vвстречается первый раз;

  4. исходя из вершины v, отличной от v, по первому заходящему в v ребру нужно идти лишь тогда, когда нет других возможностей.

Пример

Рассмотрим алгоритм Тэрри на примере поиска маршрута между вершинами 1 и 4 графа G (V, E) (рис. 4). Если это не противоречит правилам алгоритма, то переходить от одной вершины будем к смежной ей с меньшим номером.


Рис. 4

  1. Переходим из вершины 1 в вершину 2. отмечаем направление прохода ребра (рис. 5).


  1. Из вершины 2 можем перейти к вершинам 3 и 5, а также к вершине 1, но лишь в том случае, если нет других вариантов. Переходим к вершине 3. Отмечаем направление перехода (рис. 6).

    Рис. 5

    Рис. 6

  2. Из третьей вершины переходим в первую, так как она имеет наименьший номер среди всех возможных вариантов перехода (рис. 7).


  1. Первая вершина смежна с вершинами 2, 3 и 5. В вершину 2 мы не можем осуществить переход, так как это направление уже отмечено. В вершину 3 осуществлять переход не будем, так как ребро 1-3 уже отмечено как заходящее в вершину 1 и существует альтернатива перехода к вершине 5. Следовательно, переходим к вершине 5. Отмечаем направление перехода (рис. 8).


Рис. 7

Рис. 8


  1. Из вершины 5 переходим к вершине 2, так как она имеет наименьший номер среди всех возможных вариантов перехода (рис. 9).


  1. Из вершины 2 переходим к вершине 1, так как ребро, связывающее эти вершины, отмечено как заходящее в вершину 2, а не отмеченных ребер при рассматриваемой вершине нет. Отмечаем направление перехода (рис. 10).


Рис. 9

Рис. 10


  1. Из вершины 1 можно перейти только к вершине 3 (рис. 11).


  1. Из вершины 3 осуществляем переход к вершине 4, так как она имеет наименьший номер среди всех альтернативных вариантов (рис. 12). Поиск маршрута окончен.

Рис. 11

Рис. 12


Маршрут из вершины 1 в вершину 4 в соответствии с алгоритмом Тэрри имеет вид:

1 – 2 – 3 – 1 – 5 – 2 – 1 – 3 – 4

Задания:

Определить путь обхода графов.

1. Обход в ширину из точки 3.

2. Обход в ширину из точки 1.

3. Обход в ширину из точки 5.

4. Обход в глубину из точки 1.

5. Обход в глубину из точки 2.


6. Обход в ширину из точки 2.

7. Обход в ширину из точки 4.

8. Обход в глубину из точки 1.

9. Обход в глубину из точки 3.

10. Обход в глубину из точки 5.


11. Обход в ширину из точки 1.

12. Обход в ширину из точки 4.

13. Обход в ширину из точки 5.

14. Обход в глубину из точки 2.

15. Обход в глубину из точки 6.




16. Обход в ширину из точки 2.

17. Обход в ширину из точки 6.

18. Обход в глубину из точки 3.

19. Обход в глубину из точки 5.

20. Обход в глубину из точки 1.



21. Обход в ширину из точки 1.

22. Обход в ширину из точки 3.

23. Обход в ширину из точки 4.

24. Обход в глубину из точки 6.

25. Обход в глубину из точки 2.



26. Обход в ширину из точки 2.

27. Обход в ширину из точки 5.

28. Обход в глубину из точки 1.

29. Обход в глубину из точки 3.

30. Обход в глубину из точки 4.


Матроиды. Жадные алгоритмы.

Алгоритм Краскала

Описание алгоритма

Матроидом М = < E, > называется конечное множество Е, число элементов которого равно n (E= n), и семейство его подмножеств , которое содержится в множестве всех подмножеств множества Е ( 2E ) такое, что выполняются следующие три аксиомы:

М1: пустое множество принадлежит подмножеству ( );

М2: если множество А принадлежит подмножеству , то и множество В, которое содержится в множестве А, тоже принадлежит подмножеству .

(А В А В );

М3: если множества А и В принадлежат подмножеству и количество элементов множества А на один элемент меньше, чем в множестве В, то существует элемент, принадлежащий разности множеств В и А, такой, что объединение его с множеством А будет принадлежать подмножеству .

(А,В В=А+1 е В\А, А е )

Элементы множества называются независимыми, а остальные подмножества Е (2Е \ )– зависимыми. Пусть множество Х (произвольное множество) содержится в множестве Е. Максимальным независимым подмножеством множества Х называется множество Y такое, что если множество Y, принадлежащее независимому множеству , содержится в множестве Х и Z, принадлежащем независимому множеству , содержится в множестве Х, то множество Z содержится в множестве Y (YХ Y ZX ZY) . Множество максимальных независимых подмножеств множества Х обозначим Х.

Рассмотрим следующее утверждение, справедливое для любого Х:

М4: максимальные независимые подмножества данного множества равномощны ( Y Х Z Х Y= Z).

Пусть М = < E, > и выполнены аксиомы М1 и М2 . Тогда аксиома М3 и утверждение М4 эквивалентны, то есть М1, М2, М4 - эквивалентная система аксиом матроида.

Пусть имеются конечное множество Е, весовая функция и семейство 2E. Необходимо выбрать в указанном семействе подмножество Х наибольшего веса. Для решения этой задачи будем считать, что множество Е упорядочено в порядке убывания весов элементов. В начале множество Х пусто. Затем проверяем каждый элемент множества Е, начиная с первого: если объединение его с множеством Х принадлежит указанному семейству , то добавляем его в множество Х, если не принадлежит семейству , то рассматриваем следующий элемент, и так до n-го.

Алгоритм такого типа называется жадным. Очевидно, что жадный алгоритм является очень эффективным, он за наименьшее количество шагов находит искомое подмножество. Жадные алгоритмы и их свойства исследованы сравнительно недавно, но их значение в практике программирования чрезвычайно велико. Если удается свести конкретную экстремальную задачу к такой постановке, где множество допустимых вариантов (из которых необходимо выбрать наилучший) является матроидом, то в большинстве случаев следует сразу применять жадный алгоритм, поскольку он достаточно эффективен в практическом смысле. Если же наоборот, оказывается, что множество допустимых вариантов не образует матроида, то это «плохой признак». Скорее всего, данная задача окажется труднорешаемой. В этом случае целесообразно тщательно исследовать задачу для предварительного получения теоретических оценок сложности, чтобы избежать бесплодных попыток «изобрести» эффективный алгоритм там, где это на самом деле невозможно.

Другими словами, если М = < E, > - матроид, то для любой весовой функции жадный алгоритм находит независимое множество Х с наибольшим весом; если же М = < E, > не является матроидом, то существует такая функция , что множество Х, найденное жадным алгоритмом, не будет максимальным.

Пусть G (V,E) – граф. Остовной подграф G (V,E) – это подграф, содержащий все вершины. Остовной подграф, являющийся деревом, называется остовом. Несвязный граф не имеет остова, связный граф может иметь много остовов. Если задать длины рёбер, то можно поставить задачу нахождения кратчайшего остова. Существует множество различных способов найти какой-то остов графа. Множество кратчайших путей из заданной вершины ко всем остальным тоже образует остов. Однако этот остов может не быть кратчайшим. На рис. 13 показаны диаграмма графа, дерево кратчайших путей из вершины один с суммарным весом 5 и два кратчайших остова этого графа.


Рис. 13



Одним из способов нахождения кратчайшего остова в связном графе является алгоритм Краскала. Он является частным случаем жадного алгоритма. Заметим, что множество подмножеств множества рёбер, не содержащих циклов, образует матроид.


Алгоритм Краскала

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

  1. так как остов должен быть кратчайшим, выбор начинается с ребер минимальной длины;

  2. так как остов – это дерево (структура, не содержащая циклов), каждое выбранное ребро проверяется: не составляет ли оно цикла с ранее выбранными ребрами.

Цикл проходит n = v - 1 раз, где v – количество вершин графа.

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

Пример

На рис. 14 задан граф. Необходимо найти его минимальный остов при помощи алгоритма Краскала.

Решение:

Представим список ребер исходного графа с указанием длины каждого из них. Затем отсортируем ребра в порядке возрастания их длин.

Рис. 14

Исходный список


Отсортированный список

(1,2) - 2


(2,3) - 1

(1,4) - 3


(4,5) - 1

(2,3) - 1


(8,9) - 1

(2,5) - 2


(1,2) - 2

(3,6) - 3


(2,5) - 2

(4,5) - 1


(6,9) - 2

(4,7) - 4


(1,4) - 3

(5,6) - 4


(3,6) - 3

(5,8) - 3


(5,8) - 3

(6,9) - 2


(4,7) - 4

(7,8) - 4


(5,6) - 4

(8,9) - 1


(7,8) - 4

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


Шаг

Массив ребер

Компонента связности





Во втором столбце формируем массив ребер по принципу:

Шаг 1. Помещаем в первый столбец первое ребро отсортированного списка. Компонента связности данного ребра будет соответствовать вершинам, которые данное ребро связывает.

Шаг 2…Шаг N. Рассматриваем n-е ребро отсортированного списка:

  1. добавляем ребро в массив, если оно удовлетворяет условию ацикличности;

  2. пропускаем ребро в противном случае.

И так далее до конца списка ребер.

Проверка ацикличности формируемого массива производится при помощи третьего столбца таблицы, в который помещаются компоненты связности «леса», разрастающегося во втором столбце. Компоненты связности формируются следующим образом:

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

Шаг

Массив ребер

Компонента связности

1

(2,3)

2

(2,3); (4,5)

3

(2,3); (4,5); (8,9)


  1. Если одна из вершин добавляемого ребра входит в одну из имеющихся компонент связности, то ребро заносится в массив, соответствующий компоненте связности, а вторая вершина добавляемого ребра присоединяется к имеющейся компоненте.


Шаг

Массив ребер

Компонента связности

4

(2,3); (4,5); (8,9); (1,2)


  1. Если одна вершина рассматриваемого ребра входит в одну из имеющихся компонент связности, а вторая – в другую, то компоненты связности и массивы ребер объединяются.


Шаг

Массив ребер

Компонента связности

5

(2,3); (4,5); (8,9); (1,2); (2,5)


4) Если обе вершины рассматриваемого ребра принадлежат одной компоненте связности, то ребро исключается из рассмотрения, в таблицу изменения не вносятся. В рассматриваемом примере такими ребрами являются (1,4), (5,8), (5,6) и (7,8).

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


Шаг

Массив ребер

Компонента связности

6

(2,3); (4,5); (8,9); (1,2); (2,5); (6,9)

7

(2,3); (4,5); (8,9); (1,2); (2,5); (6,9) [(1,4)]

Шаг

Массив ребер

Компонента связности

8

(2,3); (4,5); (8,9); (1,2); (2,5); (6,9); (3,6)

9

(2,3); (4,5); (8,9); (1,2); (2,5); (6,9); (3,6) [(5,8)]

10

(2,3); (4,5); (8,9); (1,2); (2,5); (6,9); (3,6); (4,7)

11

(2,3); (4,5); (8,9); (1,2); (2,5); (6,9); (3,6); (4,7) [(5,6)]

12

(2,3); (4,5); (8,9); (1,2); (2,5); (6,9); (3,6); (4,7) [(7,8)]


Примечание: в квадратных скобках указано рассматриваемое на данном шаге ребро, но не включаемое в массив ребер в силу выполнения условия 4.


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

Таким образом, минимальным остовом исходного графа является остов, состоящий из ребер (2,3); (1,2); (2,5); (4,5); (8,9); (6,9); (3,6); (4,7).

Задания

Найти минимальный остов графа, заданного списком ребер, при помощи алгоритма Краскала.


Случайные файлы

Файл
145514.doc
24016.rtf
28032.rtf
143587.rtf
240-2101.DOC




Чтобы не видеть здесь видео-рекламу достаточно стать зарегистрированным пользователем.
Чтобы не видеть никакую рекламу на сайте, нужно стать VIP-пользователем.
Это можно сделать совершенно бесплатно. Читайте подробности тут.