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