Przykładowe grafy
Rozwiązania zadań 1...5 - macierz sąsiedztwa
Rozwiązania zadań 6...8 - macierz incydencji
Rozwiązania zadań 9...11 - listy sąsiedztwa

Grafy

Podstawowe pojęcia związane z grafami

Graf (ang. graph) jest strukturą zbudowaną z punktów zwanych wierzchołkami (ang. vertex) oraz łączących te punkty krawędzi (ang. edge).

 

obrazek

 

Położenie wierzchołków na płaszczyźnie lub w przestrzeni jest dowolne. Krawędzie symbolizują drogi, którymi możemy się poruszać po grafie. Dla dalszego opisu grafu ponumerujemy wierzchołki i krawędzie (numeracja jest zupełnie dowolna).

 

obrazek

 

Dla powyższego grafu mamy:

Zbiór wierzchołków: V = { v1, v2, v3, v4, v5, v6 }
Zbiór krawędzi: E = { e1, e2, e3, e4, e5, e6, e7 }

 

Zatem graf jest parą dwóch zbiorów: zbioru wierzchołków V oraz zbioru krawędzi E, które łączą te wierzchołki. Zapisujemy ten fakt następująco:

 

G  = (V, E)

 

Jest to zapis matematyczny. Jeśli będziemy chcieli przetwarzać grafy za pomocą komputerów, to będziemy musieli stosować nieco inne przedstawienia grafów, ale o tym napiszemy pod koniec tego rozdziału.

Krawędź grafu łączy ze sobą dwa wierzchołki. Możemy zatem zdefiniować ją jako parę wierzchołków. I tak dla podanego powyżej grafu mamy następujące krawędzie:

 

e1 = (v1, v2)
e2 = (v1, v3)
e3 = (v1, v5)
e4 = (v3, v4)
e5 = (v2, v4)
e6 = (v4, v5)
e7 = (v4, v6)

 

Jeśli krawędź grafu można przechodzić w obie strony (np. krawędzią e1 możemy przejść zarówno od wierzchołka v1 do v2 jak i od v2 do v1), to mówimy, że jest ona nieskierowana (ang. undirected edge). W takim przypadku para (v1, v2) nie jest uporządkowana - kolejność wierzchołków w tej parze nie ma znaczenia. Graf posiadający wszystkie krawędzie nieskierowane nazywamy grafem nieskierowanym (ang. undirected graph). Takim właśnie grafem jest graf z powyższego przykładu.

 

Jeśli kierunek przejścia krawędzi jest określony, to taką krawędź można przechodzić tylko w tym kierunku. Kierunek odwrotny jest niedozwolony. Krawędź z kierunkiem przejścia nazywamy krawędzią skierowaną (ang. directed edge) i na rysunku oznaczamy ją strzałką.

 

obrazek

 

Dla krawędzi skierowanej para definiujących ją wierzchołków jest parą uporządkowaną - tzn. istotna jest kolejność wierzchołków w tej parze. Pierwszy wierzchołek pary jest wierzchołkiem początkowym dla krawędzi, drugi wierzchołek pary jest wierzchołkiem końcowym dla krawędzi. Graf posiadający krawędzie skierowane nazywamy grafem skierowanym (ang. directed graph lub w skrócie digraph). Dla powyższego grafu mamy następujące definicje krawędzi:

 

e1 = (v1, v2)
e2 = (v1, v3)
e3 = (v5, v1)
e4 = (v4, v3)
e5 = (v2, v4)
e6 = (v5, v4)
e7 = (v4, v6)

 

W grafie skierowanym i nieskierowanym mogą występować wielokrotne krawędzie - są to jakby alternatywne drogi, którymi możemy się poruszać po grafie. Mogą również wystąpić tzw. pętle (ang. loop), czyli krawędzie wychodzące z danego wierzchołka i wracające do niego:

 

obrazek

 

Graf o takich cechach nazywamy multigrafem (ang. multigraph). Definicja krawędzi jest następująca:

 

e1 = (v1, v2)
e2 = (v1, v2) - krawędź zdublowana
e3 = (v1, v3)
e4 = (v5, v1)
e5 = (v4, v3)
e6 = (v2, v4)
e7 = (v5, v4)
e8 = (v4, v6)
e9 = (v6, v6) - pętla

 

Stopniem wierzchołka (ang. degree of a vertex) nazywamy liczbę krawędzi, które łączą się z tym wierzchołkiem. Pętle liczymy za 2.

 

obrazek

