obrazek obrazekobrazek
obrazek
Prezentowane materiały są przeznaczone dla uczniów szkół ponadgimnazjalnych.
Autor artykułu: mgr Jerzy Wałaszek,  wersja1.0

 ©2008 mgr Jerzy Wałaszek
I LO w Tarnowie

obrazek

Teoria grafów dla początkujących

Reprezentacja grafów w pamięci komputera

Pojęcie grafu

Graf (ang. graph) jest strukturą danych zbudowaną z wierzchołków (ang. vertex):

 

obrazek

 

oraz z łączących te wierzchołki krawędzi (ang. edge):

 

obrazek

 

W celu identyfikacji wierzchołki grafu zwykle numerujemy od 1 do n, gdzie n oznacza liczbę wierzchołków. Sposób numeracji jest dowolny, lecz czasem ma znaczenie:

 

obrazek

 

Umawiamy się, iż w strukturze grafu przechodzimy od wierzchołka do wierzchołka tylko wzdłuż łączących te wierzchołki krawędzi. Na przykład w naszym grafie możemy bezpośrednio przejść z wierzchołka nr 1 tylko do wierzchołka nr 3 i nr 5. Do pozostałych wierzchołków możemy dojść, ale nie bezpośrednio. Wierzchołki, które łączą się krawędzią z danym wierzchołkiem nazywamy jego sąsiadami lub wierzchołkami sąsiednimi.

Rodzaje grafów

Ze względu na własności krawędzi rozróżniamy kilka rodzajów grafów:

    obrazek

obrazek

obrazek

 

Matematyczna reprezentacja grafu

W matematyce graf przedstawiany jest jako para zbiorów:

G = (V,E)

V - zbiór wierzchołków
E - zbiór krawędzi

Zbiór wierzchołków V może składać się z numerów wierzchołków:

obrazek V = {1,2,3,4,5,6,7}

   

Zbiór krawędzi E to zbiór par wierzchołków ze zbioru V, które połączone są w grafie krawędzią:

obrazek E = {(1,3),(1,5),(2,3),(2,5),(2,6),(3,4),(3,6),(4,5),(4,7),(6,7)}

Jeśli graf jest grafem nieskierowanym, to pary w zbiorze krawędzi E mogą zawierać wierzchołki w dowolnym porządku. W grafie skierowanym wierzchołki w parze są uporządkowane zgodnie z kierunkiem krawędzi. Pierwszy wierzchołek jest wierzchołkiem wyjściowym, a drugi jest wierzchołkiem docelowym:

obrazek E = {(1,3),(2,3),(3,4),(3,6),(4,5),(4,7),(5,1),(5,2),(6,2),(7,6)}

Jeśli mamy do czynienia z grafem ważonym, to zbiór krawędzi E tworzą trójki. W każdej trójce dwa pierwsze elementy określają wierzchołki połączone krawędzią, a trzeci element określa wagę tej krawędzi:

obrazek E = {(1,3,3),(2,3,5),(3,4,1),(3,6,3),(4,5,3),(4,7,4),(5,1,2),(5,2,1),(6,2,5),(7,6,9)}

Multigraf reprezentujemy zbiorem krawędzi E, w którym pary wierzchołków mogą się powtarzać oraz para może być złożona z tego samego wierzchołka:

obrazek E = {(1,3),(1,3),(1,5),(2,3),(2,3),(2,5),(2,5),(2,6),(3,4),(3,6),(3,6),(4,4),(4,5),(4,7),(6,6),(6,7),(6,7),(6,7)}

Komputerowa reprezentacja grafu

Wymyślono wiele sposobów reprezentowania grafów w pamięci komputera. My opiszemy dwa - macierz sąsiedztwa (ang. adjacency matrix) oraz listy sąsiedztwa (ang. adjacency list).

Macierz sąsiedztwa

Tworzymy kwadratową macierz o wymiarze n × n, gdzie n oznacza liczbę wierzchołków w grafie. Numery wierszy oraz kolumn tej macierzy odpowiadają numerom wierzchołków w grafie. Dane dwa wierzchołki są połączone krawędzią, jeśli na przecięciu wiersza o numerze pierwszego wierzchołka i kolumny o numerze drugiego wierzchołka komórka macierzy przechowuje wartość 1. Dwa wierzchołki nie są połączone krawędzią, jeśli na przecięciu ich wiersza i kolumny mamy 0.

Dla grafu skierowanego macierz sąsiedztwa wygląda następująco:

obrazek
  1 2 3 4 5 6 7
1 0 0 1 0 0 0 0
2 0 0 1 0 0 0 0
3 0 0 0 1 0 1 0
4 0 0 0 0 1 0 1
5 1 1 0 0 0 0 0
6 0 1 0 0 0 0 0
7 0 0 0 0 0 1 0

