Algorytmy i struktury danych

Przeszukiwanie DFS, sortowanie

topologiczne

Mariusz Gł ˛

abowski

Instytut Elektroniki i Telekomunikacji

Politechnika Pozna ´nska

17 pa´zdziernika 2003

dr in˙z. Mariusz Gł ˛

abowski

Przeszukiwanie w gł ˛

ab

•

Algorytm przeszukiwania wszerz grafu jest znany tak˙ze jako DFS –
Depth-First Search

•

W czasie przeszukiwania w gł ˛

ab zagł ˛ebiamy si ˛e tak daleko, jak tylko

jest to mo˙zliwe, zanim zajrzymy do innych wierzchołków s ˛

asiednich

•

W algorytmie DFS wierzchołkom przypisuje si ˛e etykiety czasowe

?

d

[

v

]

: numer kroku oblicze ´n, w którym wierzchołek

v

jest odwie-

dzony po raz pierwszy

?

f

[

v

]

: numer kroku w przeszukiwaniu, w którym ko ´nczy si ˛e badanie

listy s ˛

asiedztwa wierzchołka

v

•

DFS tworzy las przeszukiwania w gł ˛

ab zło˙zony z jednego lub wi ˛e-

cej drzew przeszukiwania w gł ˛

ab

dr in˙z. Mariusz Gł ˛

abowski

Wykład 5 – Przeszukiwanie DFS, sortowanie topologiczne

1

Przeszukiwanie w gł ˛

ab

•

Kolorowanie wierzchołków:

?

biały : wierzchołek nie odwiedzony

?

szary : wierzchołek, który został odwiedzony, ale nie wszystkie
jego kraw ˛edzie zostały zbadane

?

czarny : wierzchołek , który jest przetworzony, tzn. gdy jego lista
s ˛

asiedztwa zostaje całkowicie zbadana

•

Kolorowanie zapewnia, ˙ze ka˙zdy wierzchołek b ˛edzie nale˙zał do do-
kładnie jednego drzewa przeszukiwania w gł ˛

ab



  

 

  

     

 


dr in˙z. Mariusz Gł ˛

abowski

Wykład 5 – Przeszukiwanie DFS, sortowanie topologiczne

2

Przeszukiwanie w gł ˛

ab

•

DFS

(

G

)

1:

for ka˙zdy wierzchołek

u

∈

V

[

G

]

do

2:

color

[

u

] ←

biay

3:

π

[

u

] ←

NIL

4:

end for

5:

time

←

0

6:

for ka˙zdy wierzchołek

u

∈

V

[

G

]

do

7:

if

color

[

u

] =

biay

then

8:

DFS

−

V ISIT

(

u

)

9:

end if

10:

end for

dr in˙z. Mariusz Gł ˛

abowski

Wykład 5 – Przeszukiwanie DFS, sortowanie topologiczne

3

Przeszukiwanie w gł ˛

ab

•

DFS

−

V ISIT

(

u

)

1:

color

[

u

] ←

szary

2:

/

∗

biały wierzchołek

u

został wła´snie odwiedzony

∗

/

3:

d

[

u

] ←

time

←

time

+

1

4:

for ka˙zdy

v

∈

Adj

[

u

]

do

5:

/

∗

zbadaj kraw ˛ed´z

(

u, v

) ∗

/

6:

if

color

[

v

] =

biay

then

7:

π

[

v

] ←

u

8:

DFS

−

V ISIT

(

v

)

9:

end if

10:

end for

11:

color

[

u

] ←

czarny

/

∗

u

na czarno - został przetworzony

∗

/

12:

f

[

u

] ←

time

←

time

+

1

dr in˙z. Mariusz Gł ˛

abowski

Wykład 5 – Przeszukiwanie DFS, sortowanie topologiczne

4

Przeszukiwanie DFS - przykład działania

1/

v

u

w

z

y

x

1/

2/

v

u

w

z

y

x

1/

2/

3/

v

u

w

z

y

x

1/

2/

4/

3/

v

u

w

z

y

x

1/

2/

4/

3/

v

u

w

z

y

x

1/

2/

4/5

3/

v

u

w

z

y

x

1/

2/

4/5

3/6

v

u

w

z

y

x

1/

2/7

4/5

3/6

v

u

w

z

y

x

1/

2/7

4/5

3/6

v

u

w

z

y

x



dr in˙z. Mariusz Gł ˛

abowski

Wykład 5 – Przeszukiwanie DFS, sortowanie topologiczne

5

Przeszukiwanie DFS - przykład działania

1/8

2/7

4/5

3/6

v

u

w

z

y

x



1/8

2/7

4/5

3/6

9/

v

u

w

z

y

x



1/8

2/7

4/5

3/6

9/

v

u

w

z

y

x





1/8

2/7

4/5

3/6

9/

10/

v

u

w

z

y

x





1/8

2/7

4/5

3/6

9/

10/

v

u

w

z

y

x





1/8

2/7

4/5

3/6

9/

10/11

v

u

w

z

y

x





1/8

2/7

4/5

3/6

9/12

10/11

v

u

w

z

y

x





Zło˙zono´s´c czasowa

O

(

V

+

E

)

dr in˙z. Mariusz Gł ˛

abowski

