Serwis Edukacyjny
w I-LO w Tarnowie
obrazek

Materiały dla uczniów liceum

  Wyjście       Spis treści       Wstecz       Dalej  

Autor artykułu: mgr Jerzy Wałaszek

©2024 mgr Jerzy Wałaszek
I LO w Tarnowie

Reprezentacja grafów w komputerze

SPIS TREŚCI
Tematy pomocnicze
Podrozdziały
Do reprezentacji grafów w pamięci komputera wymyślono kilka różnych struktur danych. Każda z nich posiada swoje zalety, lecz również wady. Dlatego należy je rozsądnie dobierać do zadań, w których używamy grafów. Źle dobrana reprezentacja może znacząco wydłużyć czas obliczeń lub rozmiar zajmowanej pamięci. Graf zwykle nie jest strukturą hierarchiczną, jak np. opisane wcześniej drzewa. Jego węzły nie muszą się ze sobą łączyć w określony sposób. Mogą również istnieć grupy węzłów, które nie są w żaden sposób połączone z innymi. Dlatego sposoby reprezentacji drzew niezbyt nadają się do reprezentacji grafów, które powinny zapewniać dostęp do wszystkich wierzchołków bez względu na ich wzajemne połączenia krawędziami. Takie cechy posiadają tablice i macierze. W rozdziale tym omawiamy trzy najczęściej spotykane sposoby przedstawiania grafów: macierz sąsiedztwa (ang. adjacency matrix), macierz incydencji (ang. incidence matrix) oraz listy sąsiedztwa (ang. adjacency lists). Cechą charakterystyczną tych implementacji jest wykorzystanie tablic do przechowywania informacji na temat wierzchołków lub łączących je krawędzi. Wykorzystuje się również struktury mieszane, np. tablicę, której elementami są listy.

Wprowadzanie grafu do pamięci komputera

Chcąc realizować algorytmy grafowe, będziemy zmuszeni wprowadzać różne grafy do pamięci komputera. Istnieje bardzo prosty sposób realizacji tego zadania i jest on następujący:

Na początku podajemy dwie liczby: n – ilość wierzchołków oraz m – ilość krawędzi. Następnie wprowadzamy m par liczb a i b, które definiują kolejne krawędzie grafu, gdzie a to wierzchołek startowy, a b wierzchołek końcowy (dla grafu nieskierowanego kolejność tych wierzchołków nie ma znaczenia). Umówmy się dodatkowo, że wierzchołki w grafie posiadają numery od 0 do n-1. Kolejność numeracji wierzchołków nie ma znaczenia. Dla porządku krawędzie również będą numerowane od 0 do m-1. Dzięki tej umowie uprości się tworzenie struktur danych w językach C++ i Python, gdzie, jak pamiętamy, indeksy tablic rozpoczynają się od 0.

Przykład:
obrazek 5 6 – 5 wierzchołków i 6 krawędzi
0 1 – krawędź e0
1 2 – krawędź e1
2 3 – krawędź e2
3 0 – krawędź e3
1 4 – krawędź e4
3 4 – krawędź e5

Jeśli krawędzie będą posiadały wagi, to wartości tych wag podamy jako trzecią liczbę w definicji krawędzi.

Przykład:
obrazek 5 6 – 5 wierzchołków i 6 krawędzi
0 1   5 – krawędź e0 i jej waga
1 2 -3 – krawędź e1 i jej waga
2 3   0 – krawędź e2 i jej waga
3 0 -1 – krawędź e3 i jej waga
1 4   2 – krawędź e4 i jej waga
3 4   4 – krawędź e5 i jej waga

Jeśli z wierzchołkami grafu zechcemy skojarzyć dane, to po podaniu dwóch pierwszych liczb n i m najpierw przekazujemy do programu n danych dla wierzchołków, a następnie m par (lub trójek) dla poszczególnych krawędzi.

Przykład:
obrazek 5 6 – 5 wierzchołków i 6 krawędzi
5 – dane dla v0
3 – dane dla v1
1 – dane dla v2
6 – dane dla v3
8 – dane dla v4
0 1 – krawędź e0
1 2 – krawędź e1
2 3 – krawędź e2
3 0 – krawędź e3
1 4 – krawędź e4
3 4 – krawędź e5

Na początek:  podrozdziału   strony 

Macierz sąsiedztwa

