Форум: "Основная";
Текущий архив: 2003.12.23;
Скачать: [xml.tar.bz2];

Вниз

Надо обойти граф... а он что-то зацикливается.   Найти похожие ветки 

← →
Rradion   (2003-12-09 15:51) [0]

Есть граф ( см. картинку ), V это вершины, E дуги. Построил по нему матрицу инцидентности.

Катринка -> http://www.elena-antimonova.com/BRT/grafi.jpg

Теперь этот граф ( матрицу ) надо обойти... написал такой код.


procedure TForm1.Button2Click(Sender: TObject);
begin

V:=1; // nachinaem s Vershini 1
Oboshli:=1; // Schitaem chto ee oboshli

While Oboshli <> 10 do // poka ne oboshli vse 10 vershin
begin
E:=1;
While ( StringGrid1.Cells[E, V] <> "1" ) or ( E<>11 ) do E:=E+1; // perebiraem dugi (E), poka naidem dugu ili net

If E < 11 then // esli nashli dugu...
begin
While ( StringGrid1.Cells[E, V] <> "1" ) or ( V<>11 ) do V:=V+1; // ...ishim ei podhodjashiju vershinu
If V < 11 then // esli nashli vershinu
begin
Oboshli:=Oboshli+1; // Oboshli+1
StringGrid1.Cells[E, V] := "1o"; // Otmechaem vershinu, kak oboidennaju
end
else V:=1 // esli ne nashli vershini, to obratno k V!
end
else V:=1; // esli ne nashli dugi, to obratno k V!
end;
end;


А он, почему-то, зависает. Посмотрите плиз свежим глазом...

Заранее Благодарю!

---

← →
sashas   (2003-12-09 16:02) [1]

Разбираться щас не могу, но русские слова написанные английскими буквами выглядят не очень...

---

← →
sashas   (2003-12-09 16:03) [2]

Попробуй, есть много обходов - в глубину, в ширину и все они уже написаны.

---

← →
Rradion   (2003-12-09 19:50) [3]

>>Разбираться щас не могу, но русские слова написанные английскими буквами выглядят не очень...
А что делать, из кирилици Дельфи успешно кашицу делает :)

>>Попробуй, есть много обходов - в глубину, в ширину и все они уже написаны.
В глубину надо обойти, а уже написанного что-то так и не смог найти. Не подкинешь линк плиз?

Спасибо!

---

← →
Rradion   (2003-12-09 22:16) [4]

Нашел такой код ( http://ric.uni-altai.ru/Fundamental/pascal3/lab5/teor5-1.htm ) ...

t:=Head;
While t<>Tail do
begin t^.Flag:=TRUE; t:=t^.Next end;

PROCEDURE Depth_First_Search (r: Lref);
{ Рекурсивный обход графа в глубину }
{ r - указатель на структуру Вирта }
var t: Tref;
BEGIN
t:=r^.Trail; Write (r^.Key," "); r^.Flag:=FALSE;
While t<>Nil do
begin
If t^.Id^.Flag then Depth_First_Search (t^.Id);
t:=t^.Next
end
END;

только не очень понятно, что за "t" - как что ее, и др. переменные, обявить в VAR ?
Идея такая, что при нажатии кнопки программа должна обойти ( в глубину ) реализованный в матрице граф и выдать номера вершин, в порядке посещения.

Спасибо!

---

← →
Rradion   (2003-12-10 13:04) [5]

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

Благодарю Заранее!

---

← →
Ega23   (2003-12-10 14:27) [6]

А я уже забыл, что такое обход в глубину.
Это пути(цикы) Эйлера с Гамильтоном, что ли?

---

← →
Rradion   (2003-12-10 15:01) [7]

>>А я уже забыл, что такое обход в глубину.

Вроди нет, это...
(1) находясь в вершине x, нужно двигаться в любую другую, ранее непосещенную вершину (если таковая найдется), одновременно запоминая дугу, по которой мы впервые попали в данную вершину;
(2) если из вершины x мы не можем попасть в ранее непосещенную вершину или таковой нет, то мы возвращаемся в вершину z, из которой впервые попали в x, и продолжаем обход в глубину из вершины z.

---

← →
Ega23   (2003-12-10 15:46) [8]

И что дальше? Условие выхода из этого обхода? Что нужно найти: максимальный пройденный путь?

---

← →
VitGun   (2003-12-11 06:51) [9]

2 Radion. Огрогмный thanx за ссылку!!!!!!(5-й пост). Это то что я искал!!!!
З.Ы. Сорри за оффтопик.

---

Страницы: 1 вся ветка

Форум: "Основная";
Текущий архив: 2003.12.23;
Скачать: [xml.tar.bz2];

Наверх

Память: 0.46 MB
Время: 0.007 c