Форум программистов
 

Восстановите пароль или Зарегистрируйтесь на форуме, о проблемах и с заказом рекламы пишите сюда - alarforum@yandex.ru, проверяйте папку спам!

Вернуться   Форум программистов > Delphi программирование > Паскаль, Turbo Pascal, PascalABC.NET
Регистрация

Восстановить пароль
Повторная активизация e-mail

Купить рекламу на форуме - 42 тыс руб за месяц

Ответ
 
Опции темы Поиск в этой теме
Старый 29.04.2016, 13:24   #1
Max00766
Форумчанин
 
Регистрация: 15.11.2015
Сообщений: 151
По умолчанию Метод поиск в глубину ( граф ) - PascalABC.NET

Есть программа которая реализует метод поиска в глубину:
Код:
uses crt;
const
n=5;
var
i, j, start: integer;
visited: array[1..n] of boolean;
const graph: array[1..n,1..n] of byte =
((0, 1, 0, 0, 1),
(1, 0, 1, 1, 0),
(0, 1, 0, 0, 1),
(0, 1, 0, 0, 1),
(1, 0, 1, 1, 0));
{поиск в глубину}
procedure DFS(st: integer);
var r: integer;
begin
write(st:2);
visited[st]:=true;
for r:=1 to n do
if (graph[st, r]<>0) and (not visited[r]) then
DFS(r);
end;
{основной блок программы}
begin
clrscr;
writeln('Матрица смежности:');
for i:=1 to n do
begin
visited[i]:=false;
for j:=1 to n do
write(graph[i, j],' ');
writeln;
end;
write('Стартовая вершина >> '); read(start);
writeln('Результат обхода'); DFS(start);
end.
На сайте по этой проге нарисован такой граф:
dfs.png
Как связанна матрица которая в программе и граф который представлен?
Если менять расположение нулей и единиц в матрице как меняется граф?
Объясните пожалуйста
На всякий случай ссылка на сайт где я все это взял:
http://kvodo.ru/dfs.html
Max00766 вне форума Ответить с цитированием
Старый 29.04.2016, 14:05   #2
Serge_Bliznykov
Старожил
 
Регистрация: 09.01.2008
Сообщений: 26,238
По умолчанию

А Вы точно читали, что такое матрица смежности?!

если Вы читали и не поняли, как это связано с этим кодом на Паскале,
то поясню:

const graph: array[1..n,1..n] of byte =

Первая строка - связи первого элемента графа
((0, 1, 0, 0, 1),
0 - первый элемент не связан с первым
1 - первый элемент связан со вторым
0 - первый элемент не связан с третьим
0 - первый элемент не связан с четвёртым
1 - первый элемент связан с пятым


Вторая строка - связи второго элемента графа
(1, 0, 1, 1, 0),
1 - второй элемент связан с первым
0 - второй элемент не связан со вторым
1 - второй элемент связан с третьим
1 - второй элемент связан с четвёртым
0 - второй элемент не связан с пятым

Третья строка - связи третьего элемента графа
(0, 1, 0, 0, 1),

и т.д.
Serge_Bliznykov вне форума Ответить с цитированием
Старый 29.04.2016, 14:28   #3
Max00766
Форумчанин
 
Регистрация: 15.11.2015
Сообщений: 151
По умолчанию

Цитата:
Сообщение от Serge_Bliznykov Посмотреть сообщение
А Вы точно читали, что такое матрица смежности?!

если Вы читали и не поняли, как это связано с этим кодом на Паскале,
то поясню:

const graph: array[1..n,1..n] of byte =

Первая строка - связи первого элемента графа
((0, 1, 0, 0, 1),
0 - первый элемент не связан с первым
1 - первый элемент связан со вторым
0 - первый элемент не связан с третьим
0 - первый элемент не связан с четвёртым
1 - первый элемент связан с пятым


Вторая строка - связи второго элемента графа
(1, 0, 1, 1, 0),
1 - второй элемент связан с первым
0 - второй элемент не связан со вторым
1 - второй элемент связан с третьим
1 - второй элемент связан с четвёртым
0 - второй элемент не связан с пятым

Третья строка - связи третьего элемента графа
(0, 1, 0, 0, 1),

и т.д.
Спасибо большое
Max00766 вне форума Ответить с цитированием
Ответ


Купить рекламу на форуме - 42 тыс руб за месяц

Опции темы Поиск в этой теме
Поиск в этой теме:

Расширенный поиск


Похожие темы
Тема Автор Раздел Ответов Последнее сообщение
PascalABC.Net Метод итераций для решения систем линейных уравнений now2 Помощь студентам 26 06.05.2014 14:07
граф поиск в глубину revoltecklol Паскаль, Turbo Pascal, PascalABC.NET 0 14.05.2012 23:47
метод обхода в глубину, граф Яна696 Паскаль, Turbo Pascal, PascalABC.NET 0 25.03.2012 16:14
Неориентированный граф. Поиск в глубину. Множество фундаментальных циклов jin200611 Паскаль, Turbo Pascal, PascalABC.NET 2 20.03.2012 18:57
Поиск кратчайшего пути в графе методом полного перебора в глубину. Метод ветвей и границ Олинька Помощь студентам 1 24.12.2008 16:22