Lista sąsiedniej w C ++
- Lista sąsiedności
- Matryca sąsiedności
- Macierz występowania
Podstawowym tematem tego artykułu będzie lista sąsiedności. Najpierw spróbujmy zrozumieć, czym naprawdę jest wykres, zanim weszmy w to, aby lepiej zrozumieć ten pomysł.
Co to jest wykres?
Wykres ma stałą liczbę węzłów lub wierzchołków. A każdy węzeł jest połączony linią, którą nazywamy krawędzią. Krawędź dotyczy komunikacji między dwoma wierzchołkami lub węzłami. Na przykład na powyższym wykresie widzimy sześć wierzchołków lub węzłów (0, 1, 2, 3, 4 i 5). Z wierzchołka lub węzła 0 możemy łatwo przejść do Vertex 1 i 3, ponieważ istnieje między nimi bezpośrednie połączenie. Ale nie ma bezpośredniego połączenia między wierzchołkiem lub węzłem 0 i 4.
Wykresy są używane w wielu rzeczywistych aplikacjach do rozwiązywania problemów sieciowych. Na przykład na Facebooku profil użytkownika jest węzłem lub wierzchołkiem, a przyjaciele użytkownika na liście są kolejnymi różnymi węzłami lub wierzchołkami, które mają między sobą bezpośrednie połączenia.
Rodzaje wykresów
Istnieją przede wszystkim dwa rodzaje wykresów, nieokreślone wykresy i ukierunkowane wykresy, oba opisano w następnych sekcjach:
Niekierowany wykres
Niekierowany wykres jest bardzo znany, ponieważ jest wykresem dwukierunkowym. Na przykład poniżej jest przykład niekierowanego wykresu:
Niekierowany wykres
Na niekierowanym wykresie możemy przenieść się do dowolnego wierzchołka. Na przykład, jeśli istnieje połączenie między węzłami A i B, możemy również przejść z B do A.
Kierowany wykres
Na ukierunkowanym wykresie krawędzie mają krawędzie kierunkowe. Więc te krawędzie strzałek powiedzą nam, jak możemy poruszać się na wykresie z jednego wierzchołka do drugiego wierzchołka, ale tylko w niektórych warunkach. Na przykład, jeśli istnieje ukierunkowana krawędź między węzłami A i B, możemy szybko przenieść się z wierzchołka A do B, ale nie z powrotem z B do A, jeśli nie ma ukierunkowanej krawędzi od B do A.
Kierowany wykres
Lista sąsiedności
Lista sąsiedniej jest listą tablic, w których rozmiar tablicy jest równy liczbie węzłów obecnych na wykresie. A każdy węzeł ma również podorządek, który reprezentuje swoją łączność z innymi węzłami lub wierzchołkami. Omówimy listy sąsiedności obu typów wykresów (niekierunkowane i ukierunkowane).
Lista sąsiedniej wykresu
Na powyższym niekierowanym wykresie możemy zobaczyć sześć wierzchołków (0, 1, 2, 3, 4, 5). Mamy więc szereg sześciu wierzchołków. I każdy kolejny indywidualny wierzchołek ma swoją własną listę lub listę sąsiedniej, jak pokazano na poprzedniej liście sąsiedniej. Widzimy, że Vertex 0 wskazuje na Vertex 4 i Vertex 3.
Ale, jak wyjaśniliśmy wcześniej, niekierowany wykres może poruszać się w obu kierunkach. Istnieje krawędź między węzłami 0 i 4 a bezpośrednim połączeniem między 0 do 4. Ale z powodu nieokreślonego wykresu istnieje również połączenie między 4 do 0. Dlatego jeśli spojrzysz na poprzednią listę sąsiedności, Vertex 4 wskazuje również na wierzchołek 0. To samo dotyczy również wierzchołka 3. Lista sąsiedniej Vertex 3 również wskazuje na wierzchołek 0.
Kierowana lista sąsiedniej wykresu
Powyższy obraz jest ukierunkowanym wykresem, a po prawej stronie znajduje się lista sąsiedniej. Na tej liście sąsiedniej możemy zobaczyć bezpośrednią krawędź od węzła 1 do węzła 2, ale nie z węzła 2 do 1. Możemy więc poruszać się tylko w jednym kierunku, to znaczy od 1 do 2. To samo znajduje się na liście sąsiedniej. Nie widzimy żadnego linku od Vertex 2 do 1 na liście sąsiedniej 2.
Macierz sąsiedztwa
Matryca jest używana w tej metodzie do reprezentowania szczegółów wierzchołków wykresu. Rozmiar macierzy zależy od liczby wierzchołków na wykresie. Na przykład, jeśli jakikolwiek wykres ma 5 wierzchołków, wówczas rozmiar macierzy wyniesie 5 x 5. W tym wiersz i kolumna to same wierzchołki. Reprezentacja macierzy listy sąsiedności używa 1 lub 0 do wypełnienia macierzy. Wartość 1 reprezentuje ścieżkę od wierzchołka wiersza do kolumny wierzchołek, ale wartość 0 reprezentuje ścieżkę między wierzchołkiem wiersza a wierzchołkiem kolumnowym.
Lista przyległych macierzy wykresu
Na powyższej liście MATRIX DOCCENCYS. Tak więc wypełniliśmy tę wartość 0. Ale jest ścieżka od wierzchołka B do A i wypełniliśmy tę wartość 1.
Kierowana lista macierzy wykresu
Na wyżej skierowanej listy przylegania macierzy możemy zobaczyć, że od A do D jest wartością 0, ponieważ nie ma ścieżki od A do D, ale istnieje ścieżka od D do A, więc wypełniliśmy tę wartość 1 za pomocą 1.
Macierz występowania
Matryca jest używana w tej metodzie do reprezentowania szczegółów wierzchołków wykresu. Rozmiar macierzy zależy od liczby wierzchołków i całkowitych krawędzi na wykresie. Na przykład, jeśli jakikolwiek wykres ma 5 wierzchołków i 7 krawędzi, wówczas rozmiar macierzy wyniesie 5 x 7. Krawędzie będą reprezentować kolumny, a wierzchołki będą po stronie wiersza. Reprezentacja macierzy listy sąsiedności używa 0, 1 lub -1 do wypełnienia wartości macierzy.
Wartość 1 reprezentuje ścieżkę wychodzącą od wierzchołka wiersza do kolumny, ale wartość 0 reprezentuje nie ścieżkę między wierzchołkiem wiersza a wierzchołkiem kolumnowym. Wartość -1 reprezentuje przychodzącą ścieżkę do krawędzi wierzchołka kolumny.
Kierowany wykres
Lista sąsiedniej wykresu ukierunkowanego
Kod C ++ dla listy ukierunkowanej wykresu
#włączać
za pomocą przestrzeni nazw Std;
// Składnia do utworzenia węzła
węzeł struct
wartość int;
Węzeł* następny;
;
// To będzie przechowywać szczegóły krawędzi wykresu (źródło i miejsce docelowe)
struct GraphEdge
Źródło int, miejsce docelowe;
;
klasa GraphAdjaccyList
// Utwórz nowy węzeł dla listy sąsiedności
Węzeł* getneighbourvertex (int cel docelowy, węzeł* head_node)
Node* new_node = new Node;
new_node-> wartość = miejsce docelowe;
new_node-> następny = head_node;
zwróć nowy_node;
// będzie przechowywać całkowitą liczbę węzłów na wykresie
int number_of_nodes;
publiczny:
Węzeł ** head_node;
GraphAdjaccyList (GraphEdge GraphEdges [], int num, int numer_of_nodes)
// dynamiczna alokacja pamięci
head_node = nowy węzeł*[numer_of_nodes] ();
this-> numer_of_nodes = numer_of_nodes;
// zainicjuj nod head dla każdej krawędzi wykresu
dla (int k = 0; k < number_of_nodes; k++)
head_node [k] = nullptr;
dla (int k = 0; k < num; k++)
Int źródło = Graphedges [k].źródło;
int Destination = Graphedges [k].miejsce docelowe;
Node* new_node = getneighbourvertex (miejsce docelowe, head_node [źródło]);
head_node [źródło] = new_node;
~ GraphAdjaccyList ()
dla (int k = 0; k < number_of_nodes; k++)
delete [] head_node [k];
delete [] head_node;
;
void display (węzeł* displayptr)
While (DisplayPtr != nullptr)
Cout << " adjacency list -> " << displayptr->wartość;
displayPtr = displayPtr-> następny;
Cout << endl;
int main ()
GraphEdge Graphedges [] =
// są to wartości x i y, które reprezentują krawędź od x do y
0, 1, 1, 2, 2, 0, 2, 1, 3, 2, 4, 1, 3, 4
;
// Całkowita liczba węzłów od 0 do 5, więc łączna liczba węzłów wynosi 6
int number_of_nodes = 6;
// Ta metoda obliczy liczbę krawędzi na wykresie
int num_edges = sizeof (GraphEdges)/sizeof (GraphEdges [0]);
// Utwórz wykres
GraphAdjaccyList Graph (GraphEdges, num_edges, numer_of_nodes);
// Wyświetl listę sąsiedności wykresu
dla (int k = 0; k < number_of_nodes; k++)
Cout << k;
Wyświetlacz (wykres.head_node [k]);
powrót 0;
Wyjście:
0 Lista sąsiedniej -> 1
1 lista sąsiedniej -> 2
2 Lista sąsiedności -> 1 lista sąsiedniej -> 0
3 Lista sąsiedności -> 4 Lista sąsiedniej -> 2
4 Lista sąsiedniej -> 1
5
Kierowany wykres z krawędziami ciężarowymi
Lista sąsiedniej wykresu ukierunkowanego
Kod C ++ dla listy ukierunkowanej wykresu z wagą
#włączać
za pomocą przestrzeni nazw Std;
// Składnia do utworzenia węzła
Node struct
wartość int, koszt;
Węzeł* następny;
;
// To będzie przechowywać szczegóły krawędzi wykresu (źródło i miejsce docelowe)
struct GraphEdge
INT źródło, miejsce docelowe, krawędź;
;
klasa GraphAdjaccyList
// Utwórz nowy węzeł dla listy sąsiedności
Węzeł* getneighbourvertex (int cel,
Węzeł* head_node)
Node* new_node = new Node;
new_node-> wartość = miejsce docelowe;
new_node-> cost = krawędź;
new_node-> następny = head_node;
zwróć nowy_node;
// będzie przechowywać całkowitą liczbę węzłów na wykresie
int number_of_nodes;
publiczny:
Węzeł ** head_node;
GraphAdjaccyList (GraphEdge GraphEdges [], int num, int numer_of_nodes)
// dynamiczna alokacja pamięci
head_node = nowy węzeł*[numer_of_nodes] ();
this-> numer_of_nodes = numer_of_nodes;
// zainicjuj nod head dla każdej krawędzi wykresu
dla (int k = 0; k < number_of_nodes; k++)
head_node [k] = nullptr;
dla (int k = 0; k < num; k++)
Int źródło = Graphedges [k].źródło;
int Destination = Graphedges [k].miejsce docelowe;
int Wadza krawędziowa = Graphedges [k].Wadza krawędzi;
Węzeł* new_node = getneighbourvertex (miejsce docelowe, krawędź wagi,
head_node [źródło]);
head_node [źródło] = new_node;
GraphAdjaccyList ()
dla (int k = 0; k < number_of_nodes; k++)
delete [] head_node [k];
delete [] head_node;
;
void display (węzeł* displayptr, int k)
While (DisplayPtr != nullptr)
Cout << "(" << k << ", " <<
DisplayPtr-> wartość << ", " << displayptr->koszt << ") ";
displayPtr = displayPtr-> następny;
Cout << endl;
int main ()
GraphEdge Graphedges [] =
// (x, y, z) => Są to wartości x i y, które reprezentują krawędź
// od x do y z wagą w
0, 1, 4, 1, 2, 6, 2, 0, 3, 2, 1, 5, 3, 4, 8,
4, 1, 1, 3, 2, 7
;
// Całkowita liczba węzłów od 0 do 5, więc łączna liczba węzłów wynosi 6
int number_of_nodes = 6;
// Ta metoda obliczy liczbę krawędzi na wykresie
int num_edges = sizeof (GraphEdges)/sizeof (GraphEdges [0]);
// Utwórz wykres
GraphAdjaccyList Graph (GraphEdges, num_edges, numer_of_nodes);
// Wyświetl listę sąsiedności wykresu
dla (int k = 0; k < number_of_nodes; k++)
Cout << k;
Wyświetlacz (wykres.head_node [k], k);
powrót 0;
Wyjście:
0 (0, 1, 4)
1 (1, 2, 6)
2 (2, 1, 5) (2, 0, 3)
3 (3, 2, 7) (3, 4, 8)
4 (4, 1, 1)
5
Wniosek
W tym artykule widzieliśmy różne metody reprezentowania wykresu. Widzieliśmy również matrycę występowania, która jest również metodą reprezentowania macierzy wykresu. Następnie omówiliśmy inne metody programowania C ++ w celu przedstawienia listy sąsiedności (wyświetlacze ukierunkowane i ważone). Zbadaliśmy również ukierunkowane i niekierowane wykresy. Dowiedzieliśmy się również, że niekierowany wykres jest łatwy w obsłudze w porównaniu do wykresu ukierunkowanego, ponieważ niekierowany wykres jest wykresem dwukierunkowym. W końcu nie zależy od kierunku krawędzi, tak jak wykres ukierunkowany.