поиске в ширину
поиске в ширину просматриваются все вершины связного графа. Использование массива Nnew обеспечивает “подключение” очередного ребра к каркасу без образования циклов. Действительно, цикл образуется, если мы соединяем две просмотренные вершины. Но в нашем случае “подключается” ребро, соединяющее просмотренную вершину с непросмотренной. И наконец, по самой логике методов поиска в глубину и в ширину мы строим связный граф.
Построение каркаса для связного графа методом поиска в глубину.
procedure Tree_Depth(v:integer); {рекурсивная процедура}
{A, Nnew, Tree, yk - глобальные структуры данных}
var i:integer;
begin
Nnew[v]:=false;
for i:=1 to N do if (A[v,i]<>0) and Nnew[i] then begin
{добавляем ветвь в каркас}
Inc(yk);Tree[1,yk]:=v;Tree[2,yk]:=i;
Tree_Depth(i);
end;
end;
{фрагмент основной логики}
begin
FillChar(Nnew,SizeOf(Nnew),true);yk:=0;
Tree_Depth(1); {строим от первой вершины}
<вывод каркаса>;
end.
Построение каркаса для связного
Индекс
Элементарные функции
Линейные уравнения
Нелинейные уравнения
Случайные числа
