Strona główna

Z 90 min adanie2 5


Pobieranie 48.5 Kb.
Data18.06.2016
Rozmiar48.5 Kb.

Grafy - algorytmy przejścia grafu w głąb i wszerz autor: Janusz Białowąs

Z
90 min.
adanie2_5


Grafy – algorytmy przejścia grafu

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

OPIS ZADANIA

Uzupełnij aplikację o następujące procedury:

- odczytanie z pliku tekstowego połączeń pomiędzy wierzchołkami grafu oraz ilości wierzchołków i utworzenie list sąsiedztwa dla poszczególnych wierzchołków. Zakładamy, że w pierwszym wierszu pliku znajduje się ilość wierzchołków, a w kolejnych wierszach 2 liczby, wskazujące połączone ze sobą wierzchołki grafu,

- przejście grafu w głąb (algorytm DFS),

- przejście grafu wszerz (algorytm BFS).

UWAGA: zakładamy, że graf jest grafem skierowanym.

Celem zadania jest nabycie umiejętności wykonywania podstawowych działań na grafach, czyli tworzenie list sąsiedztwa oraz sposobu odwiedzania wszystkich wierzchołków grafu.

EFEKT KOŃCOWY

Wykonując to zadanie, poznasz podstawowe algorytmy związane z grafami oraz nauczysz się je implementować w Visual Basic z wykorzystaniem klas Stack i Queue.



- Aby wykonać to zadanie, niezbędne jest wykorzystanie przygotowanego projektu: Program_2_5\DFS i BFS.sln

REALIZACJA ZADANIA

Wykonując to zadanie, poznasz i wykorzystasz w praktyce algorytmy przechodzenia grafu. Podczas pisania programu skoncentruj się na praktycznej implementacji algorytmów oraz wykorzystaniu klas Stack i Queue.

Krok 1: Tworzenie procedury odczytującej dane z pliku i tworzącej listy sąsiedztwa


  1. Otwórz projekt o nazwie BFS i DFS.sln z folderu wskazanego przez nauczyciela.

  2. Utwórz w folderze rozwiązania plik graf.txt o przykładowej zawartości.

    6

    1 2



    1 3

    2 4


    2 5

    4 5


    5 1

    3 5


    3 6

  3. Zadeklaruj zmienne globalne na początku kodu aplikacji – tablicę Listy_s typu Queue do przechowywania list sąsiedztwa oraz zmienną ileWierzcholkow.

Dim Listy_s() As Queue

Dim ileWierzcholkow As Integer



  1. Utwórz procedurę o nazwie odczyt_z _pliku.

Sub odczyt_z_pliku()

End Sub


  1. Zadeklaruj zmienne potrzebne w procedurze.

Dim nrPliku As Integer

Dim wierzcholki() As String

Dim wiersz As String

Dim i As Integer

Dim w1, w2 As Integer

Dim listy_kopia() As Queue



  1. Otwórz plik w trybie do odczytu.

nrPliku = FreeFile()

FileOpen(nrPliku, "..\graf.txt", OpenMode.Input)



  1. Odczytaj ilość wierzchołków z pliku i zmień rozmiar tablic Listy_s i listy_kopia.

ileWierzcholkow = LineInput(nrPliku)

ReDim Listy_s(ileWierzcholkow)

ReDim listy_kopia(ileWierzcholkow)


  1. Zainicjuj wszystkie elementy (kolejki Queue) w tablicach Listy_s i listy_kopia.

For i = 1 To ileWierzcholkow

Listy_s(i) = New Queue()

listy_kopia(i) = New Queue()

Next


  1. Rozpocznij odczyt danych z pliku (numerów sąsiadujących wierzchołków).

Do While Not EOF(nrPliku)

wiersz = LineInput(nrPliku)



  1. Za pomocą metody Split rozdziel cyfry umieszczone w jednym wierszu i umieść je w tablicy o nazwie wierzcholki.

wierzcholki = wiersz.Split(" ", Chr(13))

  1. Utwórz listy sąsiedztwa w tablicy Listy_s. Wiersz w komentarzu stosujemy wraz z poprzedzającą linijką kodu w przypadku, gdy graf jest nieskierowany.

Listy_s(CInt(wierzcholki(0))).Enqueue(CInt(wierzcholki(1)))

'Listy_s(CInt(wierzcholki(1))).Push(CInt(wierzcholki(0)))

Loop


  1. Zamknij plik i wyczyść pole tekstowe.

FileClose(nrPliku)

txtlisty_s.Clear()



  1. Wyświetl pole tekstowe przeznaczone do pokazania list sąsiedztwa.

txtlisty_s.Visible = True

  1. Wyświetl w polu tekstowym listy sąsiedztwa dla wczytanego grafu, operując na kopii tablicy Listy_s
    o nazwie listy_kopia.

For i = 1 To ileWierzcholkow

listy_kopia(i) = Listy_s(i).Clone

txtlisty_s.Text = txtlisty_s.Text & " wierzchołek (" & i & ") = "

Do While listy_kopia(i).Count <> 0

txtlisty_s.Text = txtlisty_s.Text & listy_kopia(i).Dequeue & " "

Loop


txtlisty_s.Text = txtlisty_s.Text & vbCrLf

Next


  1. Uaktywnij i wyświetl pozostałe kontrolki w formularzu.

btnPrzejdzWGlab.Enabled = True

btnPrzejdzWSzerz.Enabled = True

