Algorytmy i Struktury Danych

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:

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:

–

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

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

Na początek: podrozdziału strony

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:

–

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 ( 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

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

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

Na początek: podrozdziału 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.

Kwadrat grafu

Problem

Kwadrat grafu zadanego macierzą sąsiedztwa

Algorytm obliczania kwadratu grafu zadanego macierzą sąsiedztwa

Wejście:

Wyjście:

Zmienne pomocnicze:

Lista kroków:

Przykładowe programy

Kwadrat grafu zadanego listami sąsiedztwa

Algorytm obliczania kwadratu grafu zadanego listami sąsiedztwa

Wejście:

Wyjście:

Zmienne pomocnicze:

Lista kroków:

Przykładowe programy