W12 grafy 1, bioinformatyka, Semestr 2, metody programowania
[ Pobierz całość w formacie PDF ]
IIUJ Metody Programowania strona: 1 Wykład 12. Wprowadzenie do algorytmów na grafach Grafy to struktury danych podobne do drzew, ale w grafach nie wyróżnia się korzenia. Grafy często reprezentują różne problemy spotykane w rzeczywistości. Przykładowo węzły w grafie mogą reprezentują miasta na mapie, a krawędzie – połączenia lotnicze między miastami. Graf nie odzwierciedla geograficznego układu widocznych na mapie elementów. Przedstawia jedynie związki między wierzchołkami, czyli to, z którymi wierzchołkami jest połączona dana krawędź. Innym przykładem może być graf reprezentujący poszczególne zadania - składowe pewnego projektu, natomiast skierowane krawędzie określają kolejność wykonywania zadań. Definicja Grafem zorientowanym (skierowanym lub digrafem) nazywany strukturę zawierającą G = (V, E), przy czym: V - skończony niepusty zbiór wierzchołków, E V V - zbiór krawędzi, krawędzie są parami wierzchołków. W grafie skierowanym, jeśli (i, j) jest krawędzią to j jest następnikiem i , i jest poprzednikiem j , przy czym i może być równe j – wtedy istnieje pętla od danego wierzchołka do niego samego. Poniższy rysunek przedstawia graf skierowany G = (V, E ) 1 2 3 4 IIUJ Metody Programowania strona: 2 V= {1, 2, 3, 4} E = {(1, 2), (1, 3), (1, 4), (2, 3), (2, 4), (3, 2), (3, 4), (4, 3)} Definicja Grafem niezorientowanym (nieskierowanym) nazywamy strukturę : G = (V, E), przy czym: V - skończony niepusty zbiór wierzchołków E 2 V – zbiór krawędzi, e E : | e | = 2, krawędzie są dwuelementowymi podzbiorami . W grafie niezorientowanym, jeśli (i, j) jest krawędzią to j jest sąsiadem i , i jest sąsiadem j . W grafie niezorientowanym nie mogą występować pętle, każda krawędź zawiera dokładnie dwa różne wierzchołki . Typowe oznaczenie: |V|= n, |E| = m. Liczba krawędzi: w grafie zorientowanym: 0 m n * n w grafie niezorientowanym: 0 m n * (n-1)/2 Reprezentacja komputerowa grafów Utożsamiamy zbiór wierzchołków V = {1, ... ,n} 1. Tablica (macierz) sąsiedztwa , jej wielkość nie zależy od liczby krawędzi w grafie: 1 (i, j) E adjMat[i, j] = 0 (i, j) E Dla grafu niezorientowanego jest symetryczna, z zerami na przekątnej. Fakt: Rozmiar pamięci potrzebnej dla tablicy sąsiedztwa wynosi (n 2 ). 2. Listy sąsiedztwa (listy przylegania), kolejność na listach dowolna: IIUJ Metody Programowania strona: 3 Tablica L[n] nagłówków list (częste oznaczenie: Adj[n] – "adjacency") L[ i ] - jest nagłówkiem listy zawierającej wszystkie j , takie że (i, j) jest krawędzią. Dla grafu niezorientowanego każda krawędź (i, j) reprezentowana jest w liście L[i] oraz w liście L[j]. Fakt: Rozmiar pamięci potrzebnej dla list sąsiedztwa wynosi (n + m). Terminologia Stopień wierzchołka: liczba jego następników (sąsiadów) Ścieżka od wierzchołka u do wierzchołka w : ciąg wierzchołków v 0 , v 1 , ..., v k taki, że (v i , v i+1 ) E, i=0,...,k-1, v 0 , = u , v k = w (inaczej: wierzchołek w jest osiągalny z wierzchołka u) Ścieżka prosta (elementarna): wierzchołki na ścieżce nie powtarzają się (być może za wyjątkiem v 0 = v k ) W grafie zorientowanym ścieżka v 0 , v 1 , ..., v k tworzy cykl, jeśli v 0 = v k oraz zawiera co najmniej jedną krawędź. Cykl nazywamy prostym, jeśli dodatkowo v 1 , ..., v k są różne. W grafie niezorientowanym ścieżka v 0 , v 1 , ..., v k tworzy cykl, jeśli v 0 = v k oraz v 1 , ..., v k są różne i k 2 ( zawiera co najmniej trzy wierzchołki) . IIUJ Metody Programowania strona: 4 Długość ścieżki: liczba krawędzi na ścieżce (tutaj: k) Odległość od wierzchołka v do wierzchołka u - długość najkrótszej ścieżki od u do v (przyjmujemy jeśli v nie jest osiągalny z u ) Podgraf grafu G=(V, E) : graf H=(V', E') taki, że V' V, E' E Podgraf indukowany grafu G=(V, E) : graf H=(V', E') taki, że V' V, E' = {(u, v) E: u, v V' } Definicje – dla grafu niezorientowanego G=(V, E) : G jest spójny : każdy wierzchołek jest osiągalny z każdego wierzchołka Spójna składowa grafu G : maksymalny podgraf indukowany H taki, że H jest spójny G jest drzewem: gdy G jest spójny i nie zawiera cykli (często z wyróżnionym wierzchołkiem zwanym korzeniem) Drzewo rozpinające dla spójnego niezorientowanego grafu G=(V,E): drzewo T=(V', E') takie, że V'=V, E' E , czyli podgraf bez cykli, łączący wszystkie wierzchołki Definicje - dla grafu zorientowanego : G jest silnie spójny : gdy każdy wierzchołek jest osiągalny z każdego wierzchołka Silnie spójna składowa grafu G: maksymalny podgraf indukowany H taki, że H jest silnie spójny IIUJ Metody Programowania strona: 5 Reprezentacja grafu w Javie W większości zastosowań praktycznych wierzchołek reprezentuje pewien obiekt odpowiedniej klasy. W wierzchołkach przechowujemy zwykle label (etykietę) typu znakowego oraz informację reprezentowaną przez zmienną wasVisited (był odwiedzony) typu logicznego. Zatem klasa wierzchołek ma postać: class Vertex { public char label; // etykieta , np.’A’ public boolean wasVisited; // czy był odwiedzony public Vertex(char lab) // konstruktor { label = lab; wasVisited = false; // nie był odwiedzony } } // end class Vertex Obiekty klasy Vertex mogą być umieszczane w tablicy i mogą być wywoływane przy użyciu numeru indeksu. W przykładowym programie użyjemy tablicy o nazwie vertexList . Wierzchołki można również przechowywać jako listę lub inną strukturę, przy czym typ struktury nie jest powiązany z systemem łączenia wierzchołków za pomocą krawędzi. Do zapamiętania krawędzi grafu można użyć macierze sąsiedztwa lub listy sąsiedztwa w reprezentacji wiązanej. Poniżej podano definicję klasy graph, w której do zapamiętania krawędzi użyto macierzy sąsiedztwa – adjMat [ ] [ ]. class Graph{ private int MAX_VERTS = 20; private Vertex vertexList[]; // lista wierzchołków private int adjMat[ ][ ]; // macierz sąsiedztwa private int nVerts; // bieżąca liczba wierzchołków // ------------------------------------------------------------------------------------------------- public Graph() { // konstruktor vertexList = new Vertex[MAX_VERTS]; // tablica wierzchołków adjMat = new int[MAX_VERTS][MAX_VERTS]; // macierz sąsiedztwa nVerts = 0; // liczba węzłów for(int j=0; j < MAX_VERTS; j++) // zerowanie macierzy sąsiedztwa for(int k=0; k<MAX_VERTS; k++) adjMat[ j ][ k ] = 0; } // end constructor [ Pobierz całość w formacie PDF ] |