Program breadth_first_search; Const n=9; m:array[1..n, 1..n] of boolean = ( (False, True, True, False, False, False, False, False,False), (True, False, True, False, False, False, True, True,False), (True, True, False, True, True, False, False, False,False), (False, False, True, False, True, False, False, False,False), (False, False, True, True, False, True, False, True,False), (False, False, False, False, True, False, True, True, True), (False, True, False, False, False, True, False, True, True), (False, True, False, False, True, True, True, False,False), (False, False, False, False, False, True, True, False, False) ); Var A, B: integer;Procedure A_to_B(A, B: integer); Var Visited: array[1..n] of boolean; Prev: array[1..n] of integer; c: array[1..n] of integer; head, tail: integer; f: boolean; i, v, k: integer; Begin head:=1; tail:=1; f:=False; For i:=1 to n do Begin Visited[i]:=False; Prev[i]:=0 End; C[tail]:=A; Visited[A]:=True; While (head<=tail) and not f do Begin v:=C[head]; head:=head+1; For k:=1 to n do if m[v, k] and not Visited[k] then Begin tail:=tail+1; C[tail]:=k; Visited[k]:=True; Prev[k]:=v; if k=B then Begin f:=true; break End End End; if f then Begin k:=B; Write(B); While Prev[k]<>0 do Begin Write('<-', Prev[k]); k:=Prev[k] end End elseWrite('Пути из ', A, ' в ', B, ' нет')end;Begin Write('A= '); readln(A); Write('B= '); readln(B); A_to_B(A, B) End.
Поисквглубину.
Идея поиска в глубину проста: отправляясь от текущей вершины, мы находим новую (еще не пройденную) смежную с ней вершину, которую помечаем как пройденную и объявляем текущей. После этого процесс возобновляется. Если новой смежной вершины нет (тупик), возвращаемся к той вершине, из которой попали в текущую, и делаем следующую попытку. Если попадем в вершину B, печатаем путь. Если все вершины исчерпаны - такого пути нет. Заметим, что построенный таким образом алгоритм способен находить все пути из A в B, но первый найденный необязательно должен быть кратчайшим. Как обычно, алгоритм с возвратами легче всего оформить с помощью рекурсивной процедуры. Для ее реализации нам понадобятся: матрица m[1..n, 1..n] - матрица смежности графа; вспомогательный массив visited[1..n], который мы будем для того, чтобы отмечать уже пройденные вершины (visited[i]=TRUE <=> вершина i пройдена); переменная f, которая примет значение TRUE, когда путь будет найден.
Program depth_first_search; Const n=9; m:array[1..n, 1..n] of boolean = ( (False, True, True, False, False, False, False, False,False), (True, False, True, False, False, False, True, True,False), (True, True, False, True, True, False, False, False,False), (False, False, True, False, True, False, False, False,False), (False, False, True, True, False, True, False, True,False), (False, False, False, False, True, False, True, True, True), (False, True, False, False, False, True, False, True, True), (False, True, False, False, True, True, True, False,False), (False, False, False, False, False, True, True, False, False) ); Var A, B: integer;Procedure A_to_b(A, B: integer); Var Visited: array[1..n] of boolean; f: boolean; i: integer;Procedure Depth(p: integer); var k: integer; Begin Visited[p]:=True; For k:=1 to n do If not f then If m[p, k] and not Visited[k] then If k=B then Begin f:=True; Write(B); Break End else Depth(k); If f then write('<=', p); End;Begin For i:=1 to n do Visited[i]:=False; f:=false; Depth(A); If not f then write('Путииз', A, ' в', B, ' нет') End;Begin write('A= '); readln(A); write('B= '); readln(B); A_to_B(A, B) End.Заключение
Курсовой проект выполнен на тему «Графы и их представление на ЭВМ». В нём рассмотрены следующие вопросы:
- Определение графов: основное определение, смежность, другие определения;
- Способы задания графов: изображение графа, способы численного представления графов, представление ориентированных граф;
- Виды графов и операции над ними: элементы графов, изоморфизм графов, тривиальные и полые графы, двудольные графы, направленные орграфы и сети, операции над графами;
- Представление графов в ЭВМ: требование к представлению графов, реализация алгоритмов поиска в глубину и ширину в программной среде TurboPascal;
На основании найденной информации (учебная литература, Internet), я выделил основные пункты, которые наиболее полно и точно дают представление о графах и их представлении на ЭВМ. При выполнении работы были приведены примеры графов, а также различные способы их задания и представлены на основании заданных графов соответствующие им матрицы смежности и инцидентности. Были исследованы свойства операций над графами и к некоторым их них составлены графические изображения. В последней главе необходимо было указать на связь между графами и их представлением на ЭВМ, особенно это важно, на мой взгляд, для специальности математика-программиста.
После проделанной работы можно сделать следующий вывод:
Графы широко используются как в самой математике, так и в ее приложениях. Они применяются при построении различных математических моделей: линий электропередачи, сетей автодорог, линий воздушных сообщений и пр.
Список использованной литературы
1. Дискретная математика для программистов / Ф.А.Новиков. – СПб.: Питер, 2002. – 304 с.
2. Судоплатов С.В., Овчинникова Е.В. Элементы дискретной математики: Учебник. – М.: ИНФРА-М, Новосибирск: Изд-во НГТУ, 2002. – 280 с. – (Серия «Высшее образование»)
3. Материал из Википедии — свободной энциклопедии. Элементы теории граф (http://referats/mat_graph);
4. Элементы теории граф (http://book.itep.ru/10/graph1021.htm).