Контрольные вопросы

1. Основные понятия теории графов

2. Перечислите алгоритмы представления графа

3. Особенности представления графа в виде массива

4. Особенности представления графа в виде матрицы смежности

5. Особенности представления графа в виде связанного списка

6. Особенности представления графа в виде списка дуг

7. Особенности преобразования структур графа

8. Реализация обходов в графах

9. Определение путей и контуров Эйлера

10. Поиск кратчайших путей методом Дейкстры

11. Поиск кратчайших путей методом Флойда-Уоршала

12. Определение остовных деревьев методом Крускала

13. Определение остовных деревьев методом Прима

Задания для практической работы

Выберите граф и выполните следующие операции:

1. представить граф в виде массива;

2. представить граф в виде матрицы смежности;

3. представить граф в виде связанного списка;

4. представить граф в виде списка дуг;

5. предусмотреть возможность преобразования структур графа;

6. реализовать обход графа в глубину и ширину;

7. определить если имеются путь и контур Эйлера;

8. реализовать поиск кратчайшего пути методом Дейкстры и методом Флойда-Уоршала. Провести сравнительные характкристики;

9. определить минимальноем остовное дерево методом Крускала и методом Прима. Провести сравнительные характкристики.

1. 2.

3. 4.

5. 6.

7. 8.

9. 10.

11. 12.

13. 14.

16.

15.

Глава 5. Алгоритмы сортировок

5.1. Сортировка выбором

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

Изложенный метод называется сортировкой выбором, поскольку он работает по принципу выбора наименьшего элемента из числа неотсортированных. На рис. 1 представлен пример работы этого метода.

A

S

O

R

T

I

N

G

E

X

A

M

P

L

E

A

S

O

R

T

I

N

G

E

X

A

M

P

L

E

A

A

O

R

T

I

N

G

E

X

S

M

P

L

E

A

A

E

R

T

I

N

G

O

X

S

M

P

L

E

A

A

E

R

T

I

N

G

O

X

S

M

P

L

E

A

A

E

E

T

I

N

G

O

X

S

M

P

L

R

A

A

E

E

G

I

N

T

O

X

S

M

P

L

R

A

A

E

E

G

I

N

T

O

X

S

M

P

L

R

A

A

E

E

G

I

L

T

O

X

S

M

P

N

R

A

A

E

E

G

I

L

M

O

X

S

T

P

N

R

A

A

E

E

G

I

L

M

N

X

S

T

P

O

R

A

A

E

E

G

I

L

M

N

O

S

T

P

X

R

A

A

E

E

G

I

L

M

N

O

P

T

S

X

R

A

A

E

E

G

I

L

M

N

O

P

R

S

X

T

A

A

E

E

G

I

L

M

N

O

P

R

S

X

T

A

A

E

E

G

I

L

M

N

O

P

R

S

T

X

A

A

E

E

G

I

L

M

N

O

P

R

S

T

X

Рис.1. Пример работа сортировки выбором

В этом примере первый проход не дал результата, поскольку слева от А в массиве нет элемента, меньшего А. На втором проходе другой элемент А оказался наименьшим среди оставшихся, поэтому он меняется местами с элементом S, занимающим вторую позицию. Далее, на третьем проходе, элемент Е, находящийся в середине массива, меняется местами с О, занимающим третью позицию; затем, на четвертом проходе, еще один элемент Е меняется местами с R, занимающим четвертую позицию и т.д.

Для каждого i от I до г-1 поменять местами элемент a[i] с минимальным элементом в последовательности a[i],...,a[r],. По мере продвижения индекса i слева направо, элементы слева от него занимают свои окончательные позиции в массиве (дальнейшим перемещениям они не подлежат), таким образом, массив будет полностью отсортирован, когда i достигнет его правого конца.

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