Форум программистов, компьютерный форум, киберфорум
Pascal (Паскаль)
Войти
Регистрация
Восстановить пароль
 
Рейтинг 4.83/12: Рейтинг темы: голосов - 12, средняя оценка - 4.83
2 / 2 / 0
Регистрация: 16.10.2009
Сообщений: 65
1

Нахождение основного дерева в графе методом поиска в глубину.

03.01.2010, 12:36. Показов 2395. Ответов 1
Метки нет (Все метки)

УСЛОВИЕ: Разработайте программу нахождения основного дерева в графе методом поиска в глубину! Посмотрите и найдите ошибку пожалуйста!

Переменные и структуры данных:
Pascal
1
2
3
4
5
n - кол-во вершин;
p - указатель вершины стека;
a:array[1..n,1..n] of integer - матрица смежности;
Used:array[1..n] of boolean - массив "просмотренности" (Used[k]=true, если вершина k уже была просмотрена):
St:array[1..n] of integer - стек (для нерекурсивного исполнения);

Pascal
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
procedure pg(k:integer);
var
  st:array[1..n] of integer;
  p,t,j:integer;
  isnew:boolean;
begin
  FillChar(St,sizeof(st),0); //инит стека
  p := 1;
  st[p] := k; //помещаем k-ую вершину
  Used[k] := false; 
  while p <> 0 do //пока стек не пуст
  begin
    t := St[p];//выбираем верхнюю вершину
    j := 1;
    isnew := false;
    repeat //ишем смежную пока не наидем или просмотрим все
      if Nnew[j] and (a[t,j]<>0)then isnew := true 
      else inc(j);
    until isnew of (j >= n);
    if isnew then begin inc(p);St[p] := j; Used[j] := false; end //если еще непросмотренная,
    else dec(p);                                                  //кидаем в стек и отмечаем как юзаную
  end;                                                            //если не такая то выбираем из стека следующую 
end;
__________________
Помощь в написании контрольных, курсовых и дипломных работ здесь
0
Programming
Эксперт
94731 / 64177 / 26122
Регистрация: 12.04.2006
Сообщений: 116,782
03.01.2010, 12:36
Ответы с готовыми решениями:

Построить стягивающее дерево неориентированного графа методом поиска в ширину и вывести список рёбер дерева
1: Построить стягивающее дерево неориентированного графа методом поиска в ширину и вывести список...

Подсчитать глубину дерева
У меня получается только подсчитать количество узлов в левом и правом поддереве. Кто-нибудь знает...

Найти максимальную глубину дерева
найти максимальную глубину дерева

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

1
372 / 286 / 97
Регистрация: 17.12.2009
Сообщений: 567
03.01.2010, 13:40 2
наверно имелось в виду остовное дерево - подграф без циклов с по крайней мере одним путем из любой вершины в любую. Как ведет себя твоя программ не понятно без всего кода.
в 19-ой строчке:
Pascal
1
until isnew of (j >= n);
это компилится О_о?
0
IT_Exp
Эксперт
87844 / 49110 / 22898
Регистрация: 17.06.2006
Сообщений: 92,604
03.01.2010, 13:40

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

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

Анимирование алгоритма поиска в глубину на графе
Вообщем нужно сделать такую же анимация как здесь -...

Алгоритм поиска в глубину в ориентированном графе
Добрый вечер,форумчане:) Знаю, что подобная тема встречалась тут довольно часто, но у меня все-таки...


Искать еще темы с ответами

Или воспользуйтесь поиском по форуму:
2
Ответ Создать тему
Опции темы

КиберФорум - форум программистов, компьютерный форум, программирование
Powered by vBulletin
Copyright ©2000 - 2022, CyberForum.ru