Алгоритмы на графах Представление графов Построение остовного дерева Нахождение компонент смежности Перебор в глубину и в ширину. - презентация

1 Алгоритмы на графах Представление графов Построение остовного дерева Нахождение компонент смежности Перебор в глубину и в ширину

2 Представление графа Матрица смежности Матрица инцидентности Списки ребер, инцидентных каждой вершине Список ребер

3 a b c d e a b c d e a b c d e a b c d e Матрицы смежности и инцидентности a b c d e

4 a b c d e a b c d e Матрица смежности для взвешенного графа

5 Построение минимального остовного дерева Алгоритм Краскала Вход: список E рёбер графа, |V| = p Выход: минимальный остов T в виде множества T := 0 упорядочить E в порядке возрастания k:=1 for i:=1 to p-1 do while добавление ребра E k образует цикл в T do k:=k+1 end while T := T + E k end for Вход: граф G(V,E), заданный матрицей длин рёбер Выход: минимальный остов T T := V (пустой граф) while в T больше одного поддерева do взять поддерево найти к нему ближайшее добавить это ребро в T end while

6 Обход графа в глубину var n, nk :integer; c : array[1..100,1..100] of integer; s: array [1..100] of integer; procedure depth(x:integer); var i : integer; begin write(x:2); s[x]:=nk; for i:=1 to n do if c[x,i] > 0 then if s[i] = 0 then begin s[i]:=nk; depth(i); end; var i, j :integer; fi, fo : text; begin assign(fi,'input1.txt'); reset(fi); read (fi,n); for i:=1 to n do for j:=1 to n do read(fi,c[i,j]); close(fi); for i:=1 to n do s[i]:=0; nk:=1; depth(1); writeln; end.

7 Обход графа в ширину var n, k, i, j, nk :integer; c : array[1..100,1..100] of integer; s: array [1..100] of integer; o : array [1..100] of integer; procedure width(x:integer); var y,p : integer; begin o[1]:=x; k:=1; p:=0; s[x]:=nk; while pk do begin p:=p+1; y:=o[p]; for i:=1 to n do if c[y,i] > 0 then if s[i] = 0 then begin k:=k+1; o[k]:=i; s[i]:=nk; end; var fi, fo : text; begin assign(fi,'input1.txt'); reset(fi); read (fi,n); for i:=1 to n do for j:=1 to n do read(fi,c[i,j]); close(fi); for i:=1 to n do s[i]:=0; nk:=1; width(1); for i:=1 to n do write(o[i]:2); writeln; end.