Dla powyższego grafu wierzchołki posiadają następujące stopnie:

 

deg(v1) = 4
deg(v2) = 3
deg(v3) = 2
deg(v4) = 4
deg(v5) = 2
deg(v6) = 3

 

W grafie skierowanym rozróżniamy dla każdego wierzchołka stopień wchodzący (ang. indegree) - liczba krawędzi kończących się we wierzchołku oraz stopień wychodzący (ang. outdegree) - liczba krawędzi rozpoczynających się we wierzchołku.

 

Może się również zdarzyć, że dany wierzchołek grafu nie jest połączony żadną krawędzią z innymi wierzchołkami. Mówimy wtedy, że jest to wierzchołek izolowany (ang. isolated vertex).

 

obrazek

 

Tutaj wierzchołkiem izolowanym jest wierzchołek v6. Wierzchołek izolowany posiada zawsze stopień 0.

 

Krawędzie grafu mogą posiadać skojarzone ze sobą wagi, jakby koszty przejścia. Wtedy graf nazywamy grafem ważonym (ang. weighted graph) skierowanym lub nieskierowanym:

 

obrazek

Krawędzie grafu ważonego definiujemy za pomocą pary wierzchołków oraz dodatkowego parametru określającego wagę krawędzi:


e1 = ((v1, v2),w1)
e2 = ((v1, v3),w2)
e3 = ((v5, v1),w3)
e4 = ((v4, v3),w4)
e5 = ((v2, v4),w5)
e6 = ((v5, v4),w6)
e7 = ((v4, v6),w7)

 

Kolejne typy grafów oraz ich szczególne własności poznamy na kolejnych zajęciach.

 

Dlaczego grafy są tak ważne w informatyce?

Grafy pozwalają modelować wiele obiektów ze świata rzeczywistego. Oto kilka typowych przykładów:

Wszystko to sprawia, że współczesna informatyka w żaden sposób nie może się obejść bez teorii grafów. Dlatego warto ją poznać już teraz, w szkole średniej. Jedyny warunek to twoja inteligencja i chęć uczenia się. Jeśli to posiadasz, teoria grafów nie będzie taka straszna.

 

Reprezentacja grafów w pamięci komputera

Oczywistym jest, iż chcemy przetwarzać grafy za pomocą komputera. W tym celu musimy określić sposoby umieszczania grafów w pamięci komputerowej. Sposobów tych wymyślono wiele - my wykorzystamy trzy podstawowe:

Każda z tych reprezentacji posiada swoje specyficzne cechy, które ułatwiają w pewnych przypadkach realizację wybranych algorytmów grafowych.

 

Macierz sąsiedztwa

Graf przedstawiamy za pomocą kwadratowej macierzy A o wymiarze n  x n, gdzie n  oznacza liczbę wierzchołków w grafie. Elementami macierzy sąsiedztwa są liczby 0 lub 1. Element ai,j  przyjmuje wartość 1, jeśli wierzchołki vi  oraz vj  łączy w grafie krawędź. Jeśli wierzchołki te nie są połączone krawędzią, element ai,j ma wartość 0.

Na potrzeby języka C++ ponumerujmy wierzchołki od 0 do n-1. Poniższy graf skierowany będzie posiadał następującą definicję w macierzy sąsiedztwa:

 

obrazek
  0 1 2 3 4 5
0 0 1 1 0 0 0
1 0 0 0 1 0 0
2 0 0 0 1 0 0
3 0 0 1 0 0 1
4 1 0 0 1 0 1
5 0 0 0 0 0 1

 

Macierz sąsiedztwa możemy rozumieć również tak: Poszczególne wiersze oznaczają wierzchołki grafu. Numer wiersza jest numerem początkowego wierzchołka krawędzi. Teraz elementy wiersza informują nas, czy ten wierzchołek jest połączony krawędzią z wierzchołkami grafu, których numery określają kolejne kolumny. Na przykład wiersz 0 definiuje wszystkie krawędzie grafu, które rozpoczynają się w wierzchołku 0:

 

  0 1 2 3 4 5
0 0 1 1 0 0 0

 

Z wierzchołka 0 wychodzą krawędzie do wierzchołków 1 i 2. Do pozostałych wierzchołków grafu, 0, 3, 4 i 5, nie ma krawędzi.

 