Wykład 5 – Przeszukiwanie DFS, sortowanie topologiczne

6

Algorytm DFS - klasyfikacja kraw ˛edzi

•

Kraw ˛edzie drzewowe: kraw ˛edzie w lesie przeszukiwania w gł ˛

ab

G

π

; kraw ˛ed´z

(

u, v

)

jest kraw ˛edzi ˛

a drzewow ˛

a, je´sli wierzchołek

v

zo-

stał odwiedzony w wyniku zbadania kraw ˛edziami

(

u, v

)

.

•

Kraw ˛edzie powrotne: kraw ˛edzie

(

u, v

)

, ł ˛

acz ˛

ace wierzchołek

u

z

jego przodkiem

v

w drzewie przeszukiwania w gł ˛

ab. P˛etle s ˛

a trakto-

wane jako kraw ˛edzie powrotne.

•

Kraw ˛edzie w przód: kraw ˛edzie niedrzewowe

(

u, v

)

, które ł ˛

acz ˛

a

wierzchołek

u

z jego potomkiem

v

w drzewie przeszukiwania w gł ˛

ab.

•

Kraw ˛edzie poprzeczne: wszystkie inne kraw ˛edzie. Ł ˛

acz ˛

a one

wierzchołki z tego samego drzewa przeszukiwania w gł ˛

ab, je˙zeli

tylko jeden z wierzchołków nie jest przodkiem drugiego, lub ł ˛

acz ˛

a

wierzchołki z ró˙znych drzew przeszukiwania w gł ˛

ab.

dr in˙z. Mariusz Gł ˛

abowski

Wykład 5 – Przeszukiwanie DFS, sortowanie topologiczne

7

Własno ´sci algorytmu DFS

3/6

2/9

4/5

7/8

1/10

12/13

z

y

s

v

w

x

11/16

14/15

u

t

T

B

C

F

y

z

x

w

s

v

t

u

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16

x

w

y

z

s

t

u

v

dr in˙z. Mariusz Gł ˛

abowski

Wykład 5 – Przeszukiwanie DFS, sortowanie topologiczne

8

Algorytm DFS - sposób klasyfikacji kraw ˛edzi

•

Ka˙zda kraw ˛ed´z

(

u, v

)

, gdy jest badana po raz pierwszy, mo˙ze zo-

sta´c sklsyfikowana za pomoc ˛

a koloru wierzchołka

v

, do którego pro-

wadzi

(

u, v

)

jest























kraw ˛edzi ˛

a drzewow ˛

a

je˙zeli

v

jest białe

kraw ˛edzi ˛

a powrotn ˛

a

je˙zeli

v

jest szare

kraw ˛edzi ˛

a w przód

je˙zeli

v

jest czarne i

d

[

u

] <

d

[

v

]

kraw ˛edzi ˛

a poprzeczn ˛

a

je˙zeli

v

jest czarne i

d

[

u

] >

d

[

v

]

Twierdzenie 1. W przeszukiwaniu w gł ˛

ab grafu nieskierowanego

G

ka˙zda kraw ˛ed´z jest albo kraw ˛edzi ˛

a drzewow ˛

a, albo kraw ˛edzi ˛

a po-

wrotn ˛

a

dr in˙z. Mariusz Gł ˛

abowski

Wykład 5 – Przeszukiwanie DFS, sortowanie topologiczne

9

Sortowanie topologiczne

•

Sortowanie topologiczne dagu

G

= (

V, E

)

jest liniowym uporz ˛

ad-

kowaniem wszystkich jego wierzchołków w taki sposób, ˙ze je˙zeli
graf

G

zawiera kraw ˛ed´z

(

u, v

)

, to w tym porz ˛

adku wierzchołek

u

wyst ˛epuje przed wierzchołkiem

v

.

•

Je˙zeli graf nie jest acykliczny, to takie uporz ˛

adkowanie nie jest mo˙z-

liwe.

•

Zastosowania: okre´slenie kolejno´sci wykonywanych czynno´sci.

•

Do sortowania topologiczneg dagów mo˙ze by´c u˙zyte sortowanie w
gł ˛

ab.

dr in˙z. Mariusz Gł ˛

abowski

Wykład 5 – Przeszukiwanie DFS, sortowanie topologiczne

10

Sortowanie topologiczne



   

  

    

    

       

    

   

    

11/16

12/15

6/7

1/8

2/5

3/4

13/14

17/18

9/10



   

  

    

    

       

    

   

    

11/16

12/15

6/7

1/8

2/5

3/4

13/14

17/18

9/10

dr in˙z. Mariusz Gł ˛

abowski

Wykład 5 – Przeszukiwanie DFS, sortowanie topologiczne

11

Algorytm sortowania topologicznego

•

Topological

−

Sort

(

G

)

1. Wykonaj

DFS

(

G

)

w celu obliczenia czasów przetworzenia

f

[

v

]

dla wszystkich wierzchołków

v

2. Wstaw ka˙zdy wierzchołek

v

na pocz ˛

atek listy, kiedy tylko zostanie

przetworzony

3. return lista wierzchołków

•

Analiza czasowa

Θ

(

V

+

E

)

dr in˙z. Mariusz Gł ˛

abowski

Wykład 5 – Przeszukiwanie DFS, sortowanie topologiczne

12