Graf reprezentujemy za pomocą macierzy kwadratowej A o stopniu n, gdzie n oznacza liczbę wierzchołków w grafie. Macierz taką nazywamy macierzą sąsiedztwa (ang. adjacency matrix). Odwzorowuje ona połączenia wierzchołków krawędziami. Wiersze macierzy sąsiedztwa odwzorowują zawsze wierzchołki startowe krawędzi, a kolumny odwzorowują wierzchołki końcowe krawędzi. Komórka A[i,j], która znajduje się w i-tym wierszu i j-tej kolumnie, odwzorowuje krawędź łączącą wierzchołek startowy vi z wierzchołkiem końcowym vj. Jeśli A[i,j] ma wartość 1, to dana krawędź istnieje. Jeśli A[i,j] ma wartość 0, to wierzchołek vi nie łączy się krawędzią z wierzchołkiem vj.

obrazek obrazek
Przykład:
obrazek
  0 1 2 3 4
0 0 1 0 0 0
1 0 0 1 0 0
2 0 0 0 1 0
3 1 0 0 0 1
4 0 1 0 0 0

Dla grafu nieskierowanego macierz sąsiedztwa A jest symetryczna względem głównej przekątnej, ponieważ jeśli istnieje krawędź od vi do vj (A[i,j] = 1), to również musi istnieć krawędź w kierunku odwrotnym, od vj do vi (A[j,i] = 1).

Przykład:
obrazek
  0 1 2 3 4
0 0 1 0 1 0
1 1 0 1 0 1
2 0 1 0 1 0
3 1 0 1 0 1
4 0 1 0 1 0

Interpretacja zawartości macierzy sąsiedztwa jest bardzo prosta. Poszczególne wiersze traktujemy jako wierzchołki grafu. Zatem wiersz 0 odpowiada wierzchołkowi v0 wiersz 1 odpowiada wierzchołkowi v1, itd. Weźmy dla przykładu wiersz nr 3, który odpowiada wierzchołkowi v3:

  0 1 2 3 4
3 1 0 1 0 1

W kolumnach o numerach 0, 2 i 4 mamy wartości 1. Oznacza to, że wierzchołek v3 jest połączony krawędziami kolejno z wierzchołkami v0, v2 i v4. Wierzchołek v3 jest początkiem tych krawędzi, a wierzchołki v0, v2 i v4 są ich końcami. Z wierzchołka v3 nie wychodzą żadne krawędzie do wierzchołków v1 i v3. Porównaj to z rysunkiem grafu umieszczonym powyżej.

Podobnie jest dla kolumn. Weźmy na przykład kolumnę nr 1, która odpowiada wierzchołkowi v1:

  1
0 1
1 0
2 1
3 0
4 1

W kolumnie mamy wartość 1 w wierszach o numerach 0, 2 i 4. Znaczy to, że wierzchołek v1 jest końcem krawędzi wychodzących z wierzchołków v0, v2 i v4. Do wierzchołka v1 nie dochodzą krawędzie z wierzchołków v1 i v3.

Aby sprawdzić, czy w grafie dane dwa wierzchołki vi i vj są połączone krawędzią, sprawdzamy, czy komórka A[i,j] zawiera wartość 1. Jeśli tak, to dana krawędź istnieje. Zwróć uwagę, że operację tę można wykonać w czasie stałym, zatem dla macierzy sąsiedztwa sprawdzenie połączenia wierzchołków krawędzią ma klasę złożoności obliczeniowej równą O(1). Wadą jest klasa zajętość pamięci równa O(n2), gdzie n oznacza liczbę wierzchołków w grafie. Z drugiej strony komórki macierzy mogą być pojedynczymi bitami.

Z macierzy sąsiedztwa można odczytać wiele pożytecznych informacje. Oto niektóre z nich:

Przykładowe programy

Uwaga:

Zanim uruchomisz program, przeczytaj wstęp do tego artykułu, w którym wyjaśniamy funkcje tych programów oraz sposób korzystania z nich.
Program odczytuje definicję grafu skierowanego, tworzy macierz sąsiedztwa i wypisuje ją w czytelnej formie.
Dane przykładowe
(przekopiuj je do schowka, a następnie wklej do okna konsoli):
obrazek   6 8
0 1
1 2
2 2
1 3
3 1
2 4
4 0
4 3
Pascal
// Macierz sąsiedztwa
// Data: 14.07.2013
// (C)2013 mgr Jerzy Wałaszek
//---------------------------