Zauważ, że reprezentacja grafu za pomocą macierzy sąsiedztwa wymaga zarezerwowania pamięci o rozmiarze O(n2). Dla dużych grafów reprezentacja może być bardzo kosztowna - nawet wykraczająca poza możliwości zwykłego komputera klasy IBM-PC (np. dla n = 1000000 potrzeba 3725 GB RAM!). Zaletą macierzy sąsiedztwa jest stały koszt O(1) sprawdzenia, czy dwa wierzchołki vi  oraz vj  łączy krawędź. W tym celu wystarczy sprawdzić elementy ai,j oraz aj,i. Jeśli jeden z nich jest różny od 0, to krawędź istnieje. Jeśli oba są równe zero, krawędzi brak. Wynika stąd, iż reprezentacja ta jest szczególnie opłacalna w algorytmach, które często muszą sprawdzać występowanie krawędzi pomiędzy wybranymi wierzchołkami grafu, a liczba wierzchołków grafu nie jest zbyt duża.

 

Poniższy program wczytuje ze standardowego wejścia definicję grafu i tworzy dla niego dynamiczną macierz sąsiedztwa. O tworzeniu tablic wielowymiarowych przeczytasz tutaj. Definicja jest następująca:

 

Pierwsze dwie liczby n  i m  określają kolejno liczbę wierzchołków grafu n  (wierzchołki numerujemy kolejno 0, 1, 2, ... n-1) oraz liczbę krawędzi m. Następne m  par liczb definiuje poszczególne krawędzie w grafie. Kolejność podawania krawędzi jest dowolna. Przykładowe dane dla podanego powyżej grafu:

6 10
0 1
0 2
1 3
2 3
3 2
3 5
4 0
4 3
4 5
5 5
 

Code::Blocks
// Reprezentacja grafów w pamięci komputera
// Graf skierowany bez powtórzeń krawędzi
// Macierz sąsiedztwa
// (C)2011 mgr Jerzy Wałaszek
//-----------------------------

#include <iostream>
#include <iomanip>

using namespace std;

int main()
{
  int ** A,n,m,i,j,v1,v2;

  // Odczytujemy n i m

  cin >> n >> m;

  // Dynamicznie tworzymy macierz kwadratową o wymiarze n x n

  A = new int * [n];

  for(i = 0; i < n; i++) A[i] = new int [n];

  // Zerujemy macierz

  for(i = 0; i < n; i++)
    for(j = 0; j < n; j++) A[i][j] = 0;

  // Wczytujemy poszczególne krawędzie i umieszczamy informację o nich w macierzy

  for(i = 0; i < m; i++)
  {
    cin >> v1 >> v2;
    A[v1][v2] = 1;
  }

  // Wyświetlamy macierz sąsiedztwa

  for(i = 0; i < n; i++)
  {
    cout << endl << setw(2) << i << ":";
    for(j = 0; j < n; j++) cout << setw(2) << A[i][j];
  }

  cout << endl << endl;

  // Usuwamy macierz z pamięci komputera

  for(i = 0; i < n; i++) delete [] A[i];
  delete [] A;

  return 0;
}
6 10
0 1
0 2
1 3
2 3
3 2
3 5
4 0
4 3
4 5
5 5

 0: 0 1 1 0 0 0
 1: 0 0 0 1 0 0
 2: 0 0 0 1 0 0
 3: 0 0 1 0 0 1
 4: 1 0 0 1 0 1
 5: 0 0 0 0 0 1

 

Jeśli graf jest grafem nieskierowanym, to każdą wczytaną krawędź (vi, vj) zaznaczamy w elementach ai,j oraz aj,i. Jest tak dlatego, iż krawędź nieskierowaną możemy przejść zarówno od wierzchołka vi do vj, jak i na odwrót, od vj do vi. Otrzymamy symetryczną względem głównej przekątnej macierz sąsiedztwa:

 

obrazek
  0 1 2 3 4 5
0 0 1 1 0 1 0
1 1 0 0 1 0 0
2 1 0 0 1 0 0
3 0 1 1 0 1 1
4 1 0 0 1 0 1
5 0 0 0 1 1 1

 

Różnica w programie jest tylko kosmetyczna i polega na dodaniu jednej instrukcji przypisania. Dane dla programu:

 

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

 

Code::Blocks
// Reprezentacja grafów w pamięci komputera
// Graf nieskierowany bez powtórzeń krawędzi
// Macierz sąsiedztwa
// (C)2011 mgr Jerzy Wałaszek
//-----------------------------

#include <iostream>
#include <iomanip>

using namespace std;

