Algorytmy i Struktury Danych - Transpozycja grafu

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.

Algorytm transponowania grafu zadanego listami sąsiedztwa

Wejście:

n : liczba wierzchołków w grafie, n ∈ C.
A : n elementowa tablica list sąsiedztwa grafu wyjściowego.

Wyjście:

AT – n elementowa tablica list sąsiedztwa grafu transponowanego.

Elementy pomocnicze:

v : wierzchołek, v ∈ C.
p, r : wskaźniki elementu listy.

Lista kroków:

K01: Utwórz n elementową tablicę list sąsiedztwa AT
K02: Tablicę AT wypełnij pustymi listami
K03: Dla v = 0, 1, …, n-1, ; przechodzimy kolejno przez wszystkie wierzchołki grafu
     wykonuj kroki K04…K11
K04: p ← A[v] ; w p ustawiamy adres początku listy sąsiedztwa dla v
K05: Dopóki p ≠ nil, ; przechodzimy przez kolejne elementy listy
     wykonuj kroki K06…K11
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

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 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):

7 11
0 3
1 0
2 0
2 1
4 1
4 2
4 5
5 2
5 3
5 6
6 4

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
  // Liczba wierzchołków i krawędzi
  n, m, v, u, i : integer;
  // Tablice list sąsiedztwa grafu
  A, AT : TList;
  p, r : PSLel;

begin
  // Odczytujemy liczbę
  // wierzchołków i krawędzi
  read(n, m);
  // Tworzymy tablice dynamiczne
  SetLength(A, n);
  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
    // Wierzchołki tworzące krawędź
    read(v, u);
    // Tworzymy nowy element
    new(p);
    // Numerujemy go jako u
    p^.v := u;
    // i dodajemy na początek listy A[v]
    p^.next := A[v];
    A[v] := p;
  end;
  //------------------------------
  // Wyznaczamy graf transponowany
  //------------------------------
  // Przeglądamy kolejne wierzchołki
  for v := 0 to n-1 do
  begin
    // Przeglądamy sąsiadów v
    p := A[v];
    while p <> nil do
    begin
      // Tworzymy nowy element listy
      new(r);
      // Zapamiętujemy w nim wierzchołek v
      r^.v := v;
      // i dodajemy do listy sąsiada
      r^.next := AT[p^.v];
      AT[p^.v] := r;
      // Następny sąsiad
      p := p^.next;
    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 SLel
{
  SLel * next;
  int v;
};

// **********************
// *** Program główny ***
// **********************