program adj_matrix;

// Typy dla dynamicznej macierzy
type
  nptr = array of byte;  // Wiersz
  mptr = array of nptr;  // Cała macierz

var
  n, m, i, j, v1, v2 : integer;
  A : mptr = ((0)); // Macierz sąsiedztwa

begin
  // Czytamy liczbę wierzchołków i krawędzi
  read(n, m);
  // Tworzymy tablicę wskaźników
  SetLength(A, n);
  for i := 0 to n-1 do
    // Tworzymy wiersze
    SetLength(A[i], n);
  // Macierz wypełniamy zerami
  for i := 0 to n-1 do
    for j := 0 to n-1 do
      A[i][j] := 0;
  // Odczytujemy kolejne definicje krawędzi
  for i := 1 to m do
  begin
    // Wierzchołek startowy i końcowy krawędzi
    read(v1, v2);
    // Krawędź v1->v2 obecna
    A[v1][v2] := 1;
  end;
  writeln;
  // Wypisujemy zawartość macierzy sąsiedztwa
  write('   ');
  for i := 0 to n-1 do write (i:3);
  writeln;
  writeln;
  for i := 0 to n-1 do
  begin
    write (i:3);
    for j := 0 to n-1 do
      write(A[i][j] :3);
    writeln;
  end;
  // Usuwamy macierz
  for i := 0 to n-1 do
    SetLength(A[i], 0);
  SetLength(A,0);
  writeln;
 end.
C++
// Macierz sąsiedztwa
// Data: 14.07.2013
// (C)2013 mgr Jerzy Wałaszek
//---------------------------

#include <iostream>
#include <iomanip>

using namespace std;

int main()
{
  int n, m, i, j, v1, v2;
  char ** A; // Macierz sąsiedztwa

  // Czytamy liczbę wierzchołków i krawędzi
  cin >> n >> m;
  // Tworzymy tablicę wskaźników
  A = new char * [n];
  for(i = 0; i < n; i++)
    // Tworzymy wiersze
    A[i] = new char [n];
  // Macierz wypełniamy zerami
  for(i = 0; i < n; i++)
    for(j = 0; j < n; j++)
      A[i][j] = 0;
  // Odczytujemy kolejne definicje krawędzi
  for(i = 0; i < m; i++)
  {
    // Wierzchołek startowy i końcowy krawędzi
    cin >> v1 >> v2;
    // Krawędź v1->v2 obecna
    A [v1][v2] = 1;
  }
  cout << endl;
  // Wypisujemy zawartość macierzy sąsiedztwa
  cout << "   ";
  for(i = 0; i < n; i++)
    cout << setw(3) << i;
  cout << endl << endl;
  for(i = 0; i < n; i++)
  {
    cout << setw(3) << i;
    for(j = 0; j < n; j++)
      cout << setw(3) << (int)A[i][j];
    cout << endl;
  }
  // Usuwamy macierz
  for(i = 0; i < n; i++)
    delete [] A[i];
  delete [] A;
  cout << endl;

  return 0;}
Basic
' Macierz sąsiedztwa
' Data: 14.07.2013
' (C)2013 mgr Jerzy Wałaszek
'---------------------------

Dim As Integer n, m, i, j, v1, v2
Dim As Byte Ptr Ptr A

Open Cons For Input As #1

' Czytamy liczbę wierzchołków i krawędzi
Input #1, n, m
' Tworzymy tablicę wskaźników
A = New Byte Ptr [n]
For i = 0 To n-1
  ' Tworzymy wiersze
  A[i] = New Byte [n]
Next
' Macierz wypełniamy zerami
For i = 0 To n-1
  For j = 0 To n-1
    A[i][j] = 0
  Next
Next
' Odczytujemy kolejne definicje krawędzi
For i = 0 To m-1
  ' Wierzchołek startowy i końcowy krawędzi
  Input #1, v1, v2
  ' Krawędź v1->v2 obecna
  A[v1][v2] = 1
Next
Close #1
Print
' Wypisujemy zawartość macierzy sąsiedztwa
Print "   ";
For i = 0 To n-1
  Print Using "###";i;
Next
Print: Print
For i = 0 To n-1
  Print Using "###";i;
  For j = 0 To n-1
  	 Print Using "###";A[i][j];
  Next
  Print