int main()
{
  int ** A,n,m,i,j,v1,v2;

  // Odczytujemy n i m

  cin >> n >> m;

  // Dynamicznie tworzymy macierz kwadratową o wymiarze n x n

  A = new int * [n];

  for(i = 0; i < n; i++) A[i] = new int [n];

  // Zerujemy macierz

  for(i = 0; i < n; i++)
    for(j = 0; j < n; j++) A[i][j] = 0;

  // Wczytujemy poszczególne krawędzie i umieszczamy informację o nich w macierzy
  // Krawędzie wpisujemy do macierzy dwukrotnie, raz dla wierzchołków v1-v2 i 
  // drugi raz dla v2-v1

  for(i = 0; i < m; i++)
  {
    cin >> v1 >> v2;
    A[v1][v2] = A[v2][v1] = 1;
  }

  // Wyświetlamy macierz sąsiedztwa

  for(i = 0; i < n; i++)
  {
    cout << endl << setw(2) << i << ":";
    for(j = 0; j < n; j++) cout << setw(2) << A[i][j];
  }

  cout << endl << endl;

  // Usuwamy macierz z pamięci komputera

  for(i = 0; i < n; i++) delete [] A[i];
  delete [] A;

  return 0;
}
6 10
0 1
0 2
1 3
2 3
3 2
3 5
4 0
4 3
4 5
5 5

 0: 0 1 1 0 0 0
 1: 0 0 0 1 0 0
 2: 0 0 0 1 0 0
 3: 0 0 1 0 0 1
 4: 1 0 0 1 0 1
 5: 0 0 0 0 0 1

 

Problemy:

  1. Zastanów się nad sposobem reprezentacji multigrafu za pomocą macierzy sąsiedztwa. Czy jest to możliwe? Jeśli tak, to co będą zawierały komórki macierzy. Napisz odpowiedni program. Uważaj na pętle, które powinny być zaliczane jako jedna krawędź.

  2. Jak sprawdzić na podstawie macierzy sąsiedztwa, czy graf jest grafem skierowanym lub nieskierowanym.

  3. Napisz program, który w grafie skierowanym zlicza krawędzie tworzące pętle oraz krawędzie, które można przejść w obu kierunkach.

  4. Napisz program, który określa stopnie poszczególnych wierzchołków grafu - pamiętaj, że pętle są liczone za 2.

  5. Napisz program, który wyszukuje w grafie wierzchołki izolowane.

 

Macierz incydencji

Macierz incydencji określa powiązania krawędzi z wierzchołkami grafu. Macierz ta ma wymiar n  wierszy na m  kolumn, gdzie n  oznacza liczbę wierzchołków, a m  jest liczbą krawędzi w grafie. Każdy wiersz macierzy incydencji odwzorowuje wierzchołek grafu. Każda kolumna tej macierzy odwzorowuje krawędź. Numer wiersza macierzy odpowiada numerowi wierzchołka. Numer kolumny odpowiada numerowi krawędzi. Elementy macierzy incydencji mogą przyjąć jedną z 3 wartości, zgodnie z poniższą definicją:

 

obrazek

vi  - i-ty wierzchołek grafu
ej  - j-ta krawędź grafu.

 

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

 

Interpretacja macierzy incydencji jest następująca:

 

Każdy wiersz jest związany z jednym wierzchołkiem grafu. Kolejne elementy we wierszu określają, czy ten wierzchołek należy do danej krawędzi. Jeśli nie, to element w kolumnie o numerze równym numerowi krawędzi jest równy 0. Inaczej mogą wystąpić dwie możliwości. Jeżeli dany element kolumny jest równy 1, to wierzchołek rozpoczyna krawędź o numerze równym numerowi kolumny. Jeśli element jest równy -1, to wierzchołek kończy daną krawędź. Na przykład dla wierzchołka 0 analizujemy wiersz 0 macierzy:

 

  0 1 2 3 4 5 6 7 8
0 -1 1 0 0 -1 0 0 0 0

 

Widzimy, że w kolumnach 0 i 4 mamy wartości -1. Oznacza to, iż krawędzie o numerach 0 i 4 kończą się w wierzchołku 0. W kolumnie 1 mamy wartość 1. Oznacza to, że krawędź nr 1 rozpoczyna się we wierzchołku 0. Pozostałe elementy mają wartość 0, czyli krawędzie o tych numerach nie zawierają wierzchołka 0 ani na początku, ani na końcu.

 

Dane dla programu (powyższy graf)

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

 

Code::Blocks
// Reprezentacja grafów w pamięci komputera
// Graf skierowany
// Macierz incydencji
// (C)2011 mgr Jerzy Wałaszek
//-----------------------------

