Samouczek struktury danych wykresu

W obliczeniach wykres jest zestawem węzłów podłączonych przez linki. Główną różnicą między drzewem a wykresem jest to, że drzewo ma jeden węzeł główny, podczas gdy wykres ma więcej niż jeden węzeł główny. Powinieneś już mieć podstawową wiedzę na temat struktury danych drzewa przed przyjazdem, ponieważ tam pojęcia będą używane tutaj z niewielkim lub żadnym wyjaśnieniem. Jeśli nie masz tej wiedzy, przeczytaj samouczek zatytułowany Tutorial struktury danych drzewa dla początkujących, na linku, https: // Linuxhint.com/Tree_Data_Structure_Tutorial_Beginners/.

Węzeł na wykresie nazywa się wierzchołkiem (liczba mnoga - wierzchołki). Czasami jest nadal nazywany węzłem; Można go również nazwać punktem. Link na wykresie nazywa się krawędzią. Czasami wciąż nazywany jest linkiem; Można go również nazwać linią.

Wykres z wieloma funkcjami

Ta rysunek pokazuje wykres z wieloma funkcjami:

Kręgi (dyski) to wierzchołki. Każda linia prosta lub zakrzywiona lub pętla to krawędź.

Cechy wykresu

Wierzchołek

Wierzchołek to obiekt. To może być dom; może to być osoba; Może to być rzeczownik abstrakcyjny; może to być dowolny obiekt, o którym możesz pomyśleć.

Krawędź

Krawędź to połączenie (relacja) między dwoma wierzchołkami; Połączenie może być abstrakcyjne.

Pętla

Pętla to krawędź, która łączy wierzchołek z sobą.

Krawędź strzałki

Rozważ dwie osoby: John i Peter. Jeśli John pożyczy Piotra 100 USD, a jeśli John i Peter są wierzchołkami, wówczas krawędź pożyczek będzie wskazywana na Piotra. Jeśli obaj partnerzy zapomną, że Piotr jest winien John, a Peter pożycza Johna 100 USD, to na drugim końcu tej samej krawędzi strzały będzie wskazywać na Jana. Jeśli Peter pożyczył, ale 75 USD na rzecz Johna, a nie 100 USD, inna krawędź połączy Piotra z Johnem. Ta druga krawędź będzie miała strzałkę wskazującą na Jana. W drugim przypadku istnieją dwie krawędzie, z jednym grotem strzałowym, wskazującym w przeciwnych kierunkach.

Wierzchołek, do którego wskazuje krawędź, jest wierzchołkiem głowy dla tej krawędzi. Wierzchołek, z którego opuszcza krawędź, jest wierzchołkiem ogonowym.

Incydent

Krawędź łączy dwa wierzchołki. Mówi się, że krawędź jest incydent. Krawędź nie musi mieć groty strzałki. Dwa wierzchołki są znane jako punkty końcowe krawędzi. Możliwe jest posiadanie wykresu, w którym wierzchołek nie należy do żadnej krawędzi, ale nie będzie to rozważane w tym samouczku.

Niekierowany wykres

Krawędź może być strzałą lub nie może. Wykres, w którym nie ma krawędzi strzałki, jest niekierowanym wykresem. Krawędź może być reprezentowana przez linię prostą, krzywą lub pętlą.

Kierowany wykres

Wykres, na którym każda krawędź jest strzałką (kierunek), jest ukierunkowanym wykresem. Krawędź strzałki może być reprezentowana przez linię prostą z grotem strzałki lub krzywą z grotem strzałnym lub pętlą z grotem strzałkim.

Brak kierunku na krawędzi niekierowanego wykresu oznacza każdą krawędź niekierowanego wykresu, jest dwukierunkowy.

Stopień wierzchołka

Liczba krawędzi, które są zdarzenia na wierzchołku, to stopień wierzchołka. Pętla ma dwie przypadki na wierzchołek, więc pętla jest liczyła dwa razy.

Kolejność wykresu

Kolejność wykresu to liczba wierzchołków na wykresie.

Multigraph

Multigraph to wykres, w którym w niektórych parach wierzchołków jest więcej niż jedne krawędzie. Niekierżnąc multigraph to taki wykres, w którym krawędzie nie mają żadnych kierunków (nie są strzałkami). Kierowany multigraph to taki, w którym każda krawędź jest strzałką, a dla par wierzchołków, które mają więcej niż jedną strzałkę, jeden wierzchołek to ogon tych strzałek, a drugi wierzchołek jest głową tych samych strzałek. Poniższy schemat pokazuje niekierowany multigraph:

Więcej niż jedna krawędzie (ja.mi. wiele krawędzi) dla pary wierzchołków jest również nazywane krawędziami równoległymi.

Kołczan

