Поиск в графе 2

Задача поиска в графе	Поиск в глубину

Пример работы алгоритма

1) v1 v1		2)	v1
				v2
		v2		v1

		v1
3)	v2	v3
	v3	v2
		v1

4)

v1

5)

v1

6)

v2

v1

v2

v2

v4

v3

v3

v3

v3

v3

v2

v2

v2

v4

v4

v4

v1

v1

v1

Расин О.В.	Поиск в графе

Задача поиска в графе	Поиск в глубину

Пример работы алгоритма

	v1
	7)
	v2		v5
	v3	v5	v2
			v1
	v4

Расин О.В.	Поиск в графе

Задача поиска в графе	Поиск в глубину

Пример работы алгоритма

7)v1

	v2		v5
	v3	v5	v2
			v1
	v4

v1
8)		v
v2
		v6
v3	v5	v25
		v1
v4
		v6

Расин О.В.	Поиск в графе

Задача поиска в графе	Поиск в глубину

Пример работы алгоритма

7)v1

	v2		v5
	v3	v5	v2
			v1
	v4

v1
8)		v
v2
		v6
v3	v5	v25
		v1
v4
		v6

9)v1

v2		v
v3	v5	v25
		v1
v4
		v6

Расин О.В.	Поиск в графе

Задача поиска в графе	Поиск в глубину

Пример работы алгоритма

7)v1

	v2		v5
	v3	v5	v2
			v1
	v4

v1
8)		v
v2
		v6
v3	v5	v25
		v1
v4
		v6

9)v1

v2		v
v3	v5	v25
		v1
v4
		v6

10)v1

	v2	v5	v2
	v3
			v1
	v4
			v6

Расин О.В.	Поиск в графе

Задача поиска в графе	Поиск в глубину

Пример работы алгоритма

7)v1

	v2		v5
	v3	v5	v2
			v1
	v4

v1
8)		v
v2
		v6
v3	v5	v25
		v1
v4
		v6

9)v1

v2		v
v3	v5	v25
		v1
v4
		v6

10)v1

	v2	v5	v2
	v3
			v1
	v4
			v6

Расин О.В.	Поиск в графе

Задача поиска в графе	Поиск в глубину

Пример работы алгоритма

	v1
	11)
	v2	v5
	v3
		v1
	v4
		v6

Расин О.В.	Поиск в графе

	Задача поиска в графе		Поиск в глубину
Пример работы алгоритма
v1			v1
11)			12)		v7
v2	v5		v2	v5
v3			v3		v7
	v1				v1
v4			v4
	v6				v6

Расин О.В.	Поиск в графе

Задача поиска в графе

Пример работы алгоритма

v1
11)
v2	v5
v3			v1
v4		v6
v1
13)		v7
v2			v8
	v5
v3		v	v7
			v1
v4		8
		v6

Поиск в глубину

v1
12)		v7
v2	v5
v3		v7
		v1
v4
		v6

Расин О.В.	Поиск в графе

Задача поиска в графе

Пример работы алгоритма

v1
11)
v2	v5
v3			v1
v4		v6
v1
13)		v7
v2			v8
	v5
v3		v	v7
			v1
v4		8
		v6

Поиск в глубину

v1
12)		v7
v2	v5				v7
v3
					v1
v4		v6
v1
14)		v7
v2					v8
	v5
v3			v		v7
					v1
		8
v4		v	6

Расин О.В.	Поиск в графе