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

©2020 mgr Jerzy Wałaszek
I LO w Tarnowie

Kwadrat grafu

SPIS TREŚCI
Podrozdziały

Problem

Dla 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ź vu, jeśli w grafie wyjściowym istnieje taka krawędź vu  lub w grafie wyjściowym istnieje wierzchołek w  oraz krawędzie vw  i wu.

Graf wyjściowy

obrazek

       Kwadrat grafu wyjściowego

obrazek

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:
  1. Wierzchołek u  jest sąsiadem v  w grafie wyjściowym.
  2. Wierzchołek u  jest sąsiadem wierzchołka w, który z kolei sam jest sąsiadem wierzchołka v.

Wynika z tego, że nowymi sąsiadami wierzchołka v  stają się wszyscy sąsiedzi jego sąsiadów.

Kwadrat grafu zadanego macierzą sąsiedztwa

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ź vu
A [ v, u  ] = 1, jeśli istnieje w grafie krawędź vu

 Zatem  zasada tworzenia macierzy kwadratu grafu jest następująca:

Najpierw tworzymy macierz AK  o tym samym stopniu co macierz sąsiedztwa A  grafu wyjściowego. Następnie przechodzimy przez kolejne wierzchołki v  grafu. Dla każdego wierzchołka v  kopiujemy wiersz A [ v  ] do wiersza AK [ v  ]. Teraz przeglądamy wiersz A [ v  ] kolumnami u. Jeśli v  ≠ u  i A [ v, u  ] = 1, to u  jest sąsiadem wierzchołka v  i do wiersza AK [ v  ] należy dołączyć wiersz A [ u  ] ( czyli sąsiedzi u  staną się sąsiadami v  ).

Algorytm obliczania kwadratu grafu zadanego macierzą sąsiedztwa

Wejście:

n  –  liczba wierzchołków w grafie, n  ∈ C.
A  –  macierz sąsiedztwa grafu o wymiarach n  × n.

Wyjście:

AK  –  macierz sąsiedztwa kwadratu grafu o wymiarach n  × n.
Zmienne pomocnicze:
i, j, k  –  indeksy, i, j, k  ∈ C.

Lista kroków:

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 ) obrazek ( 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 ( n 3 ), gdzie n  oznacza liczbę wierzchołków grafu.


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 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 ):
obrazek 7 7
0 3
1 0 1 5
5 2 5 4 5 6
6 0
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.
C++
// 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
obrazek
Na początek:  podrozdziału   strony 

Kwadrat grafu zadanego listami sąsiedztwa

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.

Algorytm obliczania kwadratu 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ście:

AK  –  n  elementowa tablica list sąsiedztwa kwadratu grafu wyjściowego.
Zmienne pomocnicze:
i  –  wierzchołek, i  ∈ C.
p, q, r  –  wskaźniki elementów listy.

Lista kroków:

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 ( pv  ) do listy AK [ i  ]  
K07:         p  ← ( pnext  ) 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 [ pv  ]  
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 ( rv  ) = ( qv  ),
                to idź do K16
 
K15:                 r  ← ( rnext  )  
K16:             Jeśli r  = nil,
            to dodaj ( qv  ) do listy AK [ i  ]
 
K17:             q  ← ( qnext  ) następny sąsiad sąsiada
K18:         p  ← ( pnext  ) następny sąsiad wierzchołka i-tego
K19: 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 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 ):
obrazek 7 7
0 3
1 0 1 5
5 2 5 4 5 6
6 0
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.
C++
// 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
obrazek
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
©2020 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.