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 źródłowego. 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.

Elementy 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 ; przechodzimy przez kolejne wiersze
     wykonuj kroki K03…K08
K03: Dla j = 0, 1, …, n-1, ; przechodzimy przez kolejne kolumny
     wykonuj krok K04
K04    AK[i,j] ← A[i,j] ; kopiujemy wiersz wierzchołka bieżącego
K05: Dla j = 0, 1, …, n-1, ; teraz przeglądamy sąsiadów
     wykonuj kroki K06…K08 ; wierzchołka bieżącego
K06:   Jeśli (i = 1)  (A[i,j] = 0), ; pomijamy wierzchołki na przekątnej
       to następny obieg pętli K05   ; 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, ; dołączamy wiersz sąsiada 
         to AK[i,k] ← 1    ; 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
  // Wiersz
  nptr = array of byte;
  // Cała macierz
  mptr = array of nptr;

var
  n, m, i, j, k, v1, v2 : integer;
  A, AK : mptr;

begin
  // Czytamy liczbę wierzchołków
  // i krawędzi
  read(n, m);
   // Tworzymy tablice wskaźników
  SetLength(A, n);
  SetLength(AK, n);
  for i := 0 to n-1 do
  begin
    // Tworzymy wiersze
    SetLength(A[i], n);
    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
    // Wierzchołek startowy
    // i końcowy krawędzi
    read(v1, v2);
    // Krawędź v1->v2 obecna
    A[v1][v2] := 1;
  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;

  // Czytamy liczbę wierzchołków
  // i krawędzi
  cin >> n >> m;
  // Tworzymy tablice wskaźników
  A  = new char * [n];
  AK = new char * [n];
  for(i = 0; i < n; i++)
  {
    // Tworzymy wiersze
    A[i]  = new char [n];
    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++)
  {
    // Wierzchołek startowy
    // i końcowy krawędzi
    cin >> v1 >> v2;
    // Krawędź v1->v2 obecna
    A[v1][v2] = 1;
  }
  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
' Czytamy liczbę wierzchołków i krawędzi
Input #1, n, m
' Tworzymy tablice wskaźników
A  = New Byte Ptr [n]
AK = New Byte Ptr [n]
For i = 0 To n-1
  ' Tworzymy wiersze
  A[i]  = New Byte [n]
  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
  ' Wierzchołek startowy i końcowy krawędzi
  Input #1, v1, v2
  ' Krawędź v1->v2 obecna
  A[v1][v2] = 1
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

Python (dodatek)

# Kwadrat grafu
# Data: 15.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 macierze sąsiedztwa
a = []
ak = []
for i in range(n):
    # Tworzymy wiersze
    a.append([0] * n)
    ak.append([0] * n)
# 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])
    # Krawędź v1->v2 obecna
    a[v1][v2] = 1
print()
# Obliczamy kwadrat grafu w macierzy AK
for i in range(n):
    for j in range(n):
        ak[i][j] = a[i][j]
    for j in range(n):
        if (i != j) and (a[i][j] == 1):
            for k in range(n):
                if a[j][k] == 1:
                    ak[i][k] = 1
# Wypisujemy zawartość
# macierzy sąsiedztwa AK
print("   ", end="")
for i in range(n):
    print("%3d" % i, end="")
print()
print()
for i in range(n):
    print("%3d" % i, end="")
    for j in range(n):
        print("%3d" % ak[i][j], end="")
    print()
# Usuwamy macierze
del a, ak
print()

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

do podrozdziału do 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 źródłowego.

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 źródłowego.

Elementy 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, ; przechodzimy przez kolejne wierzchołki grafu
     wykonuj kroki K04…K18
K04:   p ← A[i]
K05:   Dopóki p ≠ nil, ; kopiujemy listę sąsiedztwa A[i] do AK[i]
       wykonuj kroki K06…K07
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, ; teraz będziemy przetwarzać
         wykonuj kroki K12…K17 ; 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, ; jeśli go nie będzie, to go tam wstawimy
           wykonuj kroki K14…K15
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
  PSLel = ^SLel;
  SLel =  record
    next  : PSLel;
    v     : integer;
  end;
  TList = array of PSLel;

var
  n, m, i, v1, v2 : integer;
  A, AK : TList;
  p, q, r, x : PSLel;
begin
  // Czytamy liczbę wierzchołków
  // i krawędzi
  read(n, m);
  // Tworzymy tablice
  // list sąsiedztwa
  SetLength(A, n);
  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
    // Wierzchołek startowy
    // i końcowy krawędzi
    read(v1, v2);
    // Tworzymy nowy element
    new(p);
    // Numerujemy go jako v2
    p^.v := v2;
    // Dodajemy go na początek
    // listy A[v1]
    p^.next := 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 SLel
{
  SLel * next;
  int v;
};

int main()
{
  int n, m, i, v1, v2;
  SLel ** A, ** AK;
  SLel *p, *q, *r, *x;

  // Czytamy liczbę wierzchołków
  // i krawędzi
  cin >> n >> m;
  // Tworzymy tablice list sąsiedztwa
  A = new SLel * [n];
  AK= new SLel * [n];
  // Tablice wypełniamy pustymi listami
  for(i = 0; i < n; i++)
    A[i] = AK[i] = nullptr;
  // Odczytujemy kolejne
  // definicje krawędzi
  for(i = 0; i < m; i++)
  {
    // Wierzchołek startowy
    // i końcowy krawędzi
    cin >> v1 >> v2;
    // Tworzymy nowy element
    p = new SLel;
    // Numerujemy go jako v2
    p->v = v2;
    // Dodajemy go na początek
    // listy A[v1]
    p->next = 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 SLel;
      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 SLel;
          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 SLel
  next As SLel Ptr
  v As Integer
End Type

Dim As Integer n, m, i, v1, v2
Dim As SLel Ptr Ptr A, AK
Dim As SLel Ptr p, q, r, x

Open Cons For Input As #1
' Czytamy liczbę wierzchołków i krawędzi
Input #1, n, m
' Tworzymy tablice list sąsiedztwa
A = New SLel Ptr [n]
AK= New SLel 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
  ' Wierzchołek startowy i końcowy krawędzi
  Input #1, v1, v2
  ' Tworzymy nowy element
  p = new SLel
  ' Numerujemy go jako v2
  p->v = v2
  ' Dodajemy go na początek listy A [v1]
  p->next = 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 SLel
    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 SLel
        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

Python (dodatek)

# Kwadrat grafu
# Data: 25.01.2014
# (C)2014 mgr Jerzy Wałaszek
#---------------------------

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


# 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
ak = [None] * n
# 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])
    # Tworzymy nowy element
    p = SLel()
    # Numerujemy go jako v2
    p.v = v2
    # Dodajemy go na początek listy a[v1]
    p.next = a[v1]
    a[v1] = p
print()
# Obliczamy kwadrat grafu w tablicy AK
# Przechodzimy przez kolejne
# wierzchołki grafu
for i in range(n):
    # Kopiujemy listę A[i] do AK[i]
    p = a[i]
    while p:
        x = SLel()
        x.v = p.v
        x.next = ak[i]
        ak[i] = x
        p = p.next
     # 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 and (r.v != q.v):
                r = r.next
            # Jeśli wierzchołek q.v jest
            # unikalny, to dodajemy go do
            # listy AK[i]
            if not r:
                x = SLel()
                x.v = q.v
                x.next = ak[i]
                ak[i] = x
            q = q.next
        p = p.next
# Wypisujemy zawartość tablicy
# list sąsiedztwa kwadratu grafu
for i in range(n):
    print("%3d :" % i, end="")
    p = ak[i]
    while p:
        print("%3d" % p.v, end="")
        p = p.next
    print()
# Usuwamy tablice list sąsiedztwa
for i in range(n):
    while a[i]:
        a[i] = a[i].next
    while ak[i]:
        ak[i] = ak[i].next
del a, ak
print()

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

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.

Kwadrat grafu

Problem

Kwadrat grafu zadanego macierzą sąsiedztwa

Algorytm obliczania kwadratu grafu zadanego macierzą sąsiedztwa

Wejście:

Wyjście:

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

Elementy pomocnicze:

Lista kroków:

Przykładowe programy