Trochę to multigraph, który umożliwia pętle (jedną lub więcej pętli). Niektóre multigrafy nie pozwalają na pętle.

Prosty wykres

Prosty wykres to wykres, na którym nie ma dwóch par wierzchołków wielu krawędzi. Pętle nie są dozwolone na prostym wykresie.

Pusty wykres

Pusty wykres to wykres bez wierzchołków, więc bez krawędzi.

Mieszany wykres

Mieszany wykres to wykres, na którym niektóre krawędzie to strzałki, a inne nie; Innymi słowy: niektóre krawędzie mają wskazówki, a inne nie są kierowane.

Ważony wykres

Możliwe jest posiadanie wykresu, na którym liczba, zwana wagą, jest przypisana do każdej krawędzi. Niektóre krawędzie mają tę samą liczbę, ale liczby są na ogół różne. Taki wykres nazywa się wykresem ważonym. Liczby konkretnego wykresu mogą reprezentować długości lub koszty (ceny) lub wielkość pewnego rodzaju, w zależności od problemu.

Niezależność i na zewnątrz

Słownictwo, niezależne i zewnętrzne mają zastosowanie tylko do wykresu ukierunkowanego. Wykres może, ale nie musi być multigrafem. Wykres może, ale nie musi mieć pętli.

Liczba strzałek podłączonych do wierzchołka jest niezgodnym z tego wierzchołka. Strzałka z pojedynczym grotem ma główny koniec i koniec ogona. Liczba ogonów podłączonych do wierzchołka jest reżyserem tego wierzchołka.

Uwaga: wykres z wieloma krawędziami dla pary wierzchołków, w których wiele krawędzi znajduje się w przeciwnych kierunkach, nie jest adresowany w tym samouczku.

Reprezentacja oprogramowania wykresu

Wykres może być reprezentowany w oprogramowaniu tak, jak jest rysowany na schemacie. Wykres może być również reprezentowany w oprogramowaniu przez matematyczną macierz (tablica dwuwymiarowa). Jedna z takich macierzy nazywa się macierzą przylegania.

Macierz sąsiedztwa

Matryca sąsiedności jest macierzą kwadratową. Nagłówki dla wierszy to wszystkie wierzchołki, napisane w kolejności rosnącej. Nagłówki dla kolumn to nadal te same wierzchołki, napisane w kolejności rosnącej. Liczenie wierszy lub kolumn macierzy zaczyna się od 1, a nie zero, jak w przypadku tablic. Podczas identyfikacji elementu w macierzy numer wiersza jest zapisywany najpierw przed numerem kolumny.

W przypadku nieokreślonego wykresu każdy wpis (element) w macierzy sąsiedności to liczba krawędzi łączących dwa odpowiednie wierzchołki. Pętla powinna być policzona dwukrotnie. W przypadku wykresu ukierunkowanego każdy wpis w macierzy sąsiedności jest albo liczbą krawędzi, pozostawiając wierzchołek wiersza i wchodzący do odpowiedniego wierzchołka kolumny lub jest liczbą krawędzi pozostawiających wierzchołek kolumny i wchodzący do odpowiedniego wiersza wiersza. Wybór jest wyborem programisty. W tej sytuacji (w obu przypadkach) pętla powinna być nadal liczona.

Uwaga: Wykres jest schematem to struktura danych sama w sobie. Matryca sąsiedności jest również samodzielną strukturą danych.

Nieokreślony wykres i macierz sąsiedności

Poniższe schematy pokazują niekierowany wykres i odpowiadającą macierz przylegania:

Wiodącą przekątną macierzy to przekątna od lewej górnej części do dolnej. Nieokreślona matryca jest symetryczna w kwestii wiodących przekątnej. Wpis macierzy dla wiersza A i kolumny C wynosi 1, co oznacza, że ​​istnieje jedna krawędź łącząca wierzchołek A i wierzchołek C. Wpis macierzy dla wiersza C i kolumny B wynosi 3, co oznacza, że ​​istnieją 3 krawędzie łączące wierzchołek C i wierzchołek B. Pozostałe wpisy są podobnie wyjaśnione.

Suma wpisów dla wiersza daje liczbę krawędzi (stopnia) dla odpowiedniego wierzchołka. Suma wpisów dla wiersza A wynosi 2, co oznacza, że ​​2 krawędzie są podłączone do wierzchołka a. Suma wpisów dla wiersza B wynosi 6, co oznacza, że ​​6 krawędzi jest podłączonych do wierzchołka B. Reszta wpisów jest podobnie wyjaśniona.

Kierowany wykres i macierz sąsiedności

Poniższe schematy pokazują ukierunkowany wykres i odpowiadającą macierz przylegania:

