Serwis Edukacyjny w I-LO w Tarnowie 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 |
ProblemDla danego grafu skierowanego należy znaleźć graf będący jego kwadratem. Kwadrat grafu (ang. square of graph) powstaje z grafu wyjściowego przez dodanie krawędzi pomiędzy wierzchołkami, które w grafie wyjściowym są połączone ścieżką o długości maksymalnie dwóch krawędzi. Innymi słowy, w kwadracie grafu znajduje się krawędź v→u, jeśli w grafie wyjściowym istnieje taka krawędź v→u lub w grafie wyjściowym istnieje wierzchołek w oraz krawędzie v→w i w→u.
Rozwiązanie tego problemu opiera się na prostym spostrzeżeniu: Wierzchołek u staje się sąsiadem
wierzchołka v w kwadracie grafu, jeśli:
Wynika z tego, że nowymi sąsiadami wierzchołka v stają się wszyscy sąsiedzi jego sąsiadów. |
W macierzy sąsiedztwa wierzchołki są reprezentowane przez wiersze, a sąsiedzi tych wierzchołków przez kolumny. Elementy komórek macierzy mogą przyjmować tylko dwie wartości:
A [v, u] = 0, jeśli nie
istnieje w grafie krawędź v→u A [v, u] = 1, jeśli istnieje w grafie krawędź v→u |
Zatem zasada tworzenia macierzy kwadratu grafu jest następująca:
n | : | liczba wierzchołków w grafie, n ∈ C. |
A | : | macierz sąsiedztwa grafu o wymiarach n × n. |
AK | : | macierz sąsiedztwa kwadratu grafu o wymiarach n × n. |
i, j, k | : | indeksy, i, j, k ∈ C. |
K01: | Utwórz macierz AK o wymiarach n × n |
|
K02: | Dla i = 0, 1, …,
n - 1 wykonuj kroki K03…K08 |
przechodzimy przez kolejne wiersze |
K03: | Dla j
= 0, 1, …, n - 1 wykonuj krok K04 |
przechodzimy przez kolejne kolumny |
K04 | AK [i, j] ← A [i, j ] | kopiujemy wiersz wierzchołka bieżącego |
K05: | Dla j
= 0, 1, …, n - 1 wykonuj kroki K06…K08 |
teraz przeglądamy sąsiadów wierzchołka bieżącego |
K06: |
Jeśli (i = 1)
(A [i, j] = 0), to następny obieg pętli K05 |
pomijamy wierzchołki na przekątnej i takie, do których nie prowadzi krawędź |
K07: |
Dla k = 0, 1, …, n - 1 wykonuj krok K08 |
|
K08: |
Jeśli A [j, k] = 1, to AK [i, k] ← 1 |
dołączamy wiersz sąsiada do wiersza bieżącego wierzchołka |
K09: | Zakończ | wynik w AK |
Ponieważ w tym algorytmie występują trzy zagnieżdżone pętle, to ma on klasę złożoności obliczeniowej równą O (n3), gdzie n oznacza liczbę wierzchołków grafu.
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 dla niego macierz sąsiedztwa i oblicza kwadrat grafu, po czym wypisuje wynikową macierz sąsiedztwa w oknie konsoli: |
Dane przykładowe (przekopiuj do
schowka i wklej do okna konsoli):
|
Pascal// Kwadrat grafu // Data: 25.01.2014 // (C)2014 mgr Jerzy Wałaszek //--------------------------- program squaregraph; // Typy dla dynamicznej macierzy type nptr = array of byte; // Wiersz mptr = array of nptr; // Cała macierz var n, m, i, j, k, v1, v2 : integer; A, AK : mptr; begin read (n, m); // Czytamy liczbę wierzchołków i krawędzi SetLength (A, n); // Tworzymy tablice wskaźników SetLength (AK, n); for i := 0 to n - 1 do begin SetLength (A [i], n); // Tworzymy wiersze SetLength (AK [i], n); end; // 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 read (v1, v2); // Wierzchołek startowy i końcowy krawędzi A [v1][v2] := 1; // Krawędź v1->v2 obecna end; writeln; // Obliczamy kwadrat grafu w macierzy AK for i := 0 to n - 1 do begin for j := 0 to n - 1 do AK [i][j] := A [i][j]; for j := 0 to n - 1 do if(i <> j) and (A [i][j] = 1) then for k := 0 to n - 1 do if A [j][k] = 1 then AK [i][k] := 1; end; // Wypisujemy zawartość macierzy sąsiedztwa AK 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 (AK [i][j] :3); writeln; end; // Usuwamy macierze for i := 0 to n - 1 do begin SetLength (A [i], 0); SetLength (AK [i], 0); end; SetLength (A, 0); SetLength (AK, 0); writeln; end. |
// Kwadrat grafu // Data: 25.01.2014 // (C)2014 mgr Jerzy Wałaszek //--------------------------- #include <iostream> #include <iomanip> using namespace std; int main() { int n, m, i, j, k, v1, v2; char ** A, ** AK; cin >> n >> m; // Czytamy liczbę wierzchołków i krawędzi A = new char * [n]; // Tworzymy tablice wskaźników AK = new char * [n]; for(i = 0; i < n; i++) { A [i] = new char [n]; // Tworzymy wiersze AK [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++) { cin >> v1 >> v2; // Wierzchołek startowy i końcowy krawędzi A [v1][v2] = 1; // Krawędź v1->v2 obecna } cout << endl; // Obliczamy kwadrat grafu w macierzy AK for(i = 0; i < n; i++) { for(j = 0; j < n; j++) AK [i][j] = A [i][j]; for(j = 0; j < n; j++) if((i != j) && A [i][j]) for(k = 0; k < n; k++) if(A [j][k]) AK [i][k] = 1; } // Wypisujemy zawartość macierzy sąsiedztwa AK 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) AK [i][j]; cout << endl; } // Usuwamy macierze for(i = 0; i < n; i++) { delete [] A [i]; delete [] AK [i]; } delete [] A; delete [] AK; cout << endl; return 0;} |
Basic' Kwadrat grafu ' Data: 25.01.2014 ' (C)2014 mgr Jerzy Wałaszek '--------------------------- Dim As Integer n, m, i, j, k, v1, v2 Dim As Byte Ptr Ptr A, AK Open Cons For Input As #1 Input #1, n, m ' Czytamy liczbę wierzchołków i krawędzi A = New Byte Ptr [n] ' Tworzymy tablice wskaźników AK = New Byte Ptr [n] For i = 0 To n - 1 A [i] = New Byte [n] ' Tworzymy wiersze AK [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 Input #1, v1, v2 ' Wierzchołek startowy i końcowy krawędzi A [v1][v2] = 1 ' Krawędź v1->v2 obecna Next Close #1 Print ' Obliczamy kwadrat grafu w macierzy AK For i = 0 To n - 1 For j = 0 To n - 1: AK [i][j] = A [i][j] : Next For j = 0 To n - 1 if(i <> j) AndAlso (A [i][j] = 1) Then For k = 0 To n - 1 if(A [j][k] = 1) Then AK [i][k] = 1 Next End If Next Next ' Wypisujemy zawartość macierzy sąsiedztwa AK 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 "###";AK [i][j]; Next Print Next ' Usuwamy macierze For i = 0 To n - 1 Delete [] A [i] Delete [] AK [i] Next Delete [] A Delete [] AK Print End |
Wynik: | |
7 7 0 3 1 0 1 5 5 2 5 4 5 6 6 0 0 1 2 3 4 5 6 0 0 0 0 1 0 0 0 1 1 0 1 1 1 1 1 2 0 0 0 0 0 0 0 3 0 0 0 0 0 0 0 4 0 0 0 0 0 0 0 5 1 0 1 0 1 0 1 6 1 0 0 1 0 0 0 |
Aby utworzyć listy sąsiedztwa dla kwadratu grafu, postępujemy następująco:
Tworzymy n elementową tablicę AK list sąsiedztwa, gdzie n oznacza liczbę wierzchołków w grafie. Tablicę wstępnie wypełniamy pustymi listami. Następnie przechodzimy przez kolejne wierzchołki v grafu. Dla każdego wierzchołka v przeglądamy jego listę sąsiedztwa A [v ]. Dla każdego wierzchołka u na tej liście wstawiamy wierzchołek u na listę AK [v] (czyli dodajemy ten wierzchołek do listy wierzchołka v w tablicy list sąsiedztwa kwadratu grafu). Teraz przeglądamy listę sąsiedztwa A [u] i dodajemy do listy AK [v] każdy wierzchołek z tej listy, którego jeszcze nie ma na liście AK [v] (aby nie dublować krawędzi – jeśli dublowanie krawędzi jest dopuszczalne, to po prostu dodajemy wszystkie wierzchołki z listy A [u] do listy AK [v]).
Gdy algorytm przejdzie wszystkie wierzchołki grafu, w tablicy AK otrzymamy listy sąsiedztwa grafu, który jest kwadratem grafu wyjściowego.
n | : | liczba wierzchołków w grafie, n ∈ C. |
A | : | n elementowa tablica list sąsiedztwa grafu. |
AK | : | n elementowa tablica list sąsiedztwa kwadratu grafu wyjściowego. |
i | : | wierzchołek, i ∈ C. |
p, q, r | : | wskaźniki elementów listy. |
K01: | Utwórz n elementową tablicę list AK |
|
K02: | Tablicę AK wypełnij pustymi listami |
|
K03: | Dla i = 0, 1, …,
n - 1 wykonuj kroki K04…K18 |
przechodzimy przez kolejne wierzchołki grafu |
K04: | p ← A [i] | |
K05: | Dopóki
p ≠ nil, wykonuj kroki K06…K07 |
kopiujemy listę sąsiedztwa A [i] do AK [i] |
K06: | Dodaj (p→v) do listy AK [i ] | |
K07: | p ← (p→next) | następny sąsiad |
K08: | p ← A [i] | ponownie przeglądamy listę sąsiedztwa A [i] |
K09: | Dopóki
p ≠ nil, wykonuj kroki K10…K18 |
|
K10 | q ← A [p→v] | |
K11: |
Dopóki q ≠ nil, wykonuj kroki K12…K17 |
teraz będziemy przetwarzać listy sąsiedztwa sąsiadów |
K12: | r ← AK [i] | sprawdzamy, czy wierzchołek q→v jest już na liście AK [i] |
K13: |
Dopóki r ≠ nil, wykonuj kroki K14…K15 |
jeśli go nie będzie, to go tam wstawimy |
K14: |
Jeśli (r→v) = (q→v), to idź do K16 |
|
K15: | r ← (r→next) | |
K16: |
Jeśli r = nil, to dodaj (q→v) do listy AK [i ] |
|
K17: | q ← (q→next) | następny sąsiad sąsiada |
K18: | p ← (p→next) | następny sąsiad wierzchołka i-tego |
K19: | Zakończ |
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 dla niego listy sąsiedztwa i oblicza kwadrat grafu, po czym wypisuje wynikowe listy sąsiedztwa w oknie konsoli: |
Dane przykładowe (przekopiuj do
schowka i wklej do okna konsoli):
|
Pascal// Kwadrat grafu // Data: 25.01.2014 // (C)2014 mgr Jerzy Wałaszek //--------------------------- program inc_matrix; // Typy dla dynamicznej tablicy list sąsiedztwa type PslistEl = ^slistEl; slistEl = record next : PslistEl; v : integer; end; TList = array of PslistEl; var n, m, i, v1, v2 : integer; A, AK : TList; p, q, r, x : PslistEl; begin read (n, m); // Czytamy liczbę wierzchołków i krawędzi SetLength (A, n); // Tworzymy tablice list sąsiedztwa SetLength (AK, n); // Tablice wypełniamy pustymi listami for i := 0 to n - 1 do begin A [i] := nil; AK [i] := nil; end; // Odczytujemy kolejne definicje krawędzi for i := 0 to m - 1 do begin read (v1, v2); // Wierzchołek startowy i końcowy krawędzi new (p); // Tworzymy nowy element p^.v := v2; // Numerujemy go jako v2 p^.next := A [v1]; // Dodajemy go na początek listy A [v1] A [v1] := p; end; writeln; // Obliczamy kwadrat grafu w tablicy AK // Przechodzimy przez kolejne wierzchołki grafu for i := 0 to n - 1 do begin // Kopiujemy listę A [i] do AK [i] p := A [i]; while p <> nil do begin new (x); x^.v := p^.v; x^.next := AK [i]; AK [i] := x; p := p^.next; end; // Teraz kopiujemy sąsiadów sąsiadów do AK [i] p := A [i]; while p <> nil do begin // Przeglądamy listę sąsiedztwa sąsiada q := A [p^.v]; while q <> nil do begin // Sprawdzamy, czy dodawany wierzchołek jest unikalny r := AK [i]; while(r <> nil) and (r^.v <> q^.v) do r := r^.next; // Jeśli wierzchołek q^.v jest unikalny, to dodajemy go do listy AK [i] if r = nil then begin new (x); x^.v := q^.v; x^.next := AK [i]; AK [i] := x; end; q := q^.next; end; p := p^.next; end; end; // Wypisujemy zawartość tablicy list sąsiedztwa kwadratu grafu for i := 0 to n - 1 do begin write (i:3, ' :'); p := AK [i]; while p <> nil do begin write (p^.v:3); p := p^.next; end; writeln; end; // Usuwamy tablice 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; p := AK [i]; while p <> nil do begin r := p; p := p^.next; dispose (r); end; end; SetLength (A, 0); SetLength (AK, 0); writeln; end. |
// Kwadrat grafu // Data: 25.01.2014 // (C)2014 mgr Jerzy Wałaszek //--------------------------- #include <iostream> #include <iomanip> using namespace std; // Typy dla dynamicznej tablicy list sąsiedztwa struct slistEl { slistEl * next; int v; }; int main() { int n, m, i, v1, v2; slistEl ** A, ** AK; slistEl *p, *q, *r, *x; cin >> n >> m; // Czytamy liczbę wierzchołków i krawędzi A = new slistEl * [n]; // Tworzymy tablice list sąsiedztwa AK= new slistEl * [n]; // Tablice wypełniamy pustymi listami for(i = 0; i < n; i++) A [i] = AK [i] = NULL; // Odczytujemy kolejne definicje krawędzi for(i = 0; i < m; i++) { cin >> v1 >> v2; // Wierzchołek startowy i końcowy krawędzi p = new slistEl; // Tworzymy nowy element p->v = v2; // Numerujemy go jako v2 p->next = A [v1]; // Dodajemy go na początek listy A [v1] A [v1] = p; } cout << endl; // Obliczamy kwadrat grafu w tablicy AK // Przechodzimy przez kolejne wierzchołki grafu for(i = 0; i < n; i++) { // Kopiujemy listę A [i] do AK [i] for(p = A [i]; p; p = p->next) { x = new slistEl; x->v = p->v; x->next = AK [i]; AK [i] = x; } // Teraz kopiujemy sąsiadów sąsiadów do AK [i] for(p = A [i]; p; p = p->next) { // Przeglądamy listę sąsiedztwa sąsiada for(q = A [p->v]; q; q = q->next) { // Sprawdzamy, czy dodawany wierzchołek jest unikalny for(r = AK [i]; r && (r->v != q->v); r = r->next); // Jeśli wierzchołek q->v jest unikalny, to dodajemy go do listy AK [i] if(!r) { x = new slistEl; x->v = q->v; x->next = AK [i]; AK [i] = x; } } } } // Wypisujemy zawartość tablicy list sąsiedztwa kwadratu grafu for(i = 0; i < n; i++) { cout << setw (3) << i << ":"; for(p = AK [i]; p; p = p->next) cout << setw (3) << p->v; cout << endl; } // Usuwamy tablice list sąsiedztwa for(i = 0; i < n; i++) { p = A [i]; while(p) { r = p; p = p->next; delete r; } p = AK [i]; while(p) { r = p; p = p->next; delete r; } } delete [] A; delete [] AK; cout << endl; return 0;} |
Basic' Kwadrat grafu ' Data: 25.01.2014 ' (C)2014 mgr Jerzy Wałaszek '--------------------------- ' Typy dla dynamicznej tablicy list sąsiedztwa Type slistEl next As slistEl Ptr v As Integer End Type Dim As Integer n, m, i, v1, v2 Dim As slistEl Ptr Ptr A, AK Dim As slistEl Ptr p, q, r, x Open Cons For Input As #1 Input #1, n, m ' Czytamy liczbę wierzchołków i krawędzi A = New slistEl Ptr [n] ' Tworzymy tablice list sąsiedztwa AK= New slistEl Ptr [n] ' Tablice wypełniamy pustymi listami For i = 0 To n - 1 A [i] = 0 AK [i] = 0 Next ' Odczytujemy kolejne definicje krawędzi For i = 0 To m -1 Input #1, v1, v2 ' Wierzchołek startowy i końcowy krawędzi p = new slistEl ' Tworzymy nowy element p->v = v2 ' Numerujemy go jako v2 p->next = A [v1] ' Dodajemy go na początek listy A [v1] A [v1] = p Next Close #1 Print ' Obliczamy kwadrat grafu w tablicy AK ' Przechodzimy przez kolejne wierzchołki grafu For i = 0 To n - 1 ' Kopiujemy listę A [i] do AK [i] p = A [i] While p x = New slistEl x->v = p->v x->next = AK [i] AK [i] = x p = p->Next Wend ' Teraz kopiujemy sąsiadów sąsiadów do AK [i] p = A [i] While p ' Przeglądamy listę sąsiedztwa sąsiada q = A [p->v] While q ' Sprawdzamy, czy dodawany wierzchołek jest unikalny r = AK [i] while(r <> 0) AndAlso (r->v <> q->v) r = r->next Wend ' Jeśli wierzchołek q->v jest unikalny, to dodajemy go do listy AK [i] If r = 0 Then x = New slistEl x->v = q->v x->next = AK [i] AK [i] = x End If q = q->Next Wend p = p->Next Wend Next ' Wypisujemy zawartość tablicy list sąsiedztwa kwadratu grafu For i = 0 To n - 1 Print Using "### :";i; p = AK [i] While p Print Using "###";p->v; p = p->Next Wend Print Next ' Usuwamy tablice list sąsiedztwa For i = 0 To n - 1 p = A [i] While p r = p p = p->Next Delete r Wend p = AK [i] While p r = p p = p->Next Delete r Wend Next Delete [] A Delete [] AK Print End |
Wynik: | |
7 7 0 3 1 0 1 5 5 2 5 4 5 6 6 0 0 : 3 1 : 3 2 4 6 0 5 2 : 3 : 4 : 5 : 0 2 4 6 6 : 3 0 |
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:
Serwis wykorzystuje pliki cookies. Jeśli nie chcesz ich otrzymywać, zablokuj je w swojej przeglądarce.
Informacje dodatkowe.