Информатика и информационные технологии
Добавить в закладки К обложке
- 1. Информатика. Информация - Страница 1
- 2. Представление чисел в ЭВМ. Формализованное понятие алгоритма - Страница 2
- 3. Введение в язык Pascal - Страница 3
- 4. Стандартные процедуры и функции - Страница 4
- 5. Операторы языка Pascal - Страница 5
- 6. Понятие вспомогательного алгоритма - Страница 6
- 7. Процедуры и функции в Pascal - Страница 7
- 8. Опережающие описания и подключение подпрограмм. Директива - Страница 8
- 9. Параметры подпрограмм - Страница 9
- 10. Типы параметров подпрограмм - Страница 10
- 11. Строковый тип в Pascal. Процедуры и функции для переменных строкового типа - Страница 11
- 12. Записи - Страница 12
- 13. Множества - Страница 13
- 14. Файлы. Операции с файлами - Страница 14
- 15. Модули. Виды модулей - Страница 15
- 16. Ссылочный тип данных. Динамическая память. Динамические переменные. Работа с динамической памятью - Страница 16
- 17. Абстрактные структуры данных - Страница 17
- 18. Стеки - Страница 18
- 19. Очереди - Страница 19
- 20. Древовидные структуры данных - Страница 20
- 21. Операции над деревьями - Страница 21
- 22. Примеры реализации операций - Страница 22
- 23. Понятие графа. Способы представления графа - Страница 23
- 24. Различные представления графа - Страница 24
- 25. Объектный тип в PascalПонятие объекта, его описание и использование - Страница 25
- 26. Наследование - Страница 26
- 27. Создание экземпляров объектов - Страница 27
- 28. Компоненты и область действия - Страница 28
- 29. Методы - Страница 29
- 30. Конструкторы и деструкторы - Страница 30
- 31. Деструкторы - Страница 31
- 32. Виртуальные методы - Страница 32
- 33. Поля данных объекта и формальные параметры метода - Страница 33
- 34. Инкапсуляция - Страница 34
- 35. Расширяющиеся объекты - Страница 35
- 36. Совместимость типов объектов - Страница 36
- 37. Об ассемблере - Страница 37
- 38. Программная модель микропроцессора - Страница 38
- 39. Пользовательские регистры - Страница 39
- 40. Регистры общего назначения - Страница 40
- 41. Сегментные регистры - Страница 41
- 42. Регистры состояния и управления - Страница 42
- 43. Системные регистры микропроцессора - Страница 43
- 44. Регистры управления - Страница 44
- 45. Регистры системных адресов - Страница 45
- 46. Регистры отладки - Страница 46
- 47. Структура программы на ассемблере - Страница 47
- 48. Синтаксис ассемблера - Страница 48
- 49. Директивы сегментации - Страница 49
- 50. Структура машинной команды - Страница 50
- 51. Способы задания операндов команды - Страница 51
- 52. Способы адресации - Страница 52
- 53. Команды пересылки данных - Страница 53
- 54. Арифметические команды - Страница 54
- 55. Логические команды - Страница 55
- 56. Команды передачи управления - Страница 56
24. Различные представления графа
Для реализации графа в виде списка инцидентности можно использовать следующий тип:
Type List = ^S;
S = record;
inf: Byte;
next: List;
end;
Тогда граф задается следующим образом:
Var Gr: array[1..n] of List;
Теперь обратимся к процедуре обхода графа. Это вспомогательный алгоритм, который позволяет просмотреть все вершины графа, проанализировать все информационные поля. Если рассматривать обход графа в глубину, то существуют два типа алгоритмов: рекурсивный и нерекурсивный.
На языке Pascal процедура обхода в глубину будет выглядеть следующим образом:
Procedure Obhod(gr: Graph; k: Byte);
Var g: Graph; l: List;
Begin
nov[k]:= false;
g:= gr;
While g^.inf <> k do
g:= g^.next;
l:= g^.smeg;
While l <> nil do begin
If nov[l^.inf] then Obhod(gr, l^.inf);
l:= l^.next;
End;
End;
Представление графа списком списков
Граф можно определить с помощью списка списков следующим образом:
Type List = ^Tlist;
Tlist = record
inf: Byte;
next: List;
end;
Graph = ^TGpaph;
TGpaph = record
inf: Byte;
smeg: List;
next: Graph;
end;
При обходе графа в ширину мы выбираем произвольную вершину и просматриваем сразу все вершины, смежные с ней.
Приведем процедуру обхода графа в ширину на псевдокоде:
Procedure Obhod2(v);
Begin
queue = O;
queue <= v;
nov[v] = False;
While queue <> O do
Begin
p <= queue;
For u in spisok(p) do
If nov[u] then
Begin
nov[u]:= False;
queue <= u;
End;
End;
End;