algorytm.org

Grafy i ich reprezentacje



Baza Wiedzy
wersja offline serwisu przeznaczona na urządzenia z systemem Android
Darowizny
darowiznaWspomóż rozwój serwisu
Nagłówki RSS
Artykuły
Implementacje
Komentarze
Forum
Bookmarki






Sonda
Implementacji w jakim języku programowania poszukujesz?

Grafy i ich reprezentacje
Ocena użytkowników:***** / 146
SłabyŚwietny 
Wpisany przez Michał Knasiecki, 28 lipca 2005 23:11

Na początek kilka definicji:
W informatyce grafem nazywamy strukturę G=(V, E) składającą się z węzłów (wierzchołków, oznaczanych przez V) wzajemnie połączonych za pomocą krawędzi (oznaczonych przez E).
Grafy dzielimy na grafy skierowane i nieskierowane:
Graf nieskierowany Graf skierowany
Rys.1. Graf nieskierowany Rys.2. Graf skierowany

Jeśli krawędź łączy dwa wierzchołki to jest z nimi incydentna.
Pętla własna to krawędź łączące wierzchołek z samym sobą.
Stopień wierzchołka w grafie nieskierowanym to liczba incydentnych z nim krawędzi.
Istnieje kilka algorytmów do przechowania grafu w pamięci.
Omówmy najpierw macierz sąsiedztwa.
Budujemy tablicę o rozmiarach V*V, gdzie V-liczba wierzchołków. Następnie wypełniamy ją zerami- jeśli dwa wierzchołki nie są połączone krawędzią i jedynkami- jeśli dwa wierzchołki są połączone. Oto macierz sąsiedztwa dla grafu z rysunku 1:
  1 2 3 4 5
1 0 1 1 0 1
2 1 0 1 1 1
3 1 1 0 1 0
4 0 1 1 0 1
5 1 1 0 1 0
Złożoność pamięciowa: O(V2)

Widać, że macierz jest symetryczna. Stosując tablicę dynamiczną można więc zmniejszyć rozmiar macierzy do połowy zapisując ją jako macierz dolno-(górno)-trójkątną.
Lista incydencji.
Należy utworzyć listę dla każdego wierzchołka v, w której przechowujemy zbiór wierzchołków połączonych krawędzią z v. Lista dla grafu z rysunku 1 wygląda następująco:
1: 2, 3, 5
2: 1, 3, 4
3: 1, 2, 4
4: 2, 3, 5
5: 4, 1    
Złożoność pamięciowa: O(V+E)


Lista krawędzi jest to lista, na której przechowujemy wszystkie krawędzie występujące w grafie.
Przykład dla grafu skierowanego z rys.2:
  • 1 - 2
  • 2 - 4
  • 2 - 5
  • 3 - 1
  • 3 - 2
  • 4 - 3
  • 5 - 1
  • 5 - 4
Zapisując przy pomocy tej reprezentacji graf, w którym występują krawędzie skierowane i nieskierowane należy w przypadku krawędzi nieskierowanej z u do v zapisać krawędź dwukrotnie: u - v oraz v - u.

Złożoność pamięciowa: O(E)


Macierz incydencji to tablica o rozmiarach V*E. Składa się ona z E kolumn i V wierszy, jeśli krawędź wychodzi z danego wierzchołka to piszemy w odpowiedniej kolumnie (-1), jeśli do niego wchodzi piszemy (+1), jeśli wierzchołek nie należy do krawędzi piszemy 0, jeśli jest to pętla własna piszemy 2.
Oto przykład dla grafu z rys. 2.
 12345
1 - 2-11000
1 - 310-100
1 - 51000-1
2 - 40-1010
2 - 50-1001
2 - 301-100
3 - 4001-10
5 - 11000-1
5 - 40001-1
Złożoność pamięciowa: O(E*V)

Macierz grafu została opracowana w Instytucie Informatyki PP przez dr M. Sternę. Jest to trochę bardziej skomplikowana reprezentacja grafu niż poprzednie.
Należy utworzyć tablicę o rozmiarach (V+2)2. Wiersze i kolumny numerujemy od 0 do V+1. Najpierw zajmiemy się częścią macierzy ograniczoną przez indeksy od 1 do V.Zał. że w wierszach mamy i-te wierzchołki a w kolumnach j-te wierzchołki. Liczby, które mogą znaleźć się na skrzyżowaniu wierzchołka i oraz j można podzielić na 3 grupy:
  • od 1 do V - istnieje krawędź skierowana: i <- j
  • od V+1 do 2*V - istnieje krawędź skierowana: i -> j
  • od (-V) do (-1) - brak incydentnych krawędzi
