2025/2025

Laboratorium 3 - Zadanie 1 #

Kod początkowy #

Graphs

Wprowadzenie do Grafów #

Graf to struktura danych, która składa się ze zbioru wierzchołków oraz zbioru krawędzi, które łączą pary wierzchołków. Grafy są używane do modelowania relacji między obiektami i są szeroko stosowane w różnych dziedzinach, takich jak sieci społecznościowe, systemy map i nawigacji, sieci komputerowe i inne.

Istnieje kilka sposobów reprezentacji grafu w pamięci. Dwie najczęstsze reprezentacje to:

  1. Macierz sąsiedztwa: Dwuwymiarowa tablica, w której wpis macierz[i][j] ma wartość 1 lub true, jeśli istnieje krawędź od wierzchołka i do wierzchołka j, a 0 lub false w przeciwnym razie. Ta reprezentacja jest wydajna do sprawdzania, czy istnieje krawędź między dwoma wierzchołkami, ale może zużywać dużo pamięci dla grafów rzadkich (grafów z małą liczbą krawędzi).

  2. Lista sąsiedztwa: Tablica list, w której lista o indeksie i zawiera wszystkie wierzchołki sąsiadujące z wierzchołkiem i. Ta reprezentacja jest bardziej oszczędna pamięciowo dla grafów rzadkich, ponieważ przechowuje tylko istniejące krawędzie.

W tym laboratorium zaimplementujesz obie te reprezentacje.

Wymagania ogólne #

Celem tego laboratorium jest zaimplementowanie struktury danych grafu skierowanego oraz algorytmu przeszukiwania w głąb (DFS). Wszystkie klasy powinny znajdować się w przestrzeni nazw Graphs.

Etap 1: Reprezentacja grafu (6 punktów) #

Ten etap koncentruje się na stworzeniu podstawowej struktury grafu i dwóch różnych implementacji reprezentacji krawędzi grafu.

  • 1.1. Abstrakcyjna klasa Graph (2 punkty)

    • Zdefiniuj publiczną klasę abstrakcyjną Graph.
    • Klasa ta powinna mieć chroniony konstruktor Graph(int vertexCount), który inicjalizuje publiczną właściwość tylko do odczytu int VertexCount.
    • Zadeklaruj następujące metody abstrakcyjne:
      • publiczną List<int> GetOutVertices(int vertex); - zwraca listę sąsiadów wierzchołka vertex
      • publiczną void AddEdge(int from, int to); - dodaje skierowaną krawędź do grafu
    • Zaimplementuj publiczną metodę void Display(), która wypisuje informacje o sąsiedztwie grafu na konsolę. Wynik dla każdego wierzchołka powinien być w formacie wierzchołek -> [sasiad1,sasiad2,...], na przykład:
      0 -> [1,2]
1 -> [3]
2 -> []
3 -> [1]

  • 1.2. Implementacja listy sąsiedztwa (2 punkty)

    • Stwórz publiczną klasę AdjacencyListGraph dziedziczącą po Graph.
    • Powinna mieć publiczny konstruktor AdjacencyListGraph(int vertexCount).
    • Zaimplementuj metody GetOutVertices i AddEdge używając List<int>[] do przechowywania struktury grafu.

  • 1.3. Implementacja macierzy sąsiedztwa (2 punkty)

    • Stwórz publiczną klasę AdjacencyMatrixGraph dziedziczącą po Graph.
    • Powinna mieć publiczny konstruktor AdjacencyMatrixGraph(int vertexCount).
    • Zaimplementuj metody GetOutVertices i AddEdge używając bool[,] do przechowywania struktury grafu.

Etap 2: Przechodzenie grafu i wyszukiwanie ścieżki (6 punktów) #

Ten etap obejmuje dodanie logiki przechodzenia po grafie za pomocą algorytmu DFS i zaimplementowanie wzorca wizytora do przetwarzania wierzchołków podczas przechodzenia.

Przeszukiwanie w głąb (DFS) to algorytm do przechodzenia lub przeszukiwania struktur danych w postaci drzewa lub grafu. Algorytm rozpoczyna przechodzenie od węzła głównego (lub dowolnego węzła w grafie) i eksploruje każdą gałąź tak daleko, jak to możliwe, przed powrotem. Jest on zazwyczaj implementowany przy użyciu rekurencji.

  • 2.1. Algorytm DFS (3 punkty)

    • Dodaj publiczną metodę void DepthFirstSearch(int start, IVertexVisitor visitor) do abstrakcyjnej klasy Graph.
    • Metoda ta powinna implementować algorytm DFS rekurencyjnie.
    • Przechodzenie powinno zaczynać się od wierzchołka start.
    • Przed zejściem rekurencyjnym, metoda powinna wywołać metodę PreVisit z interfejsu IVertexVisitor
    • Po zejściu rekurencyjnym, metoda powinna wywołać metodę PostVisit z interfejsu IVertexVisitor
    • Metoda może używać metody pomocniczej, na przykład DepthFirstSearchRecursive(int vertex, bool[] visited, IVertexVisitor visitor).
      • Użyj tablicy bool[] visited, aby oznaczać i pomijać już odwiedzone wierzchołki.

  • 2.1. Interfejs IVertexVisitor

    • Zdefiniuj publiczny interfejs IVertexVisitor.
    • Interfejs ten powinien deklarować następujące metody:
      • void PreVisit(int vertex);
      • void PostVisit(int vertex);

  • 2.2. PathFinderVisitor (3 punkty)

    • Stwórz publiczną klasę PathFinderVisitor implementującą interfejs IVertexVisitor.
    • Powinna mieć publiczny konstruktor PathFinderVisitor(int target).
    • Powinna mieć następujące właściwości:
      • List<int> Path - publiczna, tylko do odczytu - zawiera wierzchołki tworzące znalezioną ścieżkę
      • bool Found - publiczny odczyt, zapis tylko z poziomu klasy
    • Zaimplementuj metody PreVisit i PostVisit, aby znaleźć ścieżkę do wierzchołka target.
    • Przesłoń metodę ToString(), aby zwracała znalezioną ścieżkę w formacie w1 --> w2 --> ... lub napis “not found”.

Przykładowe rozwiązanie #

Graphs

Previous Lab03 Lab04 Next