Wiersze traktujemy jako wierzchołki wyjściowe.

Kolumny traktujemy jako wierzchołki docelowe.

Wiersz nr 4 odnosi się do wierzchołka 4. Widzimy, iż w kolumnach 5 i 7 znajduje się wartość 1. Oznacza to, iż wierzchołek 4 łączą dwie krawędzie z wierzchołkami 5 i 7 (sprawdź na rysunku).

Kolumna nr 4 odnosi się również do wierzchołka nr 4, lecz teraz traktowanego jako wierzchołek docelowy krawędzi. W kolumnie tej 1 występuje tylko w wierszu nr 3. Oznacza to, iż wierzchołek nr 4 jest końcem krawędzi rozpoczynającej się w wierzchołku nr 3.

Graf nieskierowany posiada krawędzie, które można przebywać w obu kierunkach. Możemy go potraktować jako graf skierowany, w którym mamy po dwie krawędzie skierowane w odwrotnych kierunkach:

obrazek = obrazek

Dzięki takiemu podejściu wykorzystujemy macierz sąsiedztwa do reprezentacji grafu nieskierowanego - dla danych dwóch wierzchołków v1 i v2, które w grafie nieskierowanym łączy krawędź, umieszczamy 1 w macierzy sąsiedztwa na przecięciu wiersza v1 i kolumny v2 (krawędź z v1 do v2) oraz na przecięciu wiersza v2 i kolumny v1 (krawędź "odwrotna" z v2 do v1). W ten sposób w grafie istnieje droga w obu kierunkach pomiędzy tymi dwoma wierzchołkami.

obrazek
  1 2 3 4 5 6 7
1 0 0 1 0 1 0 0
2 0 0 1 0 1 1 0
3 1 1 0 1 0 1 0
4 0 0 1 0 1 0 1
5 1 1 0 1 0 0 0
6 0 1 1 0 0 0 1
7 0 0 0 1 0 1 0

Zauważ, iż dla grafu nieskierowanego macierz sąsiedztwa jest symetryczna względem głównej przekątnej.

Graf ważony możemy przedstawić dwoma macierzami - macierzą sąsiedztwa, w której umieszczamy informacje o ścieżkach - oraz macierzą wag ścieżek o takiej samej budowie jak macierz sąsiedztwa. Jeśli mamy pewność, iż wagi ścieżek nigdy nie są zerowe, to zamiast dwóch macierzy możemy użyć tylko jednej macierzy sąsiedztwa, w której umieszczamy zamiast jedynek wagi ścieżek.

obrazek
  1 2 3 4 5 6 7
1 0 0 3 0 0 0 0
2 0 0 5 0 0 0 0
3 0 0 0 1 0 3 0
4 0 0 0 0 3 0 4
5 2 1 0 0 0 0 0
6 0 5 0 0 0 0 0
7 0 0 0 0 0 9 0
 

Multigraf przedstawiamy macierzą sąsiedztwa, w której komórkach umieszczamy informację o liczbie ścieżek łączących wierzchołki.

obrazek
  1 2 3 4 5 6 7
1 0 0 2 0 1 0 0
2 0 0 2 0 2 1 0
3 2 2 0 1 0 2 0
4 0 0 1 1 1 0 1
5 1 2 0 1 0 0 0
6 0 1 2 0 0 1 3
7 0 0 0 1 0 3 0
 

Zwróć uwagę, iż w przypadku multigrafu główna przekątna macierzy może zawierać elementy niezerowe - są to krawędzie-pętle, które łączą dany wierzchołek z nim samym. W naszym przypadku tak jest dla wierzchołków nr 4 i nr 6.

 

Definicję grafu przekazuje się do komputera najczęściej podając liczbę krawędzi, po której następują pary wierzchołków połączonych krawędzią w grafie. Dla przykładowego grafu wygląda to tak:

obrazek            10
1 3
1 5
2 3
2 5
2 6
3 4
3 6
4 5
4 7
6 7

Program

Poniższy program odczytuje z konsoli znakowej definicję grafu nieskierowanego definicję grafu podaną za pomocą krawędzi jak wyżej. Liczba wierzchołków jest ograniczona do 32. Następnie dla każdego wierzchołka grafu program wypisuje wszystkich jego sąsiadów.

 

Uwaga: Wszystkie programy są tworzone w środowisku Dev-C++.

 

// Kurs teorii grafów dla początkujących
//(C)2009 I LO w Tarnowie
//--------------------------------------

#include <iostream>

using namespace std;

const int VMAX = 32;  // maksymalna liczba wierzchołków