#include <iostream>
#include <iomanip>

using namespace std;

int main()
{
  int ** A,n,m,i,j,v1,v2;

  // Odczytujemy n i m

  cin >> n >> m;

  // Dynamicznie tworzymy macierz o wymiarze n x m

  A = new int * [n]; // n wierszy

  for(i = 0; i < n; i++) A[i] = new int [m]; // m wyrazów w wierszu

  // Zerujemy macierz

  for(i = 0; i < n; i++)
    for(j = 0; j < m; j++) A[i][j] = 0;

  // Wczytujemy poszczególne krawędzie i umieszczamy informację o nich w macierzy

  for(i = 0; i < m; i++)
  {
    cin >> v1 >> v2;
    A[v1][i] = 1;   // wierzchołek początkowy
    A[v2][i] = -1;  // wierzchołek końcowy
  }

  // Wyświetlamy macierz incydencji

  for(i = 0; i < n; i++)
  {
    cout << endl << setw(2) << i << ":";
    for(j = 0; j < m; j++) cout << setw(3) << A[i][j];
  }

  cout << endl << endl;

  // Usuwamy macierz z pamięci komputera

  for(i = 0; i < n; i++) delete [] A[i];
  delete [] A;

  return 0;
}
6 9
1 0
0 2
2 3
3 1
4 0
3 4
5 3
5 4
5 1

 0: -1  1  0  0 -1  0  0  0  0
 1:  1  0  0 -1  0  0  0  0 -1
 2:  0 -1  1  0  0  0  0  0  0
 3:  0  0 -1  1  0  1 -1  0  0
 4:  0  0  0  0  1 -1  0 -1  0
 5:  0  0  0  0  0  0  1  1  1

 

Reprezentacja grafu macierzą incydencji wymaga O(n  × m) komórek pamięci. W stosunku do macierzy sąsiedztwa zysk może pojawić się wtedy, gdy graf ma dużo więcej wierzchołków niż krawędzi.

Dla grafu nieskierowanego upraszczamy definicję:

 

obrazek

 

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

 

Interpretacja takiej macierzy incydencji jest identyczna jak poprzednio. Nie rozróżniamy tylko wierzchołków początkowych i końcowych krawędzi, ponieważ w grafie nieskierowanym krawędzie można przechodzić w obu kierunkach. Modyfikacja programu dla grafu nieskierowanego jest banalna i pozostawiamy ją czytelnikom.

Macierz incydencji pozwala w prosty sposób przedstawiać krawędzie wielokrotne. Jednakże problemy pojawiają się z pętlami - element wiersza nie może być jednocześnie równy 1 i -1.

Problemy:

  1. Napisz program, który określa dla grafu skierowanego określa stopień wejściowy i wyjściowy każdego wierzchołka.

  2. Napisz program, który wyznacza dla danego grafu skierowanego wszystkie wierzchołki startowe i końcowe. Wierzchołek startowy to taki, z którego tylko wychodzą krawędzie, lecz żadna nie wchodzi. Wierzchołek końcowy to taki, do którego tylko wchodzą krawędzie, lecz żadna nie wychodzi. W grafie może być wiele wierzchołków startowych i końcowych.

  3. Napisz program wykorzystujący macierz incydencji do rozwiązania następującego problemu grafowego:
    Jest pewna grupa n  osób. Poszczególne osoby w tej grupie są ponumerowane od 0 do n-1. Osoby łączy kryterium znajomości: osoby i-ta i j-ta są znajomymi. Dla każdej osoby i-tej w grupie należy wyznaczyć osoby, których osoba i-ta ani jej bezpośredni znajomi nie znają osobiście.

 

Listy sąsiedztwa

Reprezentacja grafu za pomocą list sąsiedztwa jest podobna do reprezentacji macierzą sąsiedztwa. Mamy tablicę n-elementową, gdzie n  oznacza liczbę wierzchołków w grafie. Każdy element tej tablicy jest skojarzony z jednym wierzchołkiem grafu - numer wiersza jest numerem wierzchołka. Elementy tablicy są listami. Na temat list i sposobów ich realizacji dowiesz się z tego artykułu. Listy te zawierają numery wierzchołków w grafie, do których prowadzi z danego wierzchołka krawędź.

 

obrazek
0 2    
1 0    
2 3    
3 1 4  
4 0    
5 1 3 4

 

Kolejność wierzchołków na liście sąsiedztwa nie jest ustalona i może być dowolna.

 

Dane dla programu (powyższy graf)

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

 

