LittelBlackAngel
16.09.2007, 11:30
Пожалуйста, посмотрите задачу. Просидела над ней все выходные, но поняла, что мне это не по силам.
Задача по теории графов. Рассчитать цикломатическое число для заданного графа.
Цикломатическое цисло = (ребра)-(вершины)+(компонент связности). Во этот самый компонент связности я не могу рассчитать. Может кто-нибудь писал такую прогу, пожалуйста, выложите ее полностью.
P.S. В инете нашла часть программы по подсчету компонента связности графа, но как-то не разобралась как ее вставить в общую программу...
Подсчет количества компонент связности
Задача. Определить количество компонент связности в заданном графе.
Рекурсивный алгоритм
Считаем, что граф задан матрицей смежности sm.
Каждый элемент специального линейного массива mark будет хранить номер компоненты связности, к которой принадлежит соответствующая вершина графа.
Алгоритм КомпСвяз-Рек
Совершить обход в глубину всех компонент связности графа, помечая вершины каждой из них отдельным номером.
Рекурсивная процедура обхода в глубину (прямого или обратного обхода) переберет все вершины, достижимые из начальной. Начальной вершиной для очередной компоненты связности может стать любая вершина, еще не отнесенная ни к какой другой компоненте связности (то есть еще не помеченная в массиве mark).
По окончании работы программы переменная kol будет содержать количество найденных компонент связности.
Реализация
procedure step (v: integer);
var j: integer;
begin
mark[v]:= k;
for j:=1 to N do
if (mark[j]=0)and(sm[v,j]<>0) then step(j);
end;
begin
...
for i:= 1 to N do mark[i]:=0;
k:= 0; {номер текущей компоненты связности}
for i:= 1 to N do
if mark[i]=0 then
begin inc(k);
step(i);
end;
...
end.
Пожалуйста, выложите программу целиком
Задача по теории графов. Рассчитать цикломатическое число для заданного графа.
Цикломатическое цисло = (ребра)-(вершины)+(компонент связности). Во этот самый компонент связности я не могу рассчитать. Может кто-нибудь писал такую прогу, пожалуйста, выложите ее полностью.
P.S. В инете нашла часть программы по подсчету компонента связности графа, но как-то не разобралась как ее вставить в общую программу...
Подсчет количества компонент связности
Задача. Определить количество компонент связности в заданном графе.
Рекурсивный алгоритм
Считаем, что граф задан матрицей смежности sm.
Каждый элемент специального линейного массива mark будет хранить номер компоненты связности, к которой принадлежит соответствующая вершина графа.
Алгоритм КомпСвяз-Рек
Совершить обход в глубину всех компонент связности графа, помечая вершины каждой из них отдельным номером.
Рекурсивная процедура обхода в глубину (прямого или обратного обхода) переберет все вершины, достижимые из начальной. Начальной вершиной для очередной компоненты связности может стать любая вершина, еще не отнесенная ни к какой другой компоненте связности (то есть еще не помеченная в массиве mark).
По окончании работы программы переменная kol будет содержать количество найденных компонент связности.
Реализация
procedure step (v: integer);
var j: integer;
begin
mark[v]:= k;
for j:=1 to N do
if (mark[j]=0)and(sm[v,j]<>0) then step(j);
end;
begin
...
for i:= 1 to N do mark[i]:=0;
k:= 0; {номер текущей компоненты связности}
for i:= 1 to N do
if mark[i]=0 then
begin inc(k);
step(i);
end;
...
end.
Пожалуйста, выложите программу целиком