Co to jest struktura danych wykresu?

A Wykres jest nieliniową strukturą danych składającą się z wierzchołków i krawędzi. Wierzchołki są czasami nazywane także węzłami, a krawędzie to linie lub łuki łączące dowolne dwa węzły na wykresie. Bardziej formalnie wykres składa się ze zbioru wierzchołków ( W ) i zbiór krawędzi ( I ). Wykres jest oznaczony przez G(V, E) .

Reprezentacje wykresu

Oto dwa najpopularniejsze sposoby przedstawiania wykresu:

1. Macierz sąsiedztwa
2. Lista sąsiedztwa

Macierz sąsiedztwa

Macierz sąsiedztwa to sposób przedstawiania wykresu jako macierzy wartości logicznych (0 i 1).

Załóżmy, że istnieją N wierzchołki grafu Utwórzmy więc macierz 2D adjMat[n][n] mający wymiar n x n.

nieskończona pętla

• Jeśli istnieje krawędź od wierzchołka I Do J , ocena adjMat[i] [j] Jak 1 .
• Jeśli nie ma krawędzi od wierzchołka I Do J , ocena adjMat[i] [j] Jak 0 .

Reprezentacja grafu nieskierowanego w macierzy sąsiedztwa:

Poniższy rysunek przedstawia graf nieskierowany. Początkowo inicjowana jest cała Matrix 0 . Jeśli istnieje krawędź od źródła do miejsca docelowego, wstawiamy 1 w obu przypadkach ( adjMat[miejsce docelowe] I przym. Mat [ miejsce docelowe]) ponieważ możemy iść w obie strony.

Ciąg odwrotny Java

Nieskierowany wykres do macierzy sąsiedztwa

Reprezentacja grafu skierowanego w macierzy sąsiedztwa:

Poniższy rysunek przedstawia graf skierowany. Początkowo inicjowana jest cała Matrix 0 . Jeśli istnieje krawędź od źródła do miejsca docelowego, wstawiamy 1 dla tego konkretnego adjMat[miejsce docelowe] .

Graf skierowany do macierzy sąsiedztwa

Lista sąsiedztwa

Tablica list służy do przechowywania krawędzi pomiędzy dwoma wierzchołkami. Rozmiar tablicy jest równy liczbie wierzchołki (tj. n) . Każdy indeks w tej tablicy reprezentuje określony wierzchołek grafu. Wpis pod indeksem i tablicy zawiera połączoną listę zawierającą wierzchołki sąsiadujące z wierzchołkiem I .

Załóżmy, że istnieją N wierzchołki grafu Utwórz więc tablica listy wielkościowy N Jak adjList[n].

• adjList[0] będzie zawierał wszystkie węzły połączone (sąsiadujące) z wierzchołkiem 0 .
• adjList[1] będzie zawierał wszystkie węzły połączone (sąsiadujące) z wierzchołkiem 1 i tak dalej.

Reprezentacja grafu nieskierowanego do listy sąsiedztwa:

Poniższy graf nieskierowany ma 3 wierzchołki. Zatem zostanie utworzona tablica list o rozmiarze 3, gdzie każdy indeks reprezentuje wierzchołek. Teraz wierzchołek 0 ma dwóch sąsiadów (tj. 1 i 2). Zatem wstaw wierzchołki 1 i 2 o indeksach 0 tablicy. Podobnie, wierzchołek 1 ma dwóch sąsiadów (tj. 2 i 0). Zatem wstaw wierzchołki 2 i 0 pod indeksami 1 tablicy. Podobnie dla wierzchołka 2 wstaw jego sąsiadów do tablicy listy.

Nieskierowany wykres do listy sąsiedztwa

zdefiniuj komputer

Reprezentacja grafu skierowanego do listy sąsiedztwa:

Poniższy graf skierowany ma 3 wierzchołki. Zatem zostanie utworzona tablica list o rozmiarze 3, gdzie każdy indeks reprezentuje wierzchołek. Teraz wierzchołek 0 nie ma sąsiadów. Dla wierzchołka 1 ma dwóch sąsiadów (tj. 0 i 2). Zatem wstaw wierzchołki 0 i 2 pod indeksami 1 tablicy. Podobnie dla wierzchołka 2 wstaw jego sąsiadów do tablicy listy.

Wykres skierowany do listy sąsiedztwa