Code::Blocks
// Reprezentacja grafów w pamięci komputera
// Graf skierowany
// Listy sąsiedztwa
// (C)2011 mgr Jerzy Wałaszek
//-----------------------------

#include <iostream>
#include <iomanip>
#include <list>

using namespace std;

int main()
{
  int n,m,i,v1,v2;

  // Odczytujemy n i m

  cin >> n >> m;

  // Tworzymy tablicę n pustych list

  list<int> * A;

  A = new list<int> [n];

  // Wczytujemy poszczególne krawędzie i umieszczamy informację o nich na listach

  for(i = 0; i < m; i++)
  {
    cin >> v1 >> v2;

    // Do listy A[v1] dodajemy wierzchołek v2

    A[v1].push_back(v2);
  }

  // Wyświetlamy zawartość tablicy list sąsiedztwa

  cout << endl;

  for(i = 0; i < n; i++)
  {
    cout << setw(2) << i << ":";

    // Za pomocą iteratora przeglądamy listę i-tą

    for(list<int>::iterator it = A[i].begin(); it != A[i].end(); it++)
      cout << " " << * it;

    cout << endl;
  }

  // Usuwamy tablicę list z pamięci komputera

  delete [] A;

  return 0;
}
6 9
1 0
0 2
2 3
3 1
4 0
3 4
5 3
5 4
5 1

 0: 2
 1: 0
 2: 3
 3: 1 4
 4: 0
 5: 3 4 1

 

Jeśli graf jest grafem nieskierowanym, to każda krawędź jest odwzorowywana jako dwie krawędzie skierowane w przeciwnych kierunkach.

 

obrazek
0 1 2 4  
1 0 3 5  
2 0 3    
3 1 2 4 5
4 0 3 5  
5 1 3 4  

 

Zaletą list sąsiedztwa jest oszczędność pamięci komputera - odwzorowywane są tylko istniejące krawędzie. Dostęp do sąsiadów danego wierzchołka jest szybszy niż w przypadku tablicy sąsiedztwa, ponieważ nie musimy sprawdzać kolejnych wierzchołków - lista od razu zawiera gotowych do odczytu sąsiadów.

 

Code::Blocks
// Reprezentacja grafów w pamięci komputera
// Graf nieskierowany
// Listy sąsiedztwa
// (C)2011 mgr Jerzy Wałaszek
//-----------------------------

#include <iostream>
#include <iomanip>
#include <list>

using namespace std;

int main()
{
  int n,m,i,v1,v2;

  // Odczytujemy n i m

  cin >> n >> m;

  // Tworzymy tablicę n pustych list

  list<int> * A;

  A = new list<int> [n];

  // Wczytujemy poszczególne krawędzie i umieszczamy informację o nich na listach

  for(i = 0; i < m; i++)
  {
    cin >> v1 >> v2;

    // Do listy A[v1] dodajemy wierzchołek v2

    A[v1].push_back(v2);

    // Do listy A[v2] dodajemy wierzchołek v1, aby krawędź była obukierunkowa

    if(v1 != v2) A[v2].push_back(v1);
  }

  // Wyświetlamy zawartość tablicy list sąsiedztwa

  cout << endl;

  for(i = 0; i < n; i++)
  {
    cout << setw(2) << i << ":";

    // Za pomocą iteratora przeglądamy listę i-tą

    for(list<int>::iterator it = A[i].begin(); it != A[i].end(); it++)
      cout << " " << * it;

    cout << endl;
  }

  // Usuwamy tablicę list z pamięci komputera

  delete [] A;

  return 0;
}
6 9
1 0
0 2
2 3
3 1
4 0
3 4
5 3
5 4
5 1

 0: 1 2 4
 1: 0 3 5
 2: 0 3
 3: 2 1 4 5
 4: 0 3 5
 5: 3 4 1

 

Problemy:

  1. Napisz program, który sprawdza, czy graf zadany listami sąsiedztwa jest grafem nieskierowanym lub skierowanym. Która z reprezentacji grafów jest dla tego zadania najlepsza?

  2. Napisz program, który wyszukuje w grafie skierowanym wszystkie wierzchołki o najwyższym stopniu. Graf zadany jest listami sąsiedztwa.

  3. Mamy graf nieskierowany, który reprezentuje zbiór osób oraz informację o tym, które osoby ze sobą współpracują. Graf zadany jest listami sąsiedztwa. Napisz program, który wyszuka wszystkie różne trójki współpracujących nawzajem osób.

 


   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