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

Алгоритмы на графах: поиск в ширину и в глубину

Составитель: Вирченко Н. И.

Где можно использовать алгоритмы?

• Олимпиадное программирование
• В 9 классе при изучении темы «Графические информационные модели»
• В 10 классе при изучении темы «Двумерный массив»
• В 11 классе при изучении темы «Программирование»

Основные сведения о графах

• Так или иначе, каждый человек в своей жизни, сам не подозревая об этом, встречался с теорией графов: либо, прокладывая маршрут путешествия, либо на предметных олимпиадах, либо в материалах учебников по географии, химии, физике, либо даже в аэропорту, изучая карту полетов самолета.
• Теория графов применяется в таких областях, как физика, химия, проектирование вычислительных машин, электротехника, машиностроение, архитектура, генетика, психология, социология, экономика и лингвистика .

Основные сведения о графах

• Граф  — это конечное множество точек, называемых  вершинами , и линий, соединяющих некоторые из вершин, называемых  ребрами  или дугами в зависимости от вида графа.

Задача

Друзья (40 баллов)

Петя и Вася поехали в пионерский лагерь, а ездят они в лагерь не первый год. И оказывается, чем больше ездишь, тем больше друзей заводишь, потому что у твоих друзей есть друзья, которые в свою очередь становятся твоими друзьями. И Вася решил написать программу, которая может определить количество друзей у конкретного человека в отряде и просит тебя помочь ему.

Вася сформулировал задачу так: В отряде N человек. Многие из них – друзья. Так же известно, что друзья друзей так же являются друзьями. Требуется выяснить, сколько всего друзей у конкретного человека в отряде. Задание. Помогите Васе написать программу, которая будет выдавать количество друзей у заданного по номеру S человека из отряда, в котором N человек.

Входные данные Выходные данные

3 1 2

0 1 0

1 0 1

0 1 0

Обход графа в глубину DFS

Стартовая вершина 0

Обход - 1, 2, 3, 4, 5

Назад – в 4

Обход – 6

Назад – в 4, 3

Обход – 7, 8

Назад – в 7

Обход - 9, 10, 11

Назад – в 10

Обход – 12, 13

Назад – в 12

Обход – 14, 15

Назад – в 14

Обход – 16

Назад – в 14, 12,10, 9, 7, 3, 2

Обход – 17

Назад – в 2, 1, 0

Обход – 18

Назад – в 0

18

5

1

2

4

0

3

6

15

17

7

14

8

12

9

16

10

13

11

Обход графа в глубину DFS

18

5

1

2

4

0

3

6

15

17

7

14

8

9

12

16

10

13

11

Ввод графа в программе

Задаем граф с помощью двумерного массива

G:array [1..10,1..10] of integer;

Вводим двумерный массив

for i:=1 to n do

for j:=1 to n do

read(G[i,j]);

var n,i,j,start,count:integer;

G:array [1..10,1..10] of integer;

flag:array [1..10] of integer;

procedure DFS(x:integer);

var r:integer;

begin

flag[x]:= 1;

for r:=1 to n do

if (G[x,r]0) and ( flag[r]=0) then

begin

inc(count);

DFS(r);

end;

end;

begin

count:=0;

Read(n,start);

for i:=1 to n do

for j:=1 to n do

read(G[i,j]);

DFS(start);

writeln(count);

end.

Программа на Pascal

Обход графа в ширину BFS

4

6

7

2

10

5

1

13

0

12

11

8

9

14

3

Стартовая вершина 0

1-й ход: 1, 10, 11, 12

2-й ход: 7, 4, 6, 3, 9, 14,8

3-й ход: 13, 2, 5

Обход графа в ширину BFS

4

6

7

2

10

5

1

13

0

12

11

8

9

14

3

const N=5;

var start,r,i,j,count,head:integer;

G:array [1..N,1..N] of integer; ochered, flag:array[1..N] of integer;

begin

for i:=1 to N do

for j:=1 to N do

read(G[i,j]);

read(start);

count:=1;

flag[start]:=1;

ochered[1]:=start;

head:=0; r:=1;

while headcount do

begin

inc(head);

writeln('- ',ochered[head]);

for i:=1 to N do

if (G[ochered[head],i]0)and(flag[i]=0) then

begin

inc(count);

ochered[count]:=i;

flag[i]:=1;

end;

for i:=1 to n do

if flag[i]=0 then begin inc(r); break; end;

end;

write('waves=',r);

end.

Подготовка к олимпиаде

https://informatics.msk.ru/