Алгоритмы на графах

Представление графа в ЭВМ

Пример

	2
1	4
	3

5	2	0	0	0	1	0	0	0
	6	0	0	1	1	0	0	0
A =		1	1	1	0	1	0	1
	6	1	0	0	1	0	0	0
	6
6		0	0	0	1	0	1	1
	6
	6
7	6	0	0	0	0	1	0	1
	6
	6
	4

Алгоритмы на графах

Представление графа в ЭВМ

Пример

2		5
1		4
		6
	3	7

	2	0	0	0	1	0	0	0	3
	6	0	0	1	1	0	0	0	7
A =		1 1 1 0 1 0 1
	6	1	0	0	1	0	0	0	7
	6								7
	6	0	0	0	1	0	1	1	7
	6								7
	6	0	0	0	0	1	0	1	7
	6								7
	6	0	0	0	1	1	1	0	7
	4								5

Алгоритмы на графах

Представление графа в ЭВМ

Пример

2		5
1		4
		6
	3	7

	2	0	0	0	1	0	0	0	3
	6	0	0	1	1	0	0	0	7
A =		1 1 1 0 1 0 1
	6	1	0	0	1	0	0	0	7
	6								7
	6	0	0	0	1	0	1	1	7
	6								7
	6	0	0	0	0	1	0	1	7
	6								7
	6	0	0	0	1	1	1	0	7
	4								5

Алгоритмы на графах

Представление графа в ЭВМ

Пример

2		5
1		4
		6
	3	7

	2	0	0	0	1	0	0	0	3
	6	0	0	1	1	0	0	0	7
A =		1 1 1 0 1 0 1
	6	1	0	0	1	0	0	0	7
	6								7
	6	0	0	0	1	0	1	1	7
	6								7
	6	0	0	0	0	1	0	1	7
	6								7
	6	0	0	0	1	1	1	0	7
	4								5

Алгоритмы на графах

Представление графа в ЭВМ

Список смежности

Предположим, что задан граф G = (V; E) íà n вершинах.

Алгоритмы на графах

Представление графа в ЭВМ

Список смежности

Предположим, что задан граф G = (V; E) íà n вершинах. Вершины графа занумерованы числами от 1 äî n

Алгоритмы на графах

Представление графа в ЭВМ

Список смежности

Предположим, что задан граф G = (V; E) íà n вершинах. Вершины графа занумерованы числами от 1 äî n Поставим в соответствие каждой вершине i графа связный список L[i],

Алгоритмы на графах

Представление графа в ЭВМ

Список смежности

Предположим, что задан граф G = (V; E) íà n вершинах. Вершины графа занумерованы числами от 1 äî n Поставим в соответствие каждой вершине i графа связный список L[i],

который содержит все вершины, смежные с вершиной i.

i L[i]

2		5
1		4
		6
	3	7

Алгоритмы на графах

Представление графа в ЭВМ

Список смежности

Предположим, что задан граф G = (V; E) íà n вершинах. Вершины графа занумерованы числами от 1 äî n Поставим в соответствие каждой вершине i графа связный список L[i],

который содержит все вершины, смежные с вершиной i.

	2
1	4
	3

	i	L[i]
5	1	3	4

6

7

Алгоритмы на графах

Представление графа в ЭВМ

Список смежности

Предположим, что задан граф G = (V; E) íà n вершинах. Вершины графа занумерованы числами от 1 äî n Поставим в соответствие каждой вершине i графа связный список L[i],

который содержит все вершины, смежные с вершиной i.

	2
1	4
	3

	i	L[i]
5	1	3	4
	2	4

6

7

Алгоритмы на графах