Autor: Codenga 22.03.2024

Dane są kluczowym elementem współczesnego świata. Równie ważna jest umiejętność badania relacji pomiędzy danymi. W praktyce do badania tych relacji bardzo często się używa grafów. W tym artykule przedstawimy Ci najważniejsze rodzaje grafów, ich zastosowania oraz najpopularniejsze algorytmy grafowe.

Co to jest graf?

Graf to abstrakcyjna struktura danych, która składa się z wierzchołków (czasem nazywanych też węzłami) i krawędzi (łączących te wierzchołki). Wierzchołki reprezentują obiekty, a krawędzie reprezentują relacje między nimi. Grafy są wykorzystywane do modelowania różnych rzeczy, takich jak sieci społeczne, sieci komputerowe, mapy drogowe itp. Oto przykład prostego grafu:

Graf ten zawiera następujące elementy:

• Wierzchołki: A, B, C
• Krawędzie: (A, B), (A, C), (B, C)

Ma więc trzy wierzchołki i trzy krawędzie. Jest to przykład grafu nieskierowanego.

Rodzaje grafów

Grafy skierowane i nieskierowane

W grafie skierowanym krawędzie mają określony kierunek, podczas gdy w grafie nieskierowanym krawędzie nie mają określonego kierunku. Oto przykład grafu skierowanego:

Grafy ważone i nieważone

W grafach ważonych każda krawędź ma przypisaną wagę lub koszt, podczas gdy w grafach nieważonych krawędzie nie posiadają takiej informacji. Poniżej mamy przykład grafu ważonego:

Krawędzie mają następujące wagi:

• (A, B) z wagą 2
• (A, C) z wagą 1
• (B, C) z wagą 3

Grafy spójne i niespójne

Graf spójny to taki, w którym istnieje ścieżka między każdą parą wierzchołków. Graf niespójny to taki, który składa się z co najmniej dwóch oddzielnych składowych.

Algorytmy Grafowe

Algorytmy grafowe to zestaw procedur i reguł służących do analizy oraz przetwarzania grafów. Oto kilka podstawowych algorytmów grafowych.

Przeszukiwanie Wszerz (BFS - Breadth-First Search)

Ten algorytm służy do przeszukiwania lub przechodzenia przez graf wszerz, rozpoczynając od zadanego wierzchołka, a następnie przechodząc do wszystkich jego sąsiadów, zanim przejdzie do sąsiadów tych sąsiadów.

Przeszukiwanie W Głąb (DFS - Depth-First Search)

W przeciwieństwie do BFS, DFS przechodzi przez graf głębiej zanim zacznie wybierać nowe wierzchołki do odwiedzenia.

Algorytm Dijkstry

Służy do znajdowania najkrótszej ścieżki między dwoma wierzchołkami w grafie ważonym.

Algorytm Kruskala i Algorytm Prima

Oba te algorytmy służą do znajdowania minimalnego drzewa rozpinającego w grafie ważonym.

Główne zastosowania grafów

Grafy mają wiele zastosowań w przeróżnych dziedzinach. Używa się ich do modelowania relacji między osobami w sieciach społecznościowych. Używają ich wyszukiwarki internetowe by ocenić powiązania pomiędzy stronami, i na tej podstawie przypisać im wagę. Grafów używa się w logistyce i transporcie do optymalizowania tras. Są też specjalne bazy danych przechowujące informacje w formie grafów - dzięki temu można łatwo zbadać powiązania pomiędzy danymi. Jak widzisz, grafy w dzisiejszym świecie pełnią ważną rolę w wielu dziedzinach życia.