Маршруты на графах Нахождение компонент связности Поиск маршрутов, удовлетворяющим определённым требованиям Кратчайшие маршруты. - презентация

1 Маршруты на графах Нахождение компонент связности Поиск маршрутов, удовлетворяющим определённым требованиям Кратчайшие маршруты

2 Обход графа и в ширину и в глубину Вход: граф G(V,E), начальная вершина x V for v V do s[v] := 0 x T (* поместить x в структуру T *) s[x]:=1 while T do u T (* извлекаем вершину из T *) выдать u for w Г(u) do (* Г(u) – вершины, смежные u *) if s[w] = 0 then w T s[w] := 1 end if end for end while

3 Нахождение компонент связности Вход: граф G(V,E), начальная вершина x V T = { x } S = while T S do u T / S (* извлекаем вершину из T *) S := S { u } T := T Г(u) (* Г(u) – вершины, смежные u *) end while

4 Нахождение компонент сильной связности procedure kss if T = then return v T; v T if Г[v] V = then C:=C M[v] V:=V \ {v} v T kss else for u Г[v] do if e[u] = 0 then u T e[u]:=1 else repeat w T V:=V \ {w} Г[u]:=Г[u] Г[w] M[u]:=M[u] M[w] until u=w w T V:=V {w} end if kss end for end if C := for v V do M[v] := {v} e[v] := 0 end for while V do select v V T v e[v]:=1 kss end while

5 Расстояние между вершинами на графе Граф без весов рёбер – алгоритм просмотра в ширину Взвешенный граф: Алгоритм Дейкстры Алгоритм Флойда

6 Алгоритм Дейкстры Матрицей смежности задан взвешенный граф. Отсутствие ребра задаётся бесконечностью. #define inf = 10000; int n, i, j, mind, minv; int c[200,200]; int s[200]; int d[200]; for(i=1;i

7 Алгоритм Флойда void dist() { long r; for(i=1;i