Форум программистов, компьютерный форум CyberForum.ru
Наши страницы

С++ для начинающих

Войти
Регистрация
Восстановить пароль
 
cfkhellboy
1 / 1 / 0
Регистрация: 13.12.2010
Сообщений: 4
#1

Фундоментальные циклы графа - C++

13.12.2010, 13:30. Просмотров 924. Ответов 4
Метки нет (Все метки)

Нужна программа на C\C++.по фундоментальным циклам графа,есть прога подобная на паскале но она у меня почемуто не работает...хотя пример взят из книжки где автор утверждает что она работает))) вот она помогите кто чем сможет(((
Pascal
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
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
Program GraphCycle; {Фундаментальные циклы графа} 
uses CRT,DOS; 
Const 
nVertex=100; {Максимальное количество вершин} 
nAdjacent=1000; {Максимальная длина списка смежности} 
Туре 
TypeVertex=array[I..nVertex] of Integer; 
TypeAdjacent=array[1..nAdjacent] of Integer; 
{ Текстовый файл } 
{ Количество вершин } 
{ Количество вершин в стеке циклов} 
Var 
f :Text;
n :Integer;
nC :Integer;
Adj :TypeAdjacent; { Список смежности графа } 
Fst :TypeVertex; { Указатели вершин списка смежности} 
Nbr :TypeVertex; { Количество вершин в списке 
смежности } 
Vtx :TypeVertex; { Список вершин графа } 
Mark :TypeVertex; { Номера компонент для вершин графа} 
С :TypeVertex; { Стек выделения циклов графа } 
В :TypeVertex; { Признаки основных и обратных ребер 
прохода в глубину } 
jC :Integer; { Счетчик числа циклов } 
count:Integer; { Счетчик меток вершин } 
Procedure Init( var yes :Boolean ); 
{ Переназначение меток вершин } 
{ их порядковыми номерами в списке смежности } 
{ yes - признак правильной структуры списка смежности } 
Var 
i,j,m -.Integer; 
begin 
for i:=l to n do 
for j:=l to Nbr[i] do begin 
yes:=FALSE; 
for m:=l to n do 
if Adj[Fst[i]+j]=Vtx[m] then begin 
yes:=TRUE; 
Adj[Fst[i]+j]:=m; 
break; 
end; 
if not yes then exit; 
end; 
end; 
Procedure PrintCycle( x:Integer; var С:TypeVertex; 
nC:Integer); {Печать цикла из стека} 
begin 
Write(ffjC,')'); 
repeat 
Write(f,Vtx[C[nC]]:3); 
nC:=nC-l; 
until C[nC]=x; 
Writeln(f); 
end; 
Procedure Cycle( x,у:Integer ); 
Var 
i,v :Integer; 
begin 
 
count:=count+l; 
Mark[x]:=count; 
for i:=l to Nbr[x] do begin 
v:=Adj[Fst[x]+i]; 
nC:=nC+l; C[nC]:=v; 
if Mark[v]=0 then Cycle(v,x) 
else if (Mark[v]<Mark[x]) and (v<>y) then begin 
(Обратное ребро в пройденную вершину - найден цикл} 
PrintCycle(v,C,nC); 
end; 
nC:=nC-l; 
end; 
end; 
Procedure DepthCycle; {Проход в глубину за циклами) 
Var 
v:Integer; 
begin 
jC:=O; {Счетчик числа циклов} 
nC:=0; {С - стек циклов пустой } 
count:=0; {Номер метки вершины} 
for v:=l to n do Mark[v]:=0; 
for v:=l to n do if Mark[v]=0 then begin 
nC:=nC+l; C[nC]:=v; 
Cycle(v,0); 
nC:=nC-l; 
end; 
end; 
Var {Main} 
i,j :Integer; 
yes .-Boolean; 
begin {Main} 
Assign(f,'Cycle.in' ) ; 
Reset(f);{Файл открыт для чтения} 
{Ввод списка смежности} 
Read(f,n); {Количество строк в списке} 
Fst[l]:=0; {Указатель начала первой строки списка} 
for i:=l to n do begin 
Read(f,Vtx[i]); {Метка вершины} 
Read(f,Nbr[i]); {Количество вершин в списке} 
for j:=l to Nbr[i] do Read(f,Adj[Fst[i]+j]); 
{Список смежных вершин} 
Fst[i+1]:=Fst[i]+Nbr[i]; {Указатель начала следующей 
строки в списке} 
 end; 
Close(f); 
Assign(f,'Cycle.out' ) ; 
Rewrite(f); {Файл открыт для записи} 
Init(yes); 
if not yes then begin 
WriteLn(f,'Плохая структура смежности графа!'); 
Close(f) ; 
exit; 
end; 
DepthCycle; 
Close(f); 
end. {Main}
1
Надоела реклама? Зарегистрируйтесь и она исчезнет полностью.
Similar
Эксперт
41792 / 34177 / 6122
Регистрация: 12.04.2006
Сообщений: 57,940
13.12.2010, 13:30
Здравствуйте! Я подобрал для вас темы с ответами на вопрос Фундоментальные циклы графа (C++):

заданно матрицу смежности простого графа. Построить каркас этого графа с использованием поиска вширь - C++
Задание: заданно матрицу смежности простого графа. Построить каркас этого графа с использованием поиска вширь. Помогите написать...

Заменить в коде циклы for на циклы while - C++
int i, j, n; bool a; cin &gt;&gt; i &gt;&gt; n; for (i; i&lt;n; i++) { a = true; for (j = 2; j &lt;= i / 2; j++) if ((i%j) == 0) a =...

Периферия графа - C++
Ребят, есть у кого код на нахождение периферии графа?

Центр графа - C++
Дана матрица смежности. Найти максимальное расстояние в графе. Пол дня уже мучаюсь, искал в гугле, сам пытался, но ничего не...

построение графа - C++
Задача: &quot;Задан граф дерево с корневой вершиной. Нужно, начиная с корневой вершины, обойти все концевые вершины (концевая вершина имеет...

Построение графа - C++
Вершины и ребра графа назовем его элементами. По графу G построить граф T(G), у которого в качестве вершин взяты элементы G, а две вершины...

4
First_Big_Love
2 / 1 / 0
Регистрация: 14.12.2010
Сообщений: 3
15.12.2010, 17:24 #2
А не подскажите, что за книжечка такая, где была опубликована эта программа?
0
cfkhellboy
1 / 1 / 0
Регистрация: 13.12.2010
Сообщений: 4
15.12.2010, 19:02  [ТС] #3
Книжки Дискретные алгоритмы.Автор Иванов
0
First_Big_Love
2 / 1 / 0
Регистрация: 14.12.2010
Сообщений: 3
16.12.2010, 14:07 #4
спасибо большое
0
cfkhellboy
1 / 1 / 0
Регистрация: 13.12.2010
Сообщений: 4
29.12.2010, 17:53  [ТС] #5
никто ни чем не помог всем спасибо сам роздуплил
0
29.12.2010, 17:53
MoreAnswers
Эксперт
37091 / 29110 / 5898
Регистрация: 17.06.2006
Сообщений: 43,301
29.12.2010, 17:53
Привет! Вот еще темы с ответами:

Подобие графа - C++
Имеется примерно такой вот класс: class Room { private: string name; string story; vector &lt;Room*&gt; rooms; //указатели,...

Визуализация графа - C++
Есть произвольный граф, состоящий из набора узлов и связей между ними. Узлы представляются прямоугольниками с известной шириной и высотой,...

Конденсация графа - C++
Найти число компонент сильной связности, вот может быть кто-нибудь реализовывал нечто подобное?

Построение графа - C++
Помогите пожалуйста написать программу вот задание:Построить копию заданного графа. граф произвольный на ваш выбор. Добавлено через...


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

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

КиберФорум - форум программистов, компьютерный форум, программирование
Powered by vBulletin® Version 3.8.9
Copyright ©2000 - 2017, vBulletin Solutions, Inc.
Рейтинг@Mail.ru