###### tags: `Matematyka Dyskretna M`

# Lista 12

## 2

Stwórzmy tablice V[n][3] (0 index: czy wierzchołek odwiedzony, 1 index: czy należy do pierwszej grupy, 2 index: czy należy do drugiej grupy), wypełnioną początkowo zerami.

Wynik <- 1
grupa <- 1

funkcja DFS(wierzchołek v){

    V[v][grupa] <- 1 // Ustawiam odpowiednią grupę
    Jeżeli grupa == 1: // Zmieniam grupę na przeciwną
        grupa <- 2
    W przeciwnym wypadku:
        grupa <- 1
        
    V[v][0] <- 1 // Zaznaczam jako odwiedzony
    
    Dla każdego sąsiada (wierzchołka v) q: // dla każdego sąsiada
        jeżeli V[q][0] == 0: // Jeżeli nie był odwiedzony to wykonuję DFS(q)
            DFS(q)
        w przeciwnym wpadku: // Jeśli był odwiedzony
            jeżeli V[q][grupa] == 0: // jeżeli nie ma innej grupy (czyli ma tę
            //samą grupę)
                Wynik <- 0 // oznacz wynik jako False

}

Algorytm:

    DFS(1) // sprawdź graf
    Jeżeli wynik == 1 // jeżeli graf jest dwudzielny
        Zwróć True;
    W przeciwnym wypadku
        Zwróć False;

## 3

Utwórzmy kolejkę Q, początkowo jest ona pusta.

Dla każdego wierzchołka sprawdźmy czy ma przychodzącą jakąś krawędź.
Jeśli nie, dodajmy go do kolejki Q.

Stwórzmy listę, która po wykonaniu algorytmu będzie wynikiem, 
początkowo lista jest pusta.

Stwórzmy tablice V[n] oznaczającą odwiedzone wierzchołki,
początkowo tablica jest wypełniona zerami.

funkcja DFS(wierzchołek v){


    V[v] <- 1 // Zaznaczam jako odwiedzony
    
    Dla każdego sąsiada (wierzchołka v) q: // dla każdego sąsiada, do którego
    //wchodzi krawędź od wierzchołka v
        jeżeli V[q] == 0: // Jeżeli nie był odwiedzony to wykonuję DFS(q)
            DFS(q)
        dodaj na początek listy wierzchołek v // Jezeli algorytm skończył 
        //analizować pozostałe wierzchołki i wrzucił już je do listy, wrzuć v 
        //na początek listy. (na ten moment nie licząc wierzchołków wrzuconych
        //do listy, v jest wierzchołkiem, od którego nie wychodzi żadna krawędź)

}

Algorytm:
    Dopóki kolejka Q nie jest pusta:
        ściągnij element z kolejki i nazwij go a
        DFS(a)

## 4

Na podstawie algorytmu Kruskala:


Na podstawie algorytmu Prima–Dijkstry:
Na początku wybrałem ZOO

## 5

Dw. Główny:

pl. Grunwaldzki:

Browar:

## 7

Weźmy zbiór krawędzi, posortujmy je malejąco i wrzućmy je do zbioru E.
Stwórzmy las L, w którym każdy wierzchołek jest drzewem.
Dopóki E jest niepuste i L nie jest drzewem:
$\quad$ Weź i usuń pierwszą krawędź ze zbioru E (największa w zbiorze E). Nazwijmy ją $E_0$
$\quad$ Jeżeli $E_0$ połączyłaby dwa różne drzewa w jedno to dodaj $E_0$ do L.

Po zakończeniu algorytmu L jest najdłuższym drzewem rozpinającym.

## 8

Dla każdego i od 0 do 31 włącznie:
$\quad$ Dla każdego j od 0 do 31 włączenie:
$\quad$$\quad$ Jeżeli $F[j]\space \& \space(1<<i)$: // Jeżeli w grafie znajduje się krawędź j,i.
$\quad$$\quad$$\quad$ $F[j]= F[i] \space | \space F[j]$ // Uzupełnij listę sąsiadów wierzchołka j o sąsiadów wierzchołka i

Algorytm sprawdza czy istnieje bezpośrednie połączenie krawędzią między dwoma wierzchołkami $j,i$ po czym jeżeli taka krawędź istnieje, to łączy wierzchołek $j$ ze wszystkimi sąsiadami wierzchołka $i$.
<br /><br /><br /><br /><br /><br /><br /><br /><br />
## 9

Algorytm:
Stwórzmy tablicę dist[n][n], w której będziemy przechowywać najkrótsze ścieżki
między wszystkimi wierzchołkami, początkowo, w każdej komórce znajduje się 
nieskończoność.

Stwórzmy tablicę prev[n][n], w której będziemy przechowywać przedostatnie 
wierzchołki każdej ścieżki, aby można było wyznaczyć na podstawie ich 
poszczególne najkrótsze ścieżki. Początkowo tablica ta jest wypełniona 
wartością NULL (niezdefiniowana wartość).

Funkcja weight(i,j) zwraca wagę krawędzi i,j.

Dla każdej krawędzi i,j:
    prev[i][j] = i // dla każdej krawędzi i,j przedostattni wierzchołek
    //ustawiamy początkowo na i
    dist[i][j] = weight(i,j); // najkrótsza ścieżka połączonych wierzchołków 
    //początkowo wynosi tyle co waga ich krawędzi
    
Dla każdego wierzchołka v:
    Dla każdego wierzchołka w:
        Dla każdego wierzchołka u:
            jeżeli dist[w][u] > dist[w][v] + dist[v][u]:
                dist[w][u] = dist[w][v] + dist[v][u]
                prev[w][u] = prev[v][u] // zapamiętujemy za każdym razem 
                //przedostatni element.

Jeżeli chcemy wziąc drogę z wierzchołka u do v, to wystarczy sprawdzać po kolei wartości prev w tablicy. Ostatnim elementem jest v, potem $prev[u][v]$, potem $prev[u][prev[v]]$ i tak dalej dopóki nie dostaniemy wierzchołka, który jest równy początkowi ścieżki.