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:
Macierz sąsiedztwa: Dwuwymiarowa tablica, w której wpis
macierz[i][j]ma wartość1lubtrue, jeśli istnieje krawędź od wierzchołkaido wierzchołkaj, a0lubfalsew 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).Lista sąsiedztwa: Tablica list, w której lista o indeksie
izawiera wszystkie wierzchołki sąsiadujące z wierzchołkiemi. 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 odczytuint VertexCount. - Zadeklaruj następujące metody abstrakcyjne:
- publiczną
List<int> GetOutVertices(int vertex);- zwraca listę sąsiadów wierzchołkavertex - publiczną
void AddEdge(int from, int to);- dodaje skierowaną krawędź do grafu
- publiczną
- Zaimplementuj publiczną metodę
void Display(), która wypisuje informacje o sąsiedztwie grafu na konsolę. Wynik dla każdego wierzchołka powinien być w formaciewierzchołek -> [sasiad1,sasiad2,...], na przykład:0 -> [1,2] 1 -> [3] 2 -> [] 3 -> [1]
- Zdefiniuj publiczną klasę abstrakcyjną
1.2. Implementacja listy sąsiedztwa (2 punkty)
- Stwórz publiczną klasę
AdjacencyListGraphdziedziczącą poGraph. - Powinna mieć publiczny konstruktor
AdjacencyListGraph(int vertexCount). - Zaimplementuj metody
GetOutVerticesiAddEdgeużywającList<int>[]do przechowywania struktury grafu.
- Stwórz publiczną klasę
1.3. Implementacja macierzy sąsiedztwa (2 punkty)
- Stwórz publiczną klasę
AdjacencyMatrixGraphdziedziczącą poGraph. - Powinna mieć publiczny konstruktor
AdjacencyMatrixGraph(int vertexCount). - Zaimplementuj metody
GetOutVerticesiAddEdgeużywającbool[,]do przechowywania struktury grafu.
- Stwórz publiczną klasę
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 klasyGraph. - Metoda ta powinna implementować algorytm DFS rekurencyjnie.
- Przechodzenie powinno zaczynać się od wierzchołka
start. - Przed zejściem rekurencyjnym, metoda powinna wywołać metodę
PreVisitz interfejsuIVertexVisitor - Po zejściu rekurencyjnym, metoda powinna wywołać metodę
PostVisitz interfejsuIVertexVisitor - 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.
- Użyj tablicy
- Dodaj publiczną metodę
2.1. Interfejs
IVertexVisitor- Zdefiniuj publiczny interfejs
IVertexVisitor. - Interfejs ten powinien deklarować następujące metody:
void PreVisit(int vertex);void PostVisit(int vertex);
- Zdefiniuj publiczny interfejs
2.2.
PathFinderVisitor(3 punkty)- Stwórz publiczną klasę
PathFinderVisitorimplementującą interfejsIVertexVisitor. - 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
PreVisitiPostVisit, aby znaleźć ścieżkę do wierzchołkatarget. - Przesłoń metodę
ToString(), aby zwracała znalezioną ścieżkę w formaciew1 --> w2 --> ...lub napis “not found”.
- Stwórz publiczną klasę
Przykładowe rozwiązanie
Graphs