Next
' Usuwamy macierz
For i = 0 To n-1
  Delete [] A[i]
Next
Delete [] A
Print
End
Python (dodatek)
# Macierz sąsiedztwa
# Data: 23.11.2024
# (C)2024 mgr Jerzy Wałaszek
#---------------------------

# Czytamy liczbę wierzchołków i krawędzi
x = input().split()
n = int(x[0])
m = int(x[1])
# Tworzymy macierz a[n][n]
# wypełnioną samymi zerami
a = []
for i in range(n):
    x = [] # Pusty wiersz macierzy
    for j in range(n):
        x.append(0) # Będzie n zer w wierszu
    a.append(x) # Wiersz dołączamy do macierzy
# Odczytujemy kolejne definicje krawędzi
for i in range(m):
    x = input().split() # Dwa wierzchołki
    v1 = int(x[0]) # Start
    v2 = int(x[1]) # Koniec
    a[v1][v2] = 1  # Krawędź v1->v2 obecna
print()
# Wypisujemy zawartość macierzy sąsiedztwa
print("   ", end="")
for i in range(n):
    print("%3d" % i, end="")
print()
print()
for i in range(n):
    print("%3d" % i, end="")
    for j in range(n):
        print("%3d" % a[i][j], end="")
    print()
# Usuwamy macierz
del a
print()
Wynik: 
6 8
0 1
1 2
2 2
1 3
3 1
2 4
4 0
4 3

     0  1  2  3  4  5

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

Zadania dla macierzy sąsiedztwa

  1. Jak zmienić powyższy program, aby traktował dane wejściowe jako graf niekierowany?
  2. Napisz program, który dla danego grafu skierowanego wyznaczy dla każdego wierzchołka wszystkich jego sąsiadów.
  3. Napisz program, który dla danego grafu skierowanego wyznaczy dla każdego wierzchołka wszystkie wierzchołki, dla których jest on sąsiadem.
  4. Napisz program, który dla danego grafu nieskierowanego wyznaczy stopnie wszystkich wierzchołków. Uważaj na pętle!
  5. Napisz program, który dla danego grafu skierowanego wyznaczy stopnie wychodzące i wchodzące wszystkich wierzchołków.
  6. Napisz program, który dla danego grafu skierowanego wyznaczy wszystkie pętle, krawędzie dwukierunkowe oraz wierzchołki izolowane.

Na początek:  podrozdziału   strony 

Macierz incydencji

Macierz incydencji (ang. incidence matrix) jest macierzą A o wymiarze n × m, gdzie n oznacza liczbę wierzchołków grafu, a m liczbę jego krawędzi. Każdy wiersz tej macierzy odwzorowuje jeden wierzchołek grafu. Każda kolumna odwzorowuje jedną krawędź. Zawartość komórki A[i, j] określa powiązanie (incydencję) wierzchołka vi z krawędzią ej w sposób następujący:

obrazek
Przykład:
obrazek
  0 1 2 3 4 5
0 1 0 0 -1 0 0
1 -1 1 0 0 -1 0
2 0 -1 1 0 0 0
3 0 0 -1 1 0 1
4 0 0 0 0 1 -1

Jeśli graf jest nieskierowany, to definicję macierzy można uprościć:

obrazek
Przykład:
obrazek
  0 1 2 3 4 5
0 1 0 0 1 0 0
1 1 1 0 0 1 0
2 0 1 1 0 0 0
3 0 0 1 1 0 1
4 0 0 0 0 1 1

Interpretacja macierzy incydencji jest równie prosta jak interpretacja macierzy sąsiedztwa. Weźmy dla przykładu wiersz nr 3:

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

Wiersz nr 3 skojarzony jest z wierzchołkiem v3 grafu. Wierzchołek v3 jest końcem krawędzi e2 oraz początkiem krawędzi e3 i e5. Nie należy do krawędzi e0, e1 i e4.

Z kolei każda kolumna odwzorowuje jedną krawędź. Weźmy kolumnę nr 2:

  2
0 0
1 0
2 1
3 -1
4 0

Kolumna nr 2 skojarzona jest z krawędzią e2 grafu. Krawędź ta wychodzi od wierzchołka v2 i kończy się w wierzchołku v3.

