Глава 2.Ненаправленные графы, часть 1. Простые графы (графы) Способы задания графа Основные способы задания графов графический

• Название: Простые графы (графы) Способы задания графа Основные способы задания графов графический
• Анкор: Глава 2.Ненаправленные графы, часть 1.doc
• Дата: 04.09.2018
• Размер: 1.28 Mb.
• Имя файла: Глава 2.Ненаправленные графы, часть 1.doc
• Тип: Глава; #24055
• страница: 13 из 14

2.8.2. Обход в ширину (BFS)

Определения

Обход в ширину является алгоритмом систематического пошагового посещения (обхода) всех смежных вершин по отношению к текущим вершинам (вершине).

О

Пример

бход и разметка вершин графа осуществлятся в следующем порядке: началу обхода S приписывается метка 0, смежным с ней вершинам – метка 1. Теперь поочередно рассматриваются окружения всех вершин с метками 1 и каждой из входящих в эти окружения еще не занумерованных вершин приписывается метка 2 и т.д.


1● S

●3S

●4

6●

5●

2●

●

7

● 8

Ширина (метка)-0


●S


3

●

● 2

4●

Ширина (метка)-1


● 5




Ширина (метка)-2


● 6


●

8

● 7

Ширина (метка)-3




Рис.2.8.1. Идея BFS

Атрибуты DFS

Пять основных атрибута алгоритма BFS:

1) начальная вершина S;

2) цвет вершины u – цвет[u]:

• 
  белый, если вершина непросмотрена;
  
• 
  серый, если вершина найдена и просмотрена;
  
• 
  черный, если вершина завершена.
  

3) d[u] – кратчайшее расстояние от вершины u до начальной вершины S, с которой начинается выполнение алгоритма. Расстояние определяется числом ребер между вершинами.

4) p[v] – предшественник вершины u в BFS дереве;

5) регулярная очередь Q.

Псевдокод

{Для каждой вершины u делать:

d[u]= ∞ ;

цвет[u]=белый;

p[u]=NIL;

цвет[S]=серый;

включить S в очередь Q;

{ До тех всех соседей v вершины u делать:

если цвет[v]=белый, тогда

цвет[v]=серый;

d[v]=d[u]+1;

p[v]=u;

включить вершину v d очередь Q;

цвет[u]=черный; }}}

Класс сложности

Сложность адгоритма BFS – O(n+m), где n=|V|, m=|E|, т.е.проблема относится к P классу.

Пример

r

s

--

v

s

w

r

--


u

r

s

t


t

u

w

x

--


u

--

y

t


y

x

w

v


v

--

r


w

x

--

t

s

x

t

--

y

w


y

--

x

u

∞

v



u

∞

s

0

t

∞



∞

y





∞

x





∞

w



r

1



∞

v



u

∞

s

0

t

∞



∞

y





∞

x





1

w



d[s]=0; d[w]=1;d[r]=1

Q

w

r

r

1



∞

v



u

∞

s

0

t

2



∞

y





2

x





1

w



d[t]=2,d[x]=2

Q

r

t

x

r

1



2

v



u

∞

s

0

t

2



∞

y





2

x





1

w



d[v]=2

Q

t

x

v

N


Рисунок графа

Описание действий алгоритма


1

В очередь помещается начальная вершина s. Вершина s – серая (на рисунке и в таблице инцидентности).

d[s]=0;

d[f_i]=∞ от s до всех остальных вершин

(расстояния показаны рядом с вершинами и в рамке под рисунком)


r

∞









s

Q

d[s]=0




2

Очередь Q: из таблицы инцидентности для вершины s выбираются смежные вершины r, w и помещаются в очередь.

Вершина s – черная (на рисунке и таблице инциденции), из очереди изымается.

Вершины r и w – серые (на рисунке и в таблице).

d[w]=1; d[s]=1;



3

Очередь Q: из таблицы инцидентности для вершины w выбираются смежные вершины t,x.

Вершина w – черная.

Вершины t и x – серые.

d[t]=2, d[x]=2




4


Очередь Q: из таблицы инцидентности для вершины r выбирается смежная вершина v.

Вершина r – черная.

Вершина v – серая.

d[v]=2




r

1



2

v



u

3

s

0

t

2



3

y





2

x





1

w



d[y]=3

Q

x

v

u

u

3

r

1



2

v



s

0

t

2



3

y





2

x





1

w




Q

u

y

u

3

r

1



2

v



s

0

t

2



3

y





2

x





1

w




Q

y

N


Рисунок графа

Описание действий алгоритма



5

Очередь Q: из таблицы инцидентности для вершины t : w –черная, x – серая, u – белая. Добавляем вершину u.

Вершина t – черная.

Вершина u – серая.

d[u]=3


r

1

u

3

s

0

t

2






2

v

∞

y

2

x

1

w