int main()
{
  // Liczba wierzchołków i krawędzi
  int n, m;
  // Tablice list sąsiedztwa
  SLel **A, **AT;
  int i, v, u;
  SLel *p, *r;

  // Odczytujemy liczbę
  // wierzchołków i krawędzi
  cin >> n >> m;
  // Tworzymy tablice dynamiczne
  A  = new SLel * [n];
  AT = new SLel * [n];
  // Inicjujemy tablice
  for(i = 0; i < n; i++)
    A[i] = AT[i] = nullptr;
  // Odczytujemy kolejne
  // definicje krawędzi
  for(i = 0; i < m; i++)
  {
    // Wierzchołki tworzące krawędź
    cin >> v >> u;
    // Tworzymy nowy element
    p = new SLel;
    // Numerujemy go jako u
    p->v = u;
    // Dodajemy go na początek
    // listy A[v]
    p->next = A[v];
    A[v] = p;
  }
  //------------------------------
  // Wyznaczamy graf transponowany
  //------------------------------
  // Przeglądamy kolejne wierzchołki
  for(v = 0; v < n; v++)
    // Przeglądamy sąsiadów v
    for(p = A [v]; p; p = p->next)
    {
      // Tworzymy nowy element listy
      r = new SLel;
      // Zapamiętujemy w nim
      // wierzchołek v
      r->v = v;
      // i dodajemy do listy sąsiada
      r->next = AT[p->v];
      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 ***
' **********************

' Liczba wierzchołków i krawędzi
Dim As Integer n, m
' Tablice list sąsiedztwa grafu
Dim As SLel Ptr Ptr A, AT
Dim As Integer Ptr C
Dim As Integer i, v, u, cc
Dim As SLel Ptr p, r

Open Cons For Input As #1
' Odczytujemy liczbę
' wierzchołków i krawędzi
Input #1, n, m
' Tworzymy tablice dynamiczne
A  = New SLel Ptr [n]
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
  ' Wierzchołki tworzące krawędź
  Input #1, v, u
  ' Tworzymy nowy element
  p = New SLel
  ' Numerujemy go jako u
  p->v = u
  ' Dodajemy go na początek listy A[v]
  p->next = A[v]
  A[v] = p
Next
Close #1
'------------------------------
' Wyznaczamy graf transponowany
'------------------------------
' Przeglądamy kolejne wierzchołki
For v = 0 To n-1
  ' Przeglądamy sąsiadów v
  p = A[v]
  While p
    ' Tworzymy nowy element listy
    r = New SLel
    ' Zapamiętujemy w nim wierzchołek v
    r->v = v
    ' i dodajemy do listy sąsiada
    r->next = AT[p->v]
    AT[p->v] = r
    ' Następny sąsiad
    p = p->Next
  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

Python (dodatek)

# Transpozycja grafu
# Data: 11.12.2024
# (C)2024 mgr Jerzy Wałaszek
#---------------------------

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


# **********************
# *** Program główny ***
# **********************

# Czytamy liczbę wierzchołków i krawędzi
x = input().split()
n = int(x[0])
m = int(x[1])
# Tworzymy tablice list sąsiedztwa
a  = [None] * n
at = [None] * n
# Odczytujemy kolejne definicje krawędzi.
for i in range(m):
    # Wierzchołki tworzące krawędź
    x = input().split()
    v = int(x[0])
    u = int(x[1])
    # Tworzymy nowy element
    p = SLel()
    # Numerujemy go jako u
    p.v = u
    # Dodajemy go na początek listy a[v]
    p.next = a[v]
    a[v] = p
# -----------------------------
# Wyznaczamy graf transponowany
# -----------------------------
# Przeglądamy kolejne wierzchołki
for v in range(n):
    # Przeglądamy sąsiadów v
    p = a[v]
    while p:
        # Tworzymy nowy element listy
        r = SLel()
        # Zapamiętujemy w nim wierzchołek v
        r.v = v
        # i dodajemy do listy sąsiada
        r.next = at[p.v]
        at[p.v] = r
        # Następny sąsiad
        p = p.next
# Wypisujemy wyniki
print()
for v in range(n):
    print(v,":", end=" ")
    p = at[v]
    while p:
        print(p.v, end=" ")
        p = p.next
    print()
# Usuwamy tablice dynamiczne
for i in range(n):
    while a[i]:
        a[i] = a[i].next
    while at[i]:
        at[i] = at[i].next
del a, at

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

do podrozdziału do strony

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ć.

Algorytm transponowania grafu zadanego macierzą incydencji

Wejście:

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.

Wyjście:

A – n × m elementowa macierz incydencji grafu transponowanego

Elementy pomocnicze:

vc : zmienna logiczna używana do przerywania pętli po dwóch wierzchołkach.
i, j : indeksy kolumn i wierszy, i, j ∈ C.

Lista kroków:

K01: vc ← true ; licznik wierzchołków
K02: Dla i = 0, 1, …, m-1, ;  przeglądamy kolejne kolumny
     wykonuj kroki K03…K07
K03:   Dla j = 0, 1, …, n-1, ; przeglądamy komórki w kolumnie i-tej
       wykonuj kroki K04…K07
K04:   Jeśli A[j, i] = 0, ; pomijamy wierzchołki nieincydentne z krawędzią i-tą
       to następny obieg pętli K03
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, ; po dwóch wierzchołkach przechodzimy do następnej kolumny
       to następny obieg pętli K02
K08: Zakończ

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, 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):

7 11
0 3
1 0
2 0
2 1
4 1
4 2
4 5
5 2
5 3
5 6
6 4

Pascal

// Transpozycja grafu
// Data: 22.01.2014
// (C)2014 mgr Jerzy Wałaszek
//---------------------------

program transg;

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

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

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], m);
  // 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);
    // Wierzchołek startowy
    A[v1][i] := 1;
    // Wierzchołek końcowy
    A[v2][i] := -1;
  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;

  // 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;
    // Wierzchołek startowy
    A[v1][i] =  1;
    // Wierzchołek końcowy
    A[v2][i] = -1;
  }
  // 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
' 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 [m]
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
  ' Wierzchołek startowy
  A[v1][i] =  1
  ' Wierzchołek końcowy
  A[v2][i] = -1
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

Python (dodatek)

# Transpozycja grafu
# Data: 12.12.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 incydencji
a = []
for i in range(n):
    a.append([0] * m)
# 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])
    # Wierzchołek startowy
    a[v1][i] = 1
    # Wierzchołek końcowy
    a[v2][i] = -1
# Transponujemy graf
vc = True
for i in range(m):
    for j in range(n):
        if a[j][i]:
            a[j][i] = -a[j][i]
            vc = not vc
            if vc: break
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
for i in range(n):
    a[i] = None
del a
print()

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

do podrozdziału do strony

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.

Transpozycja grafu

Problem

Transpozycja grafu zadanego macierzą sąsiedztwa

Transpozycja grafu zadanego listami sąsiedztwa

Algorytm transponowania grafu zadanego listami sąsiedztwa

Wejście:

Wyjście:

Elementy pomocnicze:

Lista kroków:

Przykładowe programy

Transpozycja grafu zadanego macierzą incydencji

Algorytm transponowania grafu zadanego macierzą incydencji

Wejście:

Wyjście:

Elementy pomocnicze:

Lista kroków:

Przykładowe programy