0 / 0 / 0
Регистрация: 22.11.2012
Сообщений: 5
1

Нахождение истоков и стоков ориентированного графа

29.11.2012, 09:53. Показов 2659. Ответов 0
Метки нет (Все метки)

Студворк — интернет-сервис помощи студентам
кто сможет помочь??? проблема с нахождением истоков и стоков графа...
нашла алгоритм поиска истоков в ориентированном ацикличном графе. но как-то странно он реализован....
получается если в вершине нет цикла то он источник! как это исправить и как найти еще стоки графа?
граф задан списком смежных вершин

Delphi
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
type TUk1=^TEl1; //элемент списка вершин
     TEl1=record
            Next:TUk1;
            Inf:integer;
          end;
     TUk=^TEl;
     TEl=record //элемент списка смежности
           Left:TUk1;
           Inf:integer;
           Down:TUk;
         end;
 
но есть процедура реализующая построение матрицы смежности, поэтому можно и через список и через матрицу реализовать.
 
 
{-----находим источники орграфа----}
procedure FindIstok;
var
f:boolean;
i,k:integer;
Istochnik:array of byte;
p,p1:TUk;
p2:TUk1;
begin
setlength(Istochnik,max);
for i:=0 to max-1 do Istochnik[i]:=0;
if (Head=Nil) then WriteLn('V grafe net ni odnoj vershini!!!')
else begin //если граф не пуст
k:=0;
p:=Head; //пробегаем по списку вершин
while (p<>Nil) do
begin
if (p^.Left<>Nil) then
begin //если список смежных с текущей пуст
f:=true; //то предпологаем что это источник
p1:=Head; //пробегаем снова по списку вершин
while (p1<>Nil) do
begin
p2:=p1^.Left; //указатель на первую вершину в списке смежных
while ((f)and(p2<>Nil)) do //проходим по списку смежных с текущей
begin
if p2^.Inf=p^.Inf then
f:=false; //если она равна вершине, у которой список смежных пуст(мы ее нашли на предыдущем шаге), то это не источник
p2:=p2^.Next; //переход на следующий элемент в списке смежных вершин
end;
p1:=p1^.Down; //переход на следующий элемент в списке вершин
end;
if (f=true) then //если найденная вершина все-таки источник
begin //то записываем ее в массив источников
inc(k);
// setlength(Istochnik, k);
Istochnik[k-1]:=p^.Inf;
end;
end;
p:=p^.Down;
end;
 
end;
if k=0 then writeln('Istochnikov v grafe net! ')
else for i:=0 to k-1 do Write(Istochnik[i]:2);
end;
0
Programming
Эксперт
94731 / 64177 / 26122
Регистрация: 12.04.2006
Сообщений: 116,782
29.11.2012, 09:53
Ответы с готовыми решениями:

Нахождение фактора графа и остова графа для некоторого произвольного графа (5-6 вершин)
Форумчане прошу помощь в выполнение задания по деск. мат. Задание: Нахождение фактора графа и...

Построение ориентированного графа
Привет!) Покажу код, то что я делал. На выходе нету расстояний(стоимости). Как добавить...

Остов не ориентированного графа
Здравствуйте, подскажите, пожалуйста. Дан неориентированный взвешенный граф, нужно построить остов....

Рисование ориентированного графа
Я, как нуб, ищу простой способ нарисовать граф с парой доп условий: - ноды должны содержать текст...

0
29.11.2012, 09:53
IT_Exp
Эксперт
87844 / 49110 / 22898
Регистрация: 17.06.2006
Сообщений: 92,604
29.11.2012, 09:53
Помогаю со студенческими работами здесь

Найти квадрат ориентированного графа
Здравствуйте , помогите, пожалуйста решить задачу по графам: 1.Дан ориентированный граф. Найти...

Создание ориентированного графа в Canvas
Помогите) Нужно на форме создавать граф прямо в программе. Ставим точки ЛКМ вручную, а программа...

Автоматическое построение ориентированного графа
Сломал себе мозг, но не могу решить проблему! Необходимо на основе таблицы построить...

BFS для ориентированного графа
Имеется граф такого вида. Что непонятно: 1)Как добавлять смежные вершины в очередь для их...


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

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

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