Matryca sąsiedności dla ukierunkowanego wykresu niekoniecznie jest symetryczna w sprawie wiodący. Wpis macierzy dla wiersza A i kolumny C wynosi 1, co oznacza, że ​​jedna krawędź odchodzi od wierzchołka A do wierzchołka C. Wpis macierzy dla wiersza C i kolumny B wynosi 3, co oznacza, że ​​3 krawędzie pozostawiają od wierzchołka C do wierzchołka B. Pozostałe wpisy są podobnie wyjaśnione.

Suma wpisów dla kolumny daje niezadowole. Suma wpisów dla wiersza daje enetyczne dla (wiersz) wierzchołek. Suma wpisów dla kolumny A wynosi 1, co oznacza, że ​​jedna krawędź jest skierowana do wierzchołka a. Suma wpisów dla wiersza B wynosi 2, co oznacza, że ​​2 krawędzie opuszczają od wierzchołka B. Reszta wpisów jest podobnie wyjaśniona.

Operacje wykresowe

Struktura danych, taka jak wykres, składa się z zestawu wartości danych lub zestawu obiektów, a także związku między obiektami, a także operacje (funkcje) między obiektami. Relacje na wykresie są wskazywane przez krawędzie. Do tego wykres powinien mieć przynajmniej następujące operacje:

sąsiadujący (g, x, y)

G oznacza wykres. Ta operacja weryfikuje, czy krawędź łączy Vertex X i Vertex y. Wartość i pozycja wpisu w matrycy wskazują połączenie krawędzi (i jej typu).

sąsiedzi (g, x)

Ta operacja zwraca listę wszystkich wierzchołków, które są bezpośrednio podłączone do Vertex x. Wartość i położenie wpisu w matrycy wskazują połączenie krawędzi.

remove_vertex (g, x)

Ta operacja usuwa wierzchołek, x z wykresu. Jeśli wierzchołek nie miał przewagi, nie ma problemu. Jeśli jednak wierzchołek miał linki, należy również usunąć linki (krawędzi). Wartość i pozycja wpisu w matrycy wskazują na obecność określonego wierzchołka. Jeśli wierzchołek zostanie usunięty, macierz musi zostać dostosowana.

add_vertex (g, x)

To dodaje wierzchołek, x bez dodawania krawędzi lub zastępuje wierzchołek, który miał krawędzie, ale zostały usunięte. Wartość i pozycja wpisu w matrycy wskazują na obecność określonego wierzchołka. Jeśli dodano wierzchołek, macierz musi zostać dostosowana.

add_edge (g, x, y)

Ta operacja dodaje nową krawędź między wierzchołkiem x a wierzchołkiem y, jeśli nie było krawędzi. Wartość i położenie wpisu w matrycy wskazują na obecność określonej krawędzi. W przypadku dodania krawędzi macierz musi zostać dostosowana.

Usuń_dedia (g, x, y)

Ta operacja usunie krawędź między wierzchołkiem x a wierzchołkiem y, gdyby krawędź tam była. Wartość i położenie wpisu w matrycy wskazują na obecność określonej krawędzi. Jeśli krawędź zostanie usunięta, macierz musi zostać dostosowana.

get_vertex_value (g, x)

Ta operacja zwraca wartość, v powiązaną z wierzchołkiem, x. Aby to osiągnąć, potrzebujesz zestawu mocy podzbiorów dla etykiet wierzchołków i ich wartości.

set_vertex_value (g, x, v)

Ta operacja daje nową wartość, v dla wartości powiązanej z wierzchołkiem, x. Aby to osiągnąć, potrzebujesz zestawu mocy podzbiorów dla etykiet wierzchołków i ich wartości.

Niektóre wykresy kojarzą również wartości z ich krawędziami. Takie wykresy wymagają następujących dodatkowych operacji:

get_edge_value (g, x, y)

Ta operacja zwraca wartość, v powiązaną z krawędzią, (x, y). Aby to osiągnąć, potrzebujesz zestawu mocy podzbiorów dla krawędzi i ich wartości.

set_edge_value (g, x, y, v)

Ta operacja daje nową wartość dla wartości powiązanej z krawędzią, (x, y). Aby to osiągnąć, potrzebujesz zestawu mocy podzbiorów dla krawędzi i ich wartości.

Wniosek

Wykres to zestaw wierzchołków połączonych z krawędziami. Wykres może być niekierowany lub skierowany. Krawędzie mogą być niekierunkowe lub kierunkowe. Pętle mogą być obecne lub nieobecne na wykresie. Należy się nauczyć, jest ustawione, zasilane i multiset związane z wykresami. Następnie należy nauczyć się różnych rodzajów wykresów, takich jak wykres zorientowany, wykres regularny, wykres pełny, wykres dwustronny, wykres turniejowy, wykres sieciowy przepływowy itp.

Chrys