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 |
ProblemNależy wykonać transpozycję danego grafu skierowanego. Transpozycja grafu skierowanego (ang. digraph transposition) polega na otrzymaniu grafu, który posiada te same wierzchołki, lecz którego krawędzie mają zwrot przeciwny.
|
Aby otrzymać graf transponowany, wystarczy transponować jego macierz sąsiedztwa. Spowoduje to zamianę zwrotu wszystkich krawędzi grafu. Ponieważ macierz sąsiedztwa jest macierzą kwadratową, to można ją transponować w miejscu (gdy graf wyjściowy nie jest potrzebny), utworzyć nową macierz i przepisać do niej zawartość starej macierzy zastępując kolumny wierszami i na odwrót lub po prostu zastąpić odwołania do kolumn odwołaniami do wierszy macierzy i na odwrót (w tym przypadku nic nie musimy robić z macierzą sąsiedztwa!).
Rozwiązanie jest bardzo proste i zostało dokładnie opisane w rozdziale o transpozycji macierzy.
Tworzymy nową tablicę list sąsiedztwa dla grafu transponowanego. Tablicę wypełniamy pustymi listami. Następnie przeglądamy kolejne listy sąsiedztwa w grafie wyjściowym. Jeśli lista wierzchołka v jest niepusta, to zawiera numery sąsiadów u, do których prowadzą krawędzie wychodzące z v. Dla każdego takiego sąsiada u wpisujemy na listę wierzchołka u w grafie transponowanym wierzchołek v. Dzięki temu graf transponowany będzie zawierał wszystkie krawędzie grafu wyjściowego o zwrocie przeciwnym.
n | : | liczba wierzchołków w grafie, n ∈ C. |
A | : | n elementowa tablica list sąsiedztwa grafu wyjściowego. |
v | : | wierzchołek, v ∈ C. |
p, r | : | wskaźniki elementu listy. |
K01: | Utwórz n elementową tablicę list sąsiedztwa AT |
|
K02: | Tablicę AT wypełnij pustymi listami | |
K03: | Dla v = 0, 1, …,
n-1 wykonuj kroki K04…K11 |
przechodzimy kolejno przez wszystkie wierzchołki grafu |
K04: | p ← A [v] | w p ustawiamy adres początku listy sąsiedztwa dla v |
K05: | Dopóki p
≠ nil, wykonuj kroki K06…K11 |
przechodzimy przez kolejne elementy listy |
K06: | Utwórz nowy element listy | |
K07: | r ← adres nowego elementu | |
K08: | (r→v) ← v | w elemencie umieszczamy numer v |
K09: | (r→next) ← AT [p→v] | element r dodajemy do listy AT sąsiada |
K10: | AT [p→v] ← r | |
K11: | p ← (p→next) | przechodzimy do następnego sąsiada na liście A |
K12: | 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 listy sąsiedztwa, a następnie oblicza dla niego graf transponowany i wyświetla wynik w oknie konsoli. |
Dane przykładowe (przekopiuj do
schowka i wklej do okna konsoli):
|
Pascal// Transpozycja grafu // Data: 22.01.2014 // (C)2014 mgr Jerzy Wałaszek //--------------------------- program transg; // Typy dla dynamicznej tablicy list sąsiedztwa type PSLel = ^SLel; SLel = record next : PSLel; v : integer; end; TList = array of PSLel; // ********************** // *** Program główny *** // ********************** var n, m, v, u, i : integer; // Liczba wierzchołków i krawędzi A, AT : TList; // Tablice list sąsiedztwa grafu p, r : PSLel; begin read (n, m); // Odczytujemy liczbę wierzchołków i krawędzi SetLength (A, n); // Tworzymy tablice dynamiczne SetLength (AT, n); // Inicjujemy tablice for i := 0 to n-1 do begin A [i] := nil; AT [i] := nil; end; // Odczytujemy kolejne definicje krawędzi. for i := 0 to m-1 do begin read (v, u); // Wierzchołki tworzące krawędź new (p); // Tworzymy nowy element p^.v := u; // Numerujemy go jako u p^.next := A [v]; // i dodajemy na początek listy A [v] A [v] := p; end; // Wyznaczamy graf transponowany for v := 0 to n-1 do // Przeglądamy kolejne wierzchołki begin p := A [v]; // Przeglądamy sąsiadów v while p <> nil do begin new (r); // Tworzymy nowy element listy r^.v := v; // Zapamiętujemy w nim wierzchołek v r^.next := AT [p^.v]; // i dodajemy do listy sąsiada AT [p^.v] := r; p := p^.next; // Następny sąsiad end; end; // Wypisujemy wyniki writeln; for v := 0 to n-1 do begin write (v, ' :'); p := AT [v]; while p <> nil do begin write (' ', p^.v); p := p^.next; end; writeln; end; // Usuwamy tablice dynamiczne 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 := AT [i]; while p <> nil do begin r := p; p := p^.next; dispose (r); end; end; SetLength (A, 0); SetLength (AT, 0); end. |
// Transpozycja grafu // Data: 22.01.2014 // (C)2014 mgr Jerzy Wałaszek //--------------------------- #include <iostream> #include <iomanip> using namespace std; // Typy dla dynamicznej tablicy list sąsiedztwa struct SLel { SLel * next; int v; }; // ********************** // *** Program główny *** // ********************** int main() { int n, m; // Liczba wierzchołków i krawędzi SLel **A, **AT; // Tablice list sąsiedztwa int i, v, u; SLel *p, *r; cin >> n >> m; // Odczytujemy liczbę wierzchołków i krawędzi A = new SLel * [n]; // Tworzymy tablice dynamiczne AT = new SLel * [n]; // Inicjujemy tablice for(i = 0; i < n; i++) A [i] = AT [i] = NULL; // Odczytujemy kolejne definicje krawędzi. for(i = 0; i < m; i++) { cin >> v >> u; // Wierzchołki tworzące krawędź p = new SLel; // Tworzymy nowy element p->v = u; // Numerujemy go jako w p->next = A [v]; // Dodajemy go na początek listy A [v] A [v] = p; } // Wyznaczamy graf transponowany for(v = 0; v < n; v++) // Przeglądamy kolejne wierzchołki for(p = A [v]; p; p = p->next) // Przeglądamy sąsiadów v { r = new SLel; // Tworzymy nowy element listy r->v = v; // Zapamiętujemy w nim wierzchołek v r->next = AT [p->v]; // i dodajemy do listy sąsiada AT [p->v] = r; } // Wypisujemy wyniki cout << endl; for(v = 0; v < n; v++) { cout << v << ":"; for(p = AT [v]; p; p = p->next) cout << " " << p->v; cout << endl; } // Usuwamy tablice dynamiczne for(i = 0; i < n; i++) { p = A [i]; while(p) { r = p; p = p->next; delete r; } p = AT [i]; while(p) { r = p; p = p->next; delete r; } } delete [] A; delete [] AT; return 0;} |
Basic' Transpozycja grafu ' Data: 22.01.2014 ' (C)2014 mgr Jerzy Wałaszek '--------------------------- ' Typy dla dynamicznej tablicy list sąsiedztwa Type SLel next As SLel Ptr v As Integer End Type ' ********************** ' *** Program główny *** ' ********************** Dim As Integer n, m ' Liczba wierzchołków i krawędzi Dim As SLel Ptr Ptr A, AT ' Tablice list sąsiedztwa grafu Dim As Integer Ptr C Dim As Integer i, v, u, cc Dim As SLel Ptr p, r Open Cons For Input As #1 Input #1, n, m ' Odczytujemy liczbę wierzchołków i krawędzi A = New SLel Ptr [n] ' Tworzymy tablice dynamiczne AT = New SLel Ptr [n] ' Inicjujemy tablice For i = 0 To n-1 A [i] = 0 AT [i] = 0 Next ' Odczytujemy kolejne definicje krawędzi. For i = 1 To m Input #1, v, u ' Wierzchołki tworzące krawędź p = New SLel ' Tworzymy nowy element p->v = u ' Numerujemy go jako w p->next = A [v] ' Dodajemy go na początek listy A [v] A [v] = p Next Close #1 ' Wyznaczamy graf transponowany For v = 0 To n-1 ' Przeglądamy kolejne wierzchołki p = A [v] ' Przeglądamy sąsiadów v While p r = New SLel ' Tworzymy nowy element listy r->v = v ' Zapamiętujemy w nim wierzchołek v r->next = AT [p->v] ' i dodajemy do listy sąsiada AT [p->v] = r p = p->Next ' Następny sąsiad Wend Next ' Wypisujemy wyniki Print For v = 0 To n-1 Print v;":"; p = AT [v] While p print p->v; p = p->Next Wend Print Next ' Usuwamy tablice dynamiczne For i = 0 To n-1 p = A [i] While p r = p p = p->Next Delete r Wend p = AT [i] While p r = p p = p->Next Delete r Wend Next Delete [] A Delete [] AT End |
Wynik: | |
7 11 0 3 1 0 2 0 2 1 4 1 4 2 4 5 5 2 5 3 5 6 6 4 0 : 2 1 1 : 4 2 2 : 5 4 3 : 5 0 4 : 6 5 : 4 6 : 5 |
W macierzy incydencji zamieniamy wszystkie wartości 1 na -1 i na odwrót. Otrzymamy w ten sposób graf, w którym krawędzie posiadają odwrotne zwroty. Macierz incydencji możemy przeglądać kolumnami (kolumna reprezentuje krawędź). W kolumnie szukamy dwóch niezerowych wartości i, gdy je znajdziemy, zmieniamy ich znaki na przeciwne. Dalsze przeglądanie kolumny można już zaniechać.
n | : | liczba wierzchołków w grafie, n ∈ C. |
m | : | liczba krawędzi w grafie, m ∈ C. |
A | : | n × m elementowa macierz incydencji grafu wyjściowego. |
vc | : | zmienna logiczna używana do przerywania pętli po dwóch wierzchołkach. |
i, j | : | indeksy kolumn i wierszy, i, j ∈ C. |
K01: | vc ← true | licznik wierzchołków |
K02: | Dla i = 0, 1, …,
m-1: wykonuj kroki K03…K07 |
przeglądamy kolejne kolumny |
K03: | Dla j
= 0, 1, …, n-1: wykonuj kroki K04…K07 |
przeglądamy komórki w kolumnie i-tej |
K04: |
Jeśli A [j, i] = 0, to następny obieg pętli K03 |
pomijamy wierzchołki nieincydentne z krawędzią i-tą |
K05: | A [j, i] ← (-A [j, i]) | zmieniamy kierunek krawędzi |
K06 | vc ← ¬ vc | negujemy vc, co pozwoli wykryć dwa wierzchołki |
K07: | Jeśli vc = true, to następny obieg pętli K02 |
po dwóch wierzchołkach przechodzimy do następnej kolumny |
K08: | 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 macierz incydencji, a następnie oblicza dla niego graf transponowany i wyświetla wynik w oknie konsoli. |
Dane przykładowe (przekopiuj do
schowka i wklej do okna konsoli):
|
Pascal// Transpozycja grafu // Data: 22.01.2014 // (C)2014 mgr Jerzy Wałaszek //--------------------------- program transg; // Typy dla dynamicznej macierzy incydencji type nptr = array of shortint; // Wiersz mptr = array of nptr; // Cała macierz var n, m, i, j, v1, v2 : integer; A : mptr; vc : boolean; begin read (n, m); // Czytamy liczbę wierzchołków i krawędzi SetLength (A, n); // Tworzymy tablicę wskaźników 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 read (v1, v2); // Wierzchołek startowy i końcowy krawędzi A [v1][i] := 1; // Wierzchołek startowy A [v2][i] := -1; // Wierzchołek końcowy end; // Transponujemy graf vc := true; for i := 0 to m-1 do for j := 0 to n-1 do if A [j, i] <> 0 then begin A [j, i] := -A [j, i]; vc := not vc; if vc then break; 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. |
// Transpozycja grafu // Data: 22.01.2014 // (C)2014 mgr Jerzy Wałaszek //--------------------------- #include <iostream> #include <iomanip> using namespace std; int main() { int n, m, i, j, v1, v2; signed char ** A; bool vc; cin >> n >> m; // Czytamy liczbę wierzchołków i krawędzi A = new signed char * [n]; // Tworzymy tablicę wskaźników for(i = 0; i < n; i++) A [i] = new signed char [m]; // Tworzymy wiersze // 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++) { cin >> v1 >> v2; // Wierzchołek startowy i końcowy krawędzi A [v1][i] = 1; // Wierzchołek startowy A [v2][i] = -1; // Wierzchołek końcowy } // Transponujemy graf vc = true; for(i = 0; i < m; i++) for(j = 0; j < n; j++) if(A [j][i]) { A [j][i] = -A [j][i]; vc = !vc; if(vc) break; } 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' Transpozycja grafu ' Data: 22.01.2014 ' (C)2014 mgr Jerzy Wałaszek '--------------------------- Dim As Integer n, m, i, j, v1, v2 Dim As Byte Ptr Ptr A Dim As Byte vc Open Cons For Input As #1 Input #1, n, m ' Czytamy liczbę wierzchołków i krawędzi A = New Byte Ptr [n] ' Tworzymy tablicę wskaźników 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 Input #1, v1, v2 ' Wierzchołek startowy i końcowy krawędzi A [v1][i] = 1 ' Wierzchołek startowy A [v2][i] =-1 ' Wierzchołek końcowy Next Close #1 ' Transponujemy graf vc = 1 For i = 0 To m-1 For j = 0 To n-1 If A [j][i] Then A [j][i] = -A [j][i] vc = 1-vc If vc = 1 Then Exit For End If Next Next 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 |
Wynik: | |
7 11 0 3 1 0 2 0 2 1 4 1 4 2 4 5 5 2 5 3 5 6 6 4 0 1 2 3 4 5 6 7 8 9 10 0 -1 1 1 0 0 0 0 0 0 0 0 1 0 -1 0 1 1 0 0 0 0 0 0 2 0 0 -1 -1 0 1 0 1 0 0 0 3 1 0 0 0 0 0 0 0 1 0 0 4 0 0 0 0 -1 -1 -1 0 0 0 1 5 0 0 0 0 0 0 1 -1 -1 -1 0 6 0 0 0 0 0 0 0 0 0 1 -1 |
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.