Cały sekret macierzy grafu polega jednak na tym, że odczytana wartość nie tylko informuje nas, czy istnieje krawędź łącząca wierzchołki i oraz j, ale zawiera też adres następnego wierzchołka, który jest w takiej samej relacji z wierzchołkiem i co wierzchołek j.
Podam teraz kilka przykładów dla grafu z rys. 2. Liczba wierzchołków jest równa 5. Prześledzimy sytuację dla wierzchołka 1. w grafie mamy następujące krawędzie zawierające ten wierzchołek:
  • 1 -> 2
  • 1 <- 3
  • 1 <- 5
Weźmy pierwszą krawędź: wierzchołek 2 jest jedynym następnikiem wierzchołka 1, więc w macierzy w komórce [1,2] musimy podać adres wierzchołka 2. Aby obliczyć adres wierzchołka nr. 2 (mamy do czynienia z następnikiem) wystarczy dodać do niego liczbę wierzchołków w grafie: 2+5=7. Taką liczbę zapisujemy w komórce [1,2].
Przejdźmy do krawędzi drugiej: wierzchołek 3 jest poprzednikiem wierzchołka 1, ale (w przeciwieństwie do następników) nie jedynym: także wierzchołek 5 jest poprzednikiem wierzchołka 1 (ostatnia krawędź na naszej liście). W komórce [1,3] musimy więc podać adres wierzchołka 5. Ponieważ jest to poprzednik, więc adresem wierzchołka 5 jest 5.
Przechodzimy do ostatniej krawędzi: wierzchołek 5 jest poprzednikiem wierzchołka, ponieważ jest jego ostatnim poprzednikiem (pierwszym był wierzchołek 3) w komórce [1,5] podajemy adres wierzchołka 5, czyli znów wpisujemy 5.
W naszej macierzy musimy podać także wierzchołki, które nie są połączone z wierzchołkiem 1 krawędzią. Punktem wyjściowym listy tych wierzchołków dla każdego wierzchołka i jest on sam (stąd: macierz grafu nie nadaje się dla grafów z pętlami własnymi), lista ta zaczyna się więc w komórce [i,i]. A więc wiemy, że wierzchołek 1 nie jest połączony krawędzią ze sobą samym oraz wierzchołkiem 4. W komórce [1,1] musimy podać adres wierzchołka 4, z godnie z tyum co napisałem powyżej, adresy wierzchołków, które nie są połączone z danym wierzchołek podaje się poprzedzając numer wierzchołka znakiem "-". Więc w komórce [1,1] piszemy (-4). Jednocześnie wierzchołek 4 jest ostatnim wierzchołkiem, z którym nie łączy się wierzchołek 1, więc w komórce [1,4] podajemy znów adres wierzchołka 4, czyli [1,4]=(-4).
Teraz zajmiemy się pozostałą częścią macierzy: kolumną nr. 0 i (V+1) oraz wierszem nr. 0 i (V+1). Bez nich można by już zapisać graf za pomocą macierzy, lecz dzięki nim będziemy mieli dostęp do listy poprzedników i następników w czasie O(E). A więc: komórka [i,0] zawiera pierwszy poprzednik wierzchołka i-tego natomiast komórka [0,i] ostatni poprzednik.
W przykładzie (dotyczącym wierzchołka 1) zapiszemy [1,0]=3, [0,1]=5, ponieważ pierwszym poprzednikiem wierzchołka 1 jest 3 a ostatnim poprzednikiem tego wierzchołka jest 5. Podobnie jest z następnikami: [i,V+1] rozpoczyna listę następników wierzchołka i-tego a [V+1,i] kończy, a więc [1,6]=2, [6,1]=2, gdyż pierwszym i ostatnim następnikiem wierzchołka 1 jest 2. W ten sposób wypełniliśmy pierwszy wiersz macierzy grafu.
Dodam jeszcze, że jeżeli jakiś wierzchołek nie ma następników lub poprzedników to na początku i końcu listy odpowiednio: następników lub poprzedników wpisujemy 0. Poniżej zamieszczam całą macierz dla grafu z rys. 2 (w kolumnach znajdują się wierzchołki j, w wierszach wierzchołki i).
 0123456
0X53452X
13-475-452
213-2310104
3477-54-51
42-158-153
5292-39-31
6X25234X
Dla lepszego zrozumienia macierzy grafu proponuję narysować graf na podstawie macierzy i sprawdzić, czy jest to graf z rys. 2.

Dzięki dodatkowym kolumnom i wierszom zyskujemy listy następników i poprzedników:
  • w kolumnie 0: wskaźnik do pierwszego elementu na liście poprzedników
  • w wierszu 0: wskaźnik do ostatniego elementu na liście poprzedników
  • w kolumnie V+1: wskaźnik do pierwszego elementu na liście następników
  • w wierszu V+1: wskaźnik do ostatniego elementu na liście następników
  • na głównej przekątnej: wskaźnik do pierwszego elementu na liście elementów nie będących ani następnikami ani poprzednikami
Złożoność pamięciowa: O((V+2)2)

Implementacje
AutorJęzyk
programowania
KomentarzOtwórzPobierzOcena
Piotr SkoczylasC/C++Lista incydencji reprezentowana za pomoca typu vector (tablicy dynamicznej).
.cpp
.cpp
***** / 35
 
Dodaj własną implementację tego algorytmu
  • Zaloguj się na stronie
Plik:
Język
programowania:
Komentarz:
  By móc dodać implementacje zaloguj się na stronie

Poprawiony: 29 sierpnia 2012 21:38
Komentarze
photo
+3 # Student 2009-09-11 12:01
Wielkie dzięki:-)!!!
W poniedziałek rozpoczynam kampanie wrześniową i pomogłeś mi zrozumieć istotę macierzy incydencji:-)
Odpowiedz | Odpowiedz z cytatem | Cytować
photo
+2 # . 2009-09-16 14:25
Również składam podziękowania, bo znalazłam nareszcie miejsce, gdzie wszystko jest jasno i krótko wyjaśnione.
Odpowiedz | Odpowiedz z cytatem | Cytować
photo
+1 # Piotr 2010-01-25 17:49
rzeczywiscie jasno i zwiezle wyjasnione
Odpowiedz | Odpowiedz z cytatem | Cytować
photo
+15 # AP 2010-03-06 16:31
Tekst dotyczący reguł wypełniania macierzy grafu jest niezrozumiały. Reguły są nielogiczne albo źle opisane.
Odpowiedz | Odpowiedz z cytatem | Cytować
photo
-4 # Henryk 2010-05-01 07:59
Dziękuję Tu jest jasno prosto i skutecznie
Odpowiedz | Odpowiedz z cytatem | Cytować
photo
+6 # Janek 2010-06-04 14:25
Witam. Mam takie spostrzeżenie i pytanie, bo nie jestem pewien
czy w opisie Macierzy incydencji nie ma 2 błędów. Pierwszy dotyczy fragmentu "...tablica o rozmiarach V*E. Składa się ona z E kolumn i V wierszy..." gdzie powinno być chyba V kolumn i E wierszy jak to zobrazowane jest na rysunku. Drugim błędem jest powtórzenie w tej tablicy dwa razy tej samej krawędzi, a mianowicie 1-5 i 5-1, i przez to wychodzi w tabeli, że jest 9 krawędzi, gdy tak naprawdę jest ich 8. Poprawcie mnie jeśli się mylę
Pozdrawiam.
Odpowiedz | Odpowiedz z cytatem | Cytować
photo
+4 # Oozie 2010-06-24 21:05
"...tablica o rozmiarach V*E. Składa się ona z E kolumn i V wierszy..." - powinno być odwrotnie.

W liście incydencji jest błąd 2: 1, 3, 4 - powinno być 2: 1, 3, 4, 5
oraz 5: 4, 1 - powinno być 5: 4, 2, 1. Wygląda to tak jakby nie istniała krawędź 2-5. Moim zdaniem ten tutorial można dopracować, bo mam wrażenie że był pisany na szybko.

Tak jak wspomniał Janek, macierz incydencji zawiera błąd. Dodatkowo powinna ona być skonstruowana tak że zamiast oznaczać krawędzie numerami wierzchołków, powinny być zastosowane etykiety krawędzi np: e1, e2, e3, ... , e8. Jest to bardziej czytelne, a poza tym czytelnik domyśla się dlaczego krawędź nazywa się 1-2 a nie 2-1.
Odpowiedz | Odpowiedz z cytatem | Cytować
photo
+6 # MCD 2013-06-06 21:18
Właśnie to czytałem i również te błędy zauważyłem. Niestety mimo upływu kilku lat nie poprawiono ich. Ani nikt nie napisał w komentarzu jakiegoś wyjaśnienia, bo może my się mylimy
Odpowiedz | Odpowiedz z cytatem | Cytować
Dodaj komentarz