txtPrzejscieWGlab.Visible = True

txtPrzejscieWSzerz.Visible = True



  1. Wywołaj procedurę odczyt_z_pliku w procedurze zdarzenia związanej z przyciskiem Odczyt z pliku

Private Sub btnOdczyt_Click(ByVal sender As System.Object, ByVal e As System.EventArgs) Handles btnOdczyt.Click

odczyt_z_pliku()

End Sub

Krok 2: Przechodzenie przez graf w głąb (DFS)


  1. Kliknij dwukrotnie przycisk Przejdź graf w głąb, aby przejść do edytora kodu i procedury zdarzenia dla tej kontrolki.

Private Sub btnPrzejdzWGlab_Click(ByVal sender As System.Object, ByVal e As System.EventArgs) Handles btnPrzejdzWGlab.Click

End Sub


  1. Zadeklaruj zmienne lokalne w tej procedurze

Dim i, v, w As Integer

Dim odwiedzone(ileWierzcholkow) As Boolean

Dim biezacy As Integer

Dim listy_kopia() As Queue

Dim p As Integer

Dim stos As Stack



  1. Zmień rozmiar tablicy listy_kopia wg ilości wierzchołków grafu i wyczyść pole tekstowe.

ReDim listy_kopia(ileWierzcholkow)

txtPrzejscieWGlab.Text = ""



  1. Wyczyść tablicę odwiedzone (ustaw wartość wszystkich jej elementów na False) oraz zainicjuj elementy tablicy listy_kopia (czyli kolejki) i przepisz do nich listy sąsiedztwa z tablicy Listy_s.

For i = 1 To ileWierzcholkow

odwiedzone(i) = False

listy_kopia(i) = New Queue()

listy_kopia(i) = Listy_s(i).Clone

Next


  1. Ustaw numer wierzchołka, od którego rozpocznie się przechodzenie przez graf i zaznacz go jako odwiedzony.

p = 1

odwiedzone(p) = True



  1. Sprawdź, czy są elementy na liście sąsiedztwa dla podanego wierzchołka. Jeżeli są, utwórz stos, na którym będą zapamiętane wierzchołki do sprawdzenia i wpisz do niego pierwszy wierzchołek.

If listy_kopia(p).Count <> 0 Then

stos = New Stack()

stos.Push(p)


  1. Wyświetl w polu tekstowym wierzchołek, od którego rozpoczynamy przechodzenie grafu.

txtPrzejscieWGlab.Text = txtPrzejscieWGlab.Text & " " & p

  1. Dopóki na stosie o nazwie stosjeszcze elementy, sprawdzaj kolejne wierzchołki oraz wyświetlaj te, które były odwiedzone.

Do While stos.Count <> 0

v = stos.Peek

w = listy_kopia(v).Dequeue

If listy_kopia(v).Count = 0 Then

stos.Pop()

End If


If Not odwiedzone(w) Then

odwiedzone(w) = True

txtPrzejscieWGlab.Text = txtPrzejscieWGlab.Text & " " & w

If listy_kopia(w).Count <> 0 Then

stos.Push(w)

End If


End If

Loop


End If

Krok 3: Przechodzenie przez graf wszerz (BFS)

  1. Kliknij dwukrotnie przycisk Przejdź graf wszerz, aby przejść do edytora kodu i procedury zdarzenia dla tej kontrolki

Private Sub btnPrzejdzWSzerz_Click(ByVal sender As System.Object, ByVal e As System.EventArgs) Handles btnPrzejdzWSzerz.Click

End Sub


  1. Wpisz kod procedury - wygląda tak samo, tylko lista wierzchołków do sprawdzenia jest przechowywana w kolejce, a nie na stosie jak w algorytmie DFS. Kod procedury powinien wyglądać następująco:

Dim i, v, w As Integer

Dim odwiedzone(ileWierzcholkow) As Boolean

Dim biezacy As Integer

Dim listy_kopia() As Queue

Dim p As Integer

Dim kolejka As Queue

ReDim listy_kopia(ileWierzcholkow)

txtPrzejscieWSzerz.Text = ""

For i = 1 To ileWierzcholkow

odwiedzone(i) = False

listy_kopia(i) = New Queue()

listy_kopia(i) = Listy_s(i).Clone

Next

p = 1


odwiedzone(p) = True

If listy_kopia(p).Count <> 0 Then

kolejka = New Queue()

kolejka.Enqueue(p)

txtPrzejscieWSzerz.Text = txtPrzejscieWSzerz.Text & " " & p

Do While kolejka.Count <> 0

v = kolejka.Peek

w = listy_kopia(v).Dequeue

If listy_kopia(v).Count = 0 Then

kolejka.Dequeue()

End If

If Not odwiedzone(w) Then



odwiedzone(w) = True

txtPrzejscieWSzerz.Text = txtPrzejscieWSzerz.Text & " " & w

If listy_kopia(w).Count <> 0 Then

kolejka.Enqueue(w)

End If

End If


Loop

End If


Krok 4: Testowanie aplikacji

  1. Uruchom aplikację.

  2. Sprawdź działanie poszczególnych przycisków.

  3. Narysuj na kartce papieru, jak powinien wyglądać graf odczytywany z pliku i sprawdź poprawność działania procedur.

  4. Zmień graf, modyfikując dane w pliku i sprawdź działanie aplikacji.




Algorytmika i programowanie


©snauka.pl 2016
wyślij wiadomość