Macierz incydencji wymaga pamięci o rozmiarze O(m×n). Przydaje się wtedy, gdy algorytm musi posiadać informację o krawędziach (ponieważ przykładowo posiadają one wagi). Pozwala w czasie O(1) sprawdzić, czy wierzchołek vi należy do krawędzi ej. Zwróć uwagę, że macierz incydencji nie nadaje się zbyt dobrze do reprezentacji grafów z pętlami, ponieważ wierzchołek startowy i końcowy muszą być różne. Co prawda, można się umówić na specjalną wartość, np. 2, dla wierzchołka, który jest jednocześnie początkiem jak i końcem krawędzi, lecz komplikuje to przetwarzanie macierzy. Z kolei macierz incydencji bez problemu pozwala reprezentować krawędzie wielokrotne.

Z macierzy incydencji możemy odczytać te same informacje, co z macierzy sąsiedztwa (chociaż czasami wymaga to więcej działań).

Przykładowe programy

Uwaga:

Zanim uruchomisz program, przeczytaj wstęp do tego artykułu, w którym wyjaśniamy funkcje tych programów oraz sposób korzystania z nich.
Program odczytuje definicję grafu skierowanego, tworzy macierz incydencji i wypisuje ją w czytelnej formie.
Dane przykładowe (przekopiuj do schowka i wklej do okna konsoli):
obrazek 6 7
0 1
1 2
1 3
3 1
2 4
4 0
4 3
Pascal
// Macierz incydencji
// Data: 18.07.2013
// (C)2013 mgr Jerzy Wałaszek
//---------------------------

program inc_matrix;

// Typy dla dynamicznej macierzy
type
  nptr = array of shortint; // Wiersz
  mptr = array of nptr;     // Cała macierz

var
  n, m, i, j, v1, v2 : integer;
  A : mptr;

begin
  // Czytamy liczbę wierzchołków i krawędzi
  read(n, m);
  // Tworzymy tablicę wskaźników
  SetLength(A, n);
  for i := 0 to n-1 do
    SetLength (A [i], m); // Tworzymy wiersze
  // Macierz wypełniamy zerami
  for i := 0 to n-1 do
    for j := 0 to m-1 do A [i][j] := 0;
  // Odczytujemy kolejne definicje krawędzi
  for i := 0 to m-1 do
  begin
    // Wierzchołek startowy i końcowy krawędzi
    read(v1, v2);
    A[v1][i] := 1;  // Wierzchołek startowy
    A[v2][i] := -1; // Wierzchołek końcowy
  end;
  writeln;
  // Wypisujemy zawartość macierzy incydencji
  write('   ');
  for i := 0 to m-1 do write (i:3);
  writeln;
  writeln;
  for i := 0 to n-1 do
  begin
    write (i:3);
    for j := 0 to m-1 do write(A[i][j]:3);
    writeln;
  end;
  // Usuwamy macierz
  for i := 0 to n-1 do SetLength(A[i], 0);
  SetLength(A, 0);
  writeln;
end.
C++
// Macierz incydencji
// Data: 18.07.2013
// (C)2013 mgr Jerzy Wałaszek
//---------------------------

#include <iostream>
#include <iomanip>

using namespace std;

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

  // Czytamy liczbę wierzchołków i krawędzi
  cin >> n >> m;
  // Tworzymy tablicę wskaźników
  A = new signed char * [n];

  for(i = 0; i < n; i++)
    // Tworzymy wiersze
    A[i] = new signed char [m];
  // Macierz wypełniamy zerami
  for(i = 0; i < n; i++)
    for(j = 0; j < m; j++) A [i][j] = 0;
  // Odczytujemy kolejne definicje krawędzi
  for(i = 0; i < m; i++)
  {
    // Wierzchołek startowy i końcowy krawędzi
    cin >> v1 >> v2;
    A[v1][i] =  1; // Wierzchołek startowy
    A[v2][i] = -1; // Wierzchołek końcowy
  }
  cout << endl;
  // Wypisujemy zawartość macierzy incydencji
  cout << "   ";
  for(i = 0; i < m; i++)
    cout << setw(3) << i;
  cout << endl << endl;
  for(i = 0; i < n; i++)
  {
    cout << setw(3) << i;
    for(j = 0; j < m; j++)
      cout << setw(3) << (int)A[i][j];
    cout << endl;
  }
  // Usuwamy macierz
  for(i = 0; i < n; i++)
    delete [] A[i];
  delete [] A;
  cout << endl;
  return 0;
}
Basic
' Macierz incydencji
' Data: 18.07.2013
' (C)2013 mgr Jerzy Wałaszek
'---------------------------

Dim As Integer n, m, i, j, v1, v2
Dim As Byte Ptr Ptr A

Open Cons For Input As #1
' Czytamy liczbę wierzchołków i krawędzi
Input #1, n, m
' Tworzymy tablicę wskaźników
A = New Byte Ptr [n]
For i = 0 To n-1
  A[i] = New Byte [m] ' Tworzymy wiersze
Next
' Macierz wypełniamy zerami
For i = 0 To n-1
  For j = 0 To m-1
    A[i][j] = 0
  Next
Next
' Odczytujemy kolejne definicje krawędzi
For i = 0 To m-1
  ' Wierzchołek startowy i końcowy krawędzi
  Input #1, v1, v2
  A[v1][i] =  1 ' Wierzchołek startowy
  A[v2][i] = -1 ' Wierzchołek końcowy
Next
Close #1
Print
' Wypisujemy zawartość macierzy incydencji
Print "   ";
For i = 0 To m-1
  Print Using "###";i;
Next
Print: Print
For i = 0 To n-1
  Print Using "###";i;
  For j = 0 To m-1
    Print Using "###";A[i][j];
  Next
  Print
Next
' Usuwamy macierz
For i = 0 To n-1
  Delete [] A[i]
Next
Delete [] A
Print
End
Python (dodatek)
# Macierz incydencji
# Data: 25.11.2024
# (C)2024 mgr Jerzy Wałaszek
#---------------------------

# Czytamy liczbę wierzchołków i krawędzi
x = input().split()
n = int(x[0])
m = int(x[1])
# Tworzymy macierz
a = []
for i in range(n):
    x = []
    for j in range(m):
        x.append(0)
    a.append(x)
# Odczytujemy kolejne definicje krawędzi
for i in range(m):
    # Wierzchołek startowy i końcowy krawędzi
    x = input().split()
    v1 = int(x[0])
    v2 = int(x[1])
    a[v1][i] =  1  # Wierzchołek startowy
    a[v2][i] = -1  # Wierzchołek końcowy
print()
# Wypisujemy zawartość macierzy incydencji
print("   ", end="")
for i in range(m):
    print("%3d" % i, end="")
print()
print()
for i in range(n):
    print("%3d" % i, end="")
    for j in range(m):
        print("%3d" % a[i][j], end="")
    print()
# Usuwamy macierz
del a
print()
Wynik: 
6 7
0 1
1 2
1 3
3 1
2 4
4 0
4 3

     0  1  2  3  4  5  6

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

Zadania dla macierzy incydencji

  1. Jak zmienić powyższy program, aby traktował dane wejściowe jako graf nieskierowany?
  2. Napisz program, który dla danego grafu skierowanego wyznaczy dla każdego wierzchołka wszystkich jego sąsiadów.
  3. Napisz program, który dla danego grafu skierowanego wyznaczy dla każdego wierzchołka wszystkie wierzchołki, dla których jest on sąsiadem..
  4. Napisz program, który dla danego grafu skierowanego wyznaczy wszystkie krawędzie dwukierunkowe oraz wierzchołki izolowane.

Na początek:  podrozdziału   strony 

Listy sąsiedztwa

Do reprezentacji grafu wykorzystujemy tablicę n elementową A, gdzie n oznacza liczbę wierzchołków. Każdy element tej tablicy jest listą. Lista reprezentuje wierzchołek startowy. Na liście są przechowywane numery wierzchołków końcowych, czyli sąsiadów wierzchołka startowego, z którymi jest on połączony krawędzią. Tablica ta nosi nazwę list sąsiedztwa (ang. adjacency lists).

Przykład:
obrazek
0 1  
1 2  
2 3  
3 0 4
4 1  

W przypadku grafu nieskierowanego listy są dłuższe, ponieważ muszą odzwierciedlać krawędzie biegnące w obu kierunkach.

Przykład:
obrazek
0 1 3  
1 0 4 2
2 1 3  
3 0 2 4
4 1 3  

Listy sąsiedztwa są efektywnym pamięciowo sposobem reprezentacji grafu w pamięci komputera, ponieważ zajmują pamięć rzędu O(m), gdzie m oznacza liczbę krawędzi grafu. Listy sąsiedztwa pozwalają w prosty sposób reprezentować pętle oraz krawędzie wielokrotne, co sprawia, że są bardzo chętnie stosowane w algorytmach grafowych.

Oto kilka podstawowych operacji na listach sąsiedztwa:

Przykładowe programy

Uwaga:

Zanim uruchomisz program, przeczytaj wstęp do tego artykułu, w którym wyjaśniamy funkcje tych programów oraz sposób korzystania z nich.
Program odczytuje definicję grafu skierowanego, tworzy tablicę list sąsiedztwa i wypisuje ją w czytelnej formie. W tablicy są wykorzystywane listy jednokierunkowe.
Dane przykładowe (przekopiuj do schowka i wklej do okna konsoli):
obrazek 6 8
0 1
1 2
2 2
1 3
3 1
2 4
4 0
4 3
Pascal
// Listy sąsiedztwa
// Data: 18.07.2013
// (C)2013 mgr Jerzy Wałaszek
//---------------------------

program inc_matrix;

// Typy dla dynamicznej tablicy list sąsiedztwa

type
  PSLel = ^SLel;
  SLel =  record
    next  : PSLel;
    v     : integer;
  end;
  TList = array of PSLel;

var
  n, m, i, v1, v2 : integer;
  A : TList;
  p, r : PSLel;

begin
  // Czytamy liczbę wierzchołków i krawędzi
  read(n, m);
  // Tworzymy tablicę list sąsiedztwa
  SetLength(A, n);
  // Tablicę wypełniamy pustymi listami
  for i := 0 to n-1 do A[i] := nil;
  // Odczytujemy kolejne definicje krawędzi
  for i := 0 to m-1 do
  begin
    // Wierzchołek startowy i końcowy krawędzi
    read(v1, v2);
    // Tworzymy nowy element listy
    new(p);
    // Numerujemy go jako v2
    p^.v := v2;
    // Dodajemy go na początek listy A[v1]
    p^.next := A[v1];
    A[v1] := p;
  end;
  writeln;
  // Wypisujemy zawartość tablicy list sąsiedztwa
  for i := 0 to n-1 do
  begin
    write ('A[', i, '] =');
    p := A[i];
    while p <> nil do
    begin
      write(p^.v:3);
      p := p^.next;
    end;
    writeln;
  end;
  // Usuwamy tablicę list sąsiedztwa
  for i := 0 to n-1 do
  begin
    p := A[i];
    while p <> nil do
    begin
      r := p;
      p := p^.next;
      dispose (r);
    end;
  end;
  SetLength(A, 0);
  writeln;
end.
C++
// Listy sąsiedztwa
// Data: 18.07.2013
// (C)2013 mgr Jerzy Wałaszek
//---------------------------

#include <iostream>
#include <iomanip>

using namespace std;

// Typy dla dynamicznej tablicy list sąsiedztwa

struct SLel
{
  SLel * next;
  int v;
};

int main()
{
  int n, m, i, v1, v2;
  SLel ** A;
  SLel *p, *r;

  // Czytamy liczbę wierzchołków i krawędzi
  cin >> n >> m;
  // Tworzymy tablicę list sąsiedztwa
  A = new SLel * [n];
  // Tablicę wypełniamy pustymi listami
  for(i = 0; i < n; i++) A[i] = nullptr;
  // Odczytujemy kolejne definicje krawędzi
  for(i = 0; i < m; i++)
  {
    // Wierzchołek startowy i końcowy krawędzi
    cin >> v1 >> v2;
    // Tworzymy nowy element
    p = new SLel;
    // Numerujemy go jako v2
    p->v = v2;
    // Dodajemy go na początek listy A[v1]
    p->next = A[v1];
    A[v1] = p;
  }
  cout << endl;
  // Wypisujemy zawartość tablicy list sąsiedztwa
  for(i = 0; i < n; i++)
  {
    cout << "A[" << i << "] =";
    p = A[i];
    while(p)
    {
      cout << setw(3) << p->v;
      p = p->next;
    }
    cout << endl;
  }
  // Usuwamy tablicę list sąsiedztwa
  for(i = 0; i < n; i++)
  {
    p = A[i];
    while(p)
    {
      r = p;
      p = p->next;
      delete r;
    }
  }
  delete [] A;
  cout << endl;
  return 0;
}
Basic
' Listy sąsiedztwa
' Data: 18.07.2013
' (C)2013 mgr Jerzy Wałaszek
'---------------------------

' Typy dla dynamicznej tablicy
' list sąsiedztwa

Type SLel
  next As SLel Ptr
  v As Integer
End Type

Dim As Integer n, m, i, v1, v2
Dim As SLel Ptr Ptr A
Dim As SLel Ptr p, r

Open Cons For Input As #1
' Czytamy liczbę wierzchołków i krawędzi
Input #1, n, m
' Tworzymy tablicę list sąsiedztwa
A = new SLel Ptr [n]
' Tablicę wypełniamy pustymi listami
For i = 0 To n-1
  A[i] = 0
Next
' Odczytujemy kolejne definicje krawędzi
For i = 0 To m -1
  ' Wierzchołek startowy i końcowy krawędzi
  Input #1, v1, v2
  ' Tworzymy nowy element
  p = new SLel
  ' Numerujemy go jako v2
  p->v = v2
  ' Dodajemy go na początek listy A [v1]
  p->next = A[v1]
  A[v1] = p
Next
Close #1
Print
' Wypisujemy zawartość
' tablicy list sąsiedztwa
For i = 0 To n-1
  Print Using "A[&] =";i;
  p = A[i]
  While p
    Print Using "###";p->v;
    p = p->Next
  Wend
  Print
Next
' Usuwamy tablicę list sąsiedztwa
For i = 0 To n-1
  p = A[i]
  While p
    r = p
    p = p->Next
    Delete r
  Wend
Next
Delete [] A
Print
End
Python (dodatek)
# Listy sąsiedztwa
# Data: 25.11.2024
# (C)2024 mgr Jerzy Wałaszek
#---------------------------

# Klasa elementu list sąsiedztwa
class SLel:
    def __init__(self):
        self.next = None
        self.v = 0

# Czytamy liczbę wierzchołków i krawędzi
x = input().split()
n = int(x[0])
m = int(x[1])
# Tworzymy tablicę list sąsiedztwa
a = [[]] * n
# Odczytujemy kolejne definicje krawędzi
for i in range(m):
    # Wierzchołek startowy i końcowy krawędzi
    x = input().split()
    v1 = int(x[0])
    v2 = int(x[1])
    # Tworzymy nowy element
    p = SLel()
    # Numerujemy go jako v2
    p.v = v2
    # Dodajemy go na początek listy A[v1]
    p.next = a[v1]
    a[v1] = p
print()
# Wypisujemy zawartość tablicy list sąsiedztwa
for i in range(n):
    print("A[",i,"] =", sep="", end="")
    p = a[i]
    while p:
        print("%3d" % p.v, end="")
        p = p.next
    print()
# Usuwamy tablicę list sąsiedztwa
del a
print()
Wynik: 
6 8
0 1
1 2
2 2
1 3
3 1
2 4
4 0
4 3

A[0] =  1
A[1] =  3  2
A[2] =  4  2
A[3] =  1
A[4] =  3  0
A[5] =

Zadania dla list sąsiedztwa

  1. Jak zmienić powyższy program, aby traktował dane wejściowe jako graf nieskierowany?
  2. Napisz program, który dla danego grafu skierowanego wyznaczy dla każdego wierzchołka wszystkie wierzchołki, dla których jest on sąsiadem..
  3. Napisz program, który dla danego grafu nieskierowanego wyznaczy stopnie wszystkich wierzchołków. Uważaj na pętle!
  4. Napisz program, który dla danego grafu skierowanego wyznaczy stopnie wychodzące i wchodzące wszystkich wierzchołków.
  5. Napisz program, który dla danego grafu skierowanego wyznaczy wszystkie pętle, krawędzie dwukierunkowe oraz wierzchołki izolowane.

Na początek:  podrozdziału   strony 
Zespół Przedmiotowy
Chemii-Fizyki-Informatyki
w I Liceum Ogólnokształcącym
im. Kazimierza Brodzińskiego
w Tarnowie
ul. Piłsudskiego 4
©2024 mgr Jerzy Wałaszek

Materiały tylko do użytku dydaktycznego. Ich kopiowanie i powielanie jest dozwolone pod warunkiem podania źródła oraz niepobierania za to pieniędzy.
Pytania proszę przesyłać na adres email: i-lo@eduinf.waw.pl
Serwis wykorzystuje pliki cookies. Jeśli nie chcesz ich otrzymywać, zablokuj je w swojej przeglądarce.

Informacje dodatkowe.