w8grafy alg, studia, Semestr 2, Algorytmy i struktury danych AISD, AIDS

Dr Aleksander Klosow

PWSZ Legnica

Algorytmy i Struktury Danych

Wykład

TEORIA GRAFÓW. ALGORYTMY GRAFOWE.

[1] www.binboy.org

[2] www.algorytm.cad.pl

[3] P.Wróblewski, Algorytmy, struktury danych i techniki programowania

ALGORYTMY GRAFOWE

KLASYFIKACJA WSTĘPNA

OPERACJE NA GRAFACH

-        Suma grafów

-        Kompozycja grafów

-        Potęga grafów

-        Transpozycja grafu

POSZUKIWANIE WIERZCHOŁKA

-        Przeszukiwanie wszerz

-        Przeszukiwanie w głąb

POSZUKIWANIE DROGI

-        Najkrótsze ścieżki z jednym źródłem

-        Najkrótsze ścieżki z całym grafem

INNE

-        Sortowanie topologiczne

-        Sieci przepływowe

PRZESZUKIWANIE GRAFÓW

Przeszukiwanie w głąb (DFS)                                          Przeszukiwanie w wszerz (BFS)

Istnieją dwie taktyki 'chodzenia' po grafie BFS oraz DFS. Algorytmy te mogą być częścią innych algorytmów, n.p. poszukiwanie ścieżek, poszukiwanie wierzchołków, budowanie drzew rozpinających.

PRZESZUKIWANIE GRAFÓW

Przeszukiwanie w wszerz (BFS)

funkcja BreadthFirstSearch (Graf G, Wierzchołek s)

    dla każdego wierzchołka u z G:

        kolor[u] = biały

        odleglosc[u] = inf

        rodzic[u] = NIL

    kolor[s] = SZARY

    odleglosc[s] = 0

    rodzic[s] = NIL

    Q.push(s)

    dopóki kolejka Q nie jest pusta:

        u = Q.pop()

        dla każdego v z listy sąsiedztwa u:

            jeżeli v jest biały:

                kolor[v] = SZARY

                odleglosc[v] = odleglosc[u] + 1

                rodzic[v] = u

                Q.push(v)

        kolor[u] = CZARNY

ZNALEZIENIE DROGI W GRAFIE

Dano graf: macierz sąsiedztwa - zmodyfikowana

Zadanie: znaleźć drogę od wierzchołka A do wierzchołka B

0

1

2

3

4

5

0

1

2

1

2

2

4

3

4

3

5

5

Rozwiązanie:

1)   Przekształcić macierz (wykorzystując domknięcie grafu wg algorytmu Roy-Warszalla)

2)   Wypisać drogę przechodząc po grafie.

ZNALEZIENIE DROGI W GRAFIE, c.d.

Etap 1. Przekształcenie macierzy wejściowej

void Mod(int g[N][N])

{

  int x,y,z;

  for(x=0;x<N;x++)

    for(y=0;y<N;y++)

      if(g[y][x])

              for(z=0;z<N;z++)

                if(g[y][z]==0 && g[x][z]!=0) g[y][z] = g[y][x];

}

0

1

2

3

4

5

0

1

2

2

2

2

1

2

2

2

2

2