Struktura danych wykresu

Spisie treści

Terminologia graficzna
Reprezentacja wykresu
Operacje na wykresach

W tym samouczku dowiesz się, czym jest struktura danych wykresu. Znajdziesz również reprezentacje wykresu.

Grafowa struktura danych to zbiór węzłów, które zawierają dane i są połączone z innymi węzłami.

Spróbujmy to zrozumieć na przykładzie. Na Facebooku wszystko jest węzłem. Obejmuje to użytkownika, zdjęcie, album, wydarzenie, grupę, stronę, komentarz, historię, wideo, łącze, notatkę… wszystko, co zawiera dane, jest węzłem.

Każda relacja to granica od jednego węzła do drugiego. Niezależnie od tego, czy publikujesz zdjęcie, dołączasz do grupy, jak strona itp., Tworzy się nowa krawędź dla tej relacji.

Przykład struktury danych wykresu

Cały Facebook jest wtedy zbiorem tych węzłów i krawędzi. Dzieje się tak, ponieważ Facebook używa struktury danych wykresu do przechowywania swoich danych.

Dokładniej, wykres to struktura danych (V, E), z której składa się

Zbiór wierzchołków V
Zbiór krawędzi E, reprezentowanych jako uporządkowane pary wierzchołków (u, v)

Wierzchołki i krawędzie

Na wykresie

 V = (0, 1, 2, 3) E = ((0,1), (0,2), (0,3), (1,2)) G = (V, E)

Terminologia graficzna

Przyleganie : mówi się, że wierzchołek sąsiaduje z innym wierzchołkiem, jeśli łączy je krawędź. Wierzchołki 2 i 3 nie sąsiadują ze sobą, ponieważ nie ma między nimi krawędzi.
Ścieżka : sekwencja krawędzi, która umożliwia przejście od wierzchołka A do wierzchołka B nazywana jest ścieżką. 0-1, 1-2 i 0-2 to ścieżki od wierzchołka 0 do wierzchołka 2.
Wykres skierowany : wykres, w którym krawędź (u, v) niekoniecznie oznacza, że istnieje również krawędź (v, u). Krawędzie na takim wykresie są reprezentowane strzałkami, aby pokazać kierunek krawędzi.

Reprezentacja wykresu

Wykresy są zwykle przedstawiane na dwa sposoby:

1. Macierz sąsiedztwa

Macierz sąsiedztwa to dwuwymiarowa tablica wierzchołków V x V. Każdy wiersz i kolumna reprezentują wierzchołek.

Jeśli wartość dowolnego elementu a(i)(j)wynosi 1, oznacza to, że istnieje krawędź łącząca wierzchołek i i wierzchołek j.

Macierz sąsiedztwa dla utworzonego powyżej wykresu to

Wykres macierzy sąsiedztwa

Ponieważ jest to wykres nieukierunkowany, dla krawędzi (0,2) musimy również zaznaczyć krawędź (2,0); uczynienie macierzy sąsiedztwa symetryczną względem przekątnej.

Wyszukiwanie krawędzi (sprawdzanie, czy istnieje krawędź między wierzchołkiem A i wierzchołkiem B) jest niezwykle szybkie w reprezentacji macierzy sąsiedztwa, ale musimy zarezerwować miejsce na każde możliwe połączenie między wszystkimi wierzchołkami (V x V), więc wymaga więcej miejsca.

2. Lista sąsiedztwa

Lista sąsiedztwa przedstawia wykres jako tablicę połączonych list.

Indeks tablicy reprezentuje wierzchołek, a każdy element na jego liście połączonej reprezentuje inne wierzchołki, które tworzą krawędź z wierzchołkiem.

Lista sąsiedztwa dla wykresu, który stworzyliśmy w pierwszym przykładzie, wygląda następująco:

Reprezentacja listy sąsiedztwa

Lista sąsiedztwa jest wydajna pod względem przechowywania, ponieważ musimy przechowywać tylko wartości dla krawędzi. W przypadku wykresu z milionami wierzchołków może to oznaczać dużo zaoszczędzonego miejsca.