// Macierz sąsiedztwa tworzymy o wymiarach o 1 większych,
// aby zapewnić numerację wierszy i kolumn od 1 do VMAX.
// Jeśli chcemy oszczędzać pamięć, to należy stosować
// numerację wierzchołków od 0 do VMAX-1.
//-------------------------------------------------------

bool AM[VMAX+1][VMAX+1]; // macierz sąsiedztwa

int n; // faktyczna liczba wierzchołków w grafie
int m; // liczba krawędzi

// Funkcja zeruje macierz sąsiedztwa
//----------------------------------

void zero_AM()
{
  for(int i = 1; i <= VMAX; i++)
    for(int j = 1; j <= VMAX; j++)
      AM[i][j] = false;
}

// Funkcja odczytuje definicję grafu
// ze standardowego wejścia
//----------------------------------

void read_AM()
{
  n = 0;
  cin >> m;
  for(int i = 0; i < m; i++)
  {
    int v1,v2;
    cin >> v1 >> v2;
    if(v1 > n) n = v1;
    if(v2 > n) n = v2;
    AM[v1][v2] = AM[v2][v1] = true;        
  }
}

// Funkcja wypisuje sąsiadów każdego wierzchołka
//----------------------------------------------

void show_neighbours()
{
  for(int i = 1; i <= n; i++)
  {
    cout << i << ": ";
    for(int j = 1; j <= n; j++)
      if(AM[i][j]) cout << j << " ";
    cout << endl;
  }
}

// Program główny
//---------------

main()
{
  zero_AM();         // zerujemy macierz sąsiedztwa
  read_AM();         // wczytujemy definicję grafu
  cout << endl;
  show_neighbours(); // wyświetlamy sąsiadów
  cout << endl << endl;
  system("PAUSE");
}
10
1 3
1 5
2 3
2 5
2 6
3 4
3 6
4 5
4 7
6 7

1: 3 5
2: 3 5 6
3: 1 2 4 6
4: 3 5 7
5: 1 2 4
6: 2 3 7
7: 4 6

Zadania

Zadanie 1

Napisz analogiczne programy dla grafu skierowanego i multigrafu.

 

Zadanie 2

Napisz program, który wczyta definicję grafu skierowanego, a następnie dla każdego wierzchołka wyświetli wszystkie wierzchołki, dla których ten wierzchołek jest wierzchołkiem docelowym łączącej je krawędzi.

 

Zadanie 3

Ważony graf skierowany definiujemy następująco:

Pierwsza liczba określa ilość krawędzi w grafie.

Następnie występuje tyle trójek liczb ile wynosiła pierwsza liczba. W każdej trójce dwie pierwsze liczby określają kolejno numer wierzchołka wyjściowego i numer wierzchołka docelowego krawędzi. Trzecia liczba jest wagą tej krawędzi.

Graf może posiadać maksymalnie 32 wierzchołki.

Przykładowe dane są następujące:

obrazek            8
1 2 1
1 5 3
2 3 2
2 5 2
3 4 2
4 1 4
4 5 5
5 3 6

Napisz program, który dla każdego wierzchołka grafu wyliczy różnicę sumy wag krawędzi wchodzących do wierzchołka  i sumy wag krawędzi wychodzących z wierzchołka. Wyniki nanieś na rysunek grafu.

 Listy sąsiedztwa

Reprezentacja grafu macierzą sąsiedztwa jest bardzo prosta, lecz pamięciożerna. Macierz wymaga pamięci rzędu O(n2), gdzie n oznacza liczbę wierzchołków w grafie. Macierz w czasie O(1) daje odpowiedź na pytanie, czy wierzchołek v łączy się z wierzchołkiem u - wystarczy sprawdzić komórkę w wierszu v i kolumnie u. Jednakże wyszukiwanie wszystkich sąsiadów wierzchołka v wymaga przeglądnięcia całego wiersza, zatem ma złożoność O(n).

Przy przetwarzaniu grafów stosuje się często inną reprezentację. Tworzy się tablicę list - czyli tablicę, której elementami są listy. Tablica posiada tyle elementów ile w grafie jest wierzchołków. Zatem poszczególne elementy tablicy odpowiadają poszczególnym wierzchołkom grafu. Na liście wierzchołka umieszcza się numery wierzchołków, które są połączone krawędzią z tym wierzchołkiem. Tablice list nazywamy listami sąsiedztwa (ang. Adjancency Lists).

Graf skierowany:

obrazek      
1: 3  
2: 3  
3: 4 6
4: 5 7
5: 1 2
6: 2  
7: 6  

Graf nieskierowany - każdą krawędź traktujemy jako dwie krawędzie skierowane przeciwnie:

obrazek      
1: 3 5    
2: 3 5 6  
3: 1 2 4 6
4: 3 5 7  
5: 1 2 4  
6: 2 3 7  
7: 4 6    

Multigraf - w reprezentacji listami sąsiedztwa krawędzie mogą się w naturalny sposób powtarzać - na liście po prostu umieszczamy wierzchołek docelowy tyle razy, ile jest do niego krawędzi z danego wierzchołka wyjściowego. Nie występuje także żaden problem dla pętli.

obrazek      
1: 3 3 5        
2: 3 3 5 5 6    
3: 1 1 2 2 4 6 6
4: 3 4 5        
5: 1 2 2 4      
6: 2 3 3 6 7 7 7
7: 4 6 6 6      

Graf ważony - elementy list sąsiedztwa są dwuskładnikowe. Pierwszy składnik jest numerem wierzchołka docelowego krawędzi, a drugi składnik jest wagą tej krawędzi.

obrazek      
1: (3,3)  
2: (3,5)  
3: (4,1) (6,3)
4: (5,3) (7,4)
5: (1,2) (2,1)
6: (2,5)  
7: (6,9)  

W porównaniu z macierzami sąsiedztwa listy sąsiedztwa są bardziej efektywne pamięciowo - złożoność klasy O(m), gdzie m oznacza liczbę krawędzi grafu. Listy sąsiedztwa nadają się doskonale do zapamiętywania dużych grafów. Szybciej uzyskujemy dostęp do sąsiadów danego wierzchołka - mamy ich przecież bezpośrednio na liście. Jednakże sprawdzenie, czy dane dwa wierzchołki u i v łączy krawędź wymaga przejrzenia list sąsiedztwa wierzchołka v i u, nie jest to zatem operacja wykonywana w czasie stałym.

Program

Poniższy program odczytuje z konsoli znakowej definicję grafu nieskierowanego definicję grafu podaną za pomocą krawędzi jak wyżej. Liczba wierzchołków jest ograniczona do 32. Następnie dla każdego wierzchołka grafu program wypisuje wszystkich jego sąsiadów.

 

Uwaga: Wszystkie programy są tworzone w środowisku Dev-C++.

 

// Kurs teorii grafów dla początkujących
//(C)2009 I LO w Tarnowie
//--------------------------------------

#include <iostream>
#include <list>

using namespace std;

const int VMAX = 32;  // maksymalna liczba wierzchołków

// Tablicę list sąsiedztwa tworzymy o wymiarze o 1 większym od VMAX,
// aby zachować numerację wierzchołków od 1 do VMAX

list<int> AL[VMAX+1];  // tablica list sąsiedztwa

int n; // faktyczna liczba wierzchołków w grafie
int m; // liczba krawędzi


// Funkcja odczytuje definicję grafu
// ze standardowego wejścia
//----------------------------------

void read_AL()
{
  n = 0;
  cin >> m;
  for(int i = 0; i < m; i++)
  {
    int v1,v2;
    cin >> v1 >> v2;
    if(v1 > n) n = v1;
    if(v2 > n) n = v2;
    AL[v1].push_back(v2); // v2 umieszczamy na liście wierzchołka v1
    AL[v2].push_back(v1); // v1 umieszczamy na liście wierzchołka v2
  }
}

// Funkcja wypisuje sąsiadów każdego wierzchołka
//----------------------------------------------

void show_neighbours()
{
  for(int i = 1; i <= n; i++)
  {
    cout << i << ": ";
    for(list<int>::iterator j = AL[i].begin(); j != AL[i].end(); j++)
      cout << *j << " ";
    cout << endl;
  }
}

// Program główny
//---------------

main()
{
  read_AL();         // wczytujemy definicję grafu
  cout << endl;
  show_neighbours(); // wyświetlamy sąsiadów
  cout << endl << endl;
  system("PAUSE");
}
10
1 3
1 5
2 3
2 5
2 6
3 4
3 6
4 5
4 7
6 7

1: 3 5
2: 3 5 6
3: 1 2 4 6
4: 3 5 7
5: 1 2 4
6: 2 3 7
7: 4 6

Zadania

Postaraj się wykonać dla reprezentacji listami sąsiedztwa te same zadania co dla reprezentacji macierzą sąsiedztwa.

 

   I Liceum Ogólnokształcące   
im. Kazimierza Brodzińskiego
w Tarnowie
©2024 mgr Jerzy Wałaszek
Dokument ten rozpowszechniany jest zgodnie z zasadami licencji
GNU Free Documentation License.

Pytania proszę przesyłać na adres email: i-lo@eduinf.waw.pl

W artykułach serwisu są używane cookies. Jeśli nie chcesz ich otrzymywać,
zablokuj je w swojej przeglądarce.
Informacje dodatkowe