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 |
©2023 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 PslistEl = ^slistEl; slistEl = record next : PslistEl; v : integer; end; TList = array of PslistEl; // ********************** // *** 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 : PslistEl; 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. |
C++// 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 slistEl { slistEl * next; int v; }; // ********************** // *** Program główny *** // ********************** int main( ) { int n, m; // Liczba wierzchołków i krawędzi slistEl **A, **AT; // Tablice list sąsiedztwa int i, v, u; slistEl *p, *r; cin >> n >> m; // Odczytujemy liczbę wierzchołków i krawędzi A = new slistEl * [ n ]; // Tworzymy tablice dynamiczne AT = new slistEl * [ 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 slistEl; // 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 slistEl; // 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 slistEl next As slistEl Ptr v As Integer End Type ' ********************** ' *** Program główny *** ' ********************** Dim As Integer n, m ' Liczba wierzchołków i krawędzi Dim As slistEl Ptr Ptr A, AT ' Tablice list sąsiedztwa grafu Dim As Integer Ptr C Dim As Integer i, v, u, cc Dim As slistEl Ptr p, r Open Cons For Input As #1 Input #1, n, m ' Odczytujemy liczbę wierzchołków i krawędzi A = New slistEl Ptr [ n ] ' Tworzymy tablice dynamiczne AT = New slistEl 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 slistEl ' 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 slistEl ' 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. |
C++// 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 ©2023 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.