Rozdział 6. Algorytmy grafowe

Przegląd

Grafy są podstawowymi strukturami używanymi w informatyce do reprezentowania złożonych informacji strukturalnych. Każda z ilustracji zestawionych na Rysunek 6-1 jest przykładem grafu.

W tym rozdziale rozpatrujemy typowe sposoby reprezentowania grafów i niektóre związane z nimi, często spotykane algorytmy. Graf jako taki składa się ze zbioru elementów, które zwykło się nazywać wierzchołkami (ang. vertices), i powiązań między parami tych elementów, nazywanych krawędziami (albo łukami, ang. edges). W tym rozdziale rozważamy tylko grafy proste — takie, w których nie ma: (a) pętli, czyli krawędzi prowadzących do wierzchołków, z których same wychodzą, i (b) wielu krawędzi między tą samą parą wierzchołków.

Grafy

Graf ...

Get Algorytmy. Almanach now with the O’Reilly learning platform.

O’Reilly members experience books, live events, courses curated by job role, and more from O’Reilly and nearly 200 top publishers.