Тема 10. Алгоритмы на графах

на графах
Шевченко А. В.

на связность
Пример 1. Контроль качества печатных плат
В процессе изготовления печатных

плат металлизированные отверстия соединяются проводниками. При контроле продукции проверяется наличие или отсутствие соединения между различными точками.

В.
Алгоритм Уоршалла
1
2
3
4
5
6
1
1
1
2
1
3
4
5
6
1
1
2
3
4
5
6
7
8
7
1
8
1
1
7
1
1
8
1
T = C
Цикл i
Цикл j

Цикл k
Tjk = Tjk or (Tji and Tik)

Tij

...

...

Т - матрица транзитивных замыканий.

Уоршалла
int C[8][8] = {{-1, 1, 0, 0, 0, 1, 0,

0}, ...};
int T[8][8];
int n = 8;

for(int i = 0; i < n; i++)
for(int j = 0; j < n; j++)
T[i][j] = C[i][j];

for(int i = 0; i < n; i++)
for(int j = 0; j < n; j++)
if(j != i)
for(int k = 0; k < n; k++)
if(k != j)
T[j][k] = T[j][k] || T[j][i] && T[i][k];

Уоршалла
Tij
1
2
3
4
5
6
1
1
1
2
1
1
3
4
1
5
1
6
1
1
1
2
3
4
5
6
7
8
7
1
8
1
1
7
1
1
8
1
bool TestConnection(int Node1, int Node2)
{
return(T[Node1-1][Node2-1] == 1);

}

на связность
Пример 2. Транспортная сеть
Транспортная сеть представлена ориентированным графом, в

котором узлы соответствуют населенным пунктам, точкам пересечения улиц или дорог, а дуги - дорогам, связывающим узлы. Требуется проверить возможность путешествия из пункта А в пункт В.

Уоршалла
Cij
1
2
3
4
5
6
1
1
1
2
1
1
3
1
4
1
1
5
1
6
7
1
8
1
7
1
8
1
1
1
Tij
...
...
1
3
2
5
4
6
7
8
T = C
Цикл i
Цикл j

Цикл k
Tjk = Tjk or (Tji and Tik)

Т - матрица транзитивных замыканий.

Уоршалла
Tij
1
2
3
4
5
6
1
1
1
1
1
1
2
1
1
1
1
1
3
1
1
1
1
1
4
1
1
1
1
1
5
1
1
1
1
1
6
1
1
1
1
1
7
1
1
1
1
8
1
1
1
1
1
1
1
1
7
1
1
1
1
1
8
1
1
1
1
1
1
1
1
1
1
3
2
5
4
6
7
8
bool CanTravel(int A, int B)
{
return(T[A-1][B-1] == 1);

}

Уоршалла
Cij
1
2
3
4
5
6
1
1
1
2
1
1
3
1
4
1
1
5
1
6
7
1
8
7
1
8
1
1
Tij
...
...

Уоршалла
Tij
1
2
3
4
5
6
1
1
1
1
1
1
2
1
1
1
1
1
3
1
4
1
1
1
1
1
5
1
1
1
1
1
6
7
1
1
1
1
8
1
1
7
1
1
1
1
8
1
1
1
1
1
1
1

на поиск минимального пути
Пример. Транспортная сеть
Транспортная сеть представлена ориентированным графом,

в котором узлы соответствуют населенным пунктам, точкам пересечения улиц или дорог, а дуги - дорогам, связывающим узлы. Требуется найти минимальный путь из пункта А в пункт В.

Флойда
Сij
1
2
3
4
5
6
1
4

3


2
4
4



3




3
4
3


4

5

3



6





7



3
8






3

7



3

8




3

5
4

1
3
2
5
4
6
7
8
4
4
4
4
3
3
3
3
3
5
Tij
...
...
Hij
...
...
T = C
Цикл i
Цикл j

Цикл k
Tjk = min(Tjk , Tji + Tik)

Т - матрица минимальных расстояний,
Н - матрица путей.

Флойда
const int INF 1000000
int C[8][8] = {{INF, 4, INF, 3,

INF, INF, INF, INF}, ...};
int T[8][8];
int H[8][8];
const int n = 8;
for(int i = 0; i < n; i++)
for(int j = 0; j < n; j++)
{
T[i][j] = C[i][j];
if(C[i][j] == INF)
H[i][j] = -1;
else
H[i][j] = j;
}

Флойда
for(int i = 0; i < n; i++)
for(int

j = 0; j < n; j++)
if(j != i)
for(int k = 0; k < n; k++)
if(k != j)
if(T[j][i]+T[i][k] < T[j][k])
{
H[j][k] = H[j][i];
T[j][k] = T[j][i]+T[i][k];
}

Флойда
1
3
2
5
4
6
7
8
4
4
4
4
3
3
3
3
3
5
Hij
1
2
3
4
5
6
1
2
2
4
4
2
2
1
3
1
1
3
3
6
6
6
6
6
4
1
5
5
5
5
5
2
2
2
2
2
6
8
8
8
8
8
7
4
8
8
4
8
5
5
5
5
8
8
5
5
7
4
1
6
7
2
8
4
3
6
7
8
8
8
8
5
Tij
1
2
3
4
5
6
1
4
8
3
7
11
2
4
4
7
11
7
3
18
14
21
11
3
4
3
7
11
4
14
5
7
3
7
10
10
6
15
11
15
18
8
7
6
10
14
3
8
10
6
10
13
7
17
3
13
7
6
10
24
3
13
8
10
12
8
7
3
21
5
4
16
int Distance(int A, int B)
{
return(T[A-1][B-1]);
}

Флойда
1
3
2
5
4
6
7
8
4
4
4
4
3
3
3
3
3
5
Hij
1
2
3
4
5
6
1
2
2
4
4
2
2
1
3
1
1
3
3
6
6
6
6
6
4
1
5
5
5
5
5
2
2
2
2
2
6
8
8
8
8
8
7
4
8
8
4
8
5
5
5
5
8
8
5
5
7
4
1
6
7
2
8
4
3
6
7
8
8
8
8
5
void Path(int A, int B, int P[], int &N)
{

N = 0;
P[N++] = H[A-1][B-1];
while(P[N-1] != A)
P[N++] = H[A-1][P[N-1]];
}

Дейкстры
Алгоритм Дейкстры (1959 г.) позволяет найти минимальные расстояния от заданной

вершины до всех остальных вершин графа. Граф не должен иметь отрицательных циклов. Применяется в технологиях маршрутизации, например в протоколах OSPF и IS-IS.















0

Дейкстры



3
5

4
0



3
5
7
4
0

Дейкстры
10

8
3
5
7
4
0
10
12
8
3
5
7
4
0

Дейкстры
10
12
8
3
5
7
4
0
10
12
8
3
5
7
4
0