Algorytmy i Struktury Danych

W grafie nieskierowanym stopień wierzchołka wyznaczamy bardzo prosto – wystarczy zliczyć sąsiadów (jeśli graf zawiera pętle, to należy je policzyć za 2 ). Następnie wyznaczamy największą wartość otrzymanego stopnia i w ten sposób otrzymamy stopień grafu.

Algorytm wyznaczania stopnia grafu nieskierowanego

Wejście:

n	–	liczba wierzchołków w grafie G, n C.
G	–	graf zadany w dowolnie wybrany sposób, algorytm tego nie precyzuje.

Wyjście:

–

stopień grafu, dg symbol

Zmienne pomocnicze:

dv	–	stopień wierzchołka, dv C.
v, u	–	wierzchołki grafu, v, u C.

Lista kroków:

K01:	dg ← 0	zerujemy stopień grafu
K02:	Dla v = 0, 1, ..., n - 1: wykonuj kroki K02...K06	przechodzimy przez kolejne wierzchołki grafu
K03:	dv ← 0	zerujemy stopień wierzchołka
K04	Dla każdego sąsiada u wierzchołka v : wykonuj krok K05	przechodzimy przez sąsiadów wierzchołka v
K05:	Jeśli u = v, to dv ← dv + 2 inaczej dv ← dv + 1	pętle zliczamy za 2, zwykłe krawędzie za 1
K06:	Jeśli dv > dg, to dg ← dv	ustalamy stopień grafu
K07:	Zakończ z wynikiem dg

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 nieskierowanego, a następnie wyznacza jego stopień. Graf może zawierać pętle oraz krawędzie wielokrotne. Dane wejściowe posiadają następującą postać:

Pierwsze dwie liczby oznaczają kolejno liczbę wierzchołków n oraz liczbę krawędzi m. Następne m par liczb definiuje wierzchołki grafu, pomiędzy którymi jest krawędź nieskierowana. W pętli oba wierzchołki pary są takie same

Dane przykładowe (przekopiuj do schowka i wklej do okna konsoli ):

8 22
0 1 0 3 0 3 0 4
1 1 1 3 1 4 1 5
2 3 2 3 2 5
3 3 3 4 3 7
4 5 4 6 4 7
5 5 5 6
6 6 6 7
7 7

Pascal

// Stopień grafu nieskierowanego
// Data   : 26.04.2014
// (C)2014 mgr Jerzy Wałaszek
//------------------------------

program graph_degree;

// Definicja elementu listy sąsiedztwa
type
  PslistEl = ^slistEl;
  slistEl = record
    next : PslistEl;              // Następny element listy
    v : integer;                  // Wierzchołek docelowy
  end;

var
  n, m : integer;                 // Liczba wierzchołków, liczba krawędzi
  G : array of PslistEl;          // Graf
  dg, dv, i, v, u : integer;
  p, r : PslistEl;
begin
  read ( n, m );                  // Czytamy rozmiary grafu

  SetLength ( G, n );             // Tworzymy zerowy graf G
  for i := 0 to n - 1 do G [ i ] := nil;

  // Odczytujemy definicje krawędzi grafu G

  for i := 1 to m do
  begin
    read ( v, u );                // Czytamy wierzchołki
    new ( p );                    // Tworzymy rekord listy
    p^.v := u;                    // Wypełniamy go danymi
    p^.next := G [ v ];           // Rekord dołączamy do listy sąsiedztwa wierzchołka v
    G [ v ] := p;

    if v <> u then                // To samo dla krawędzi odwrotnej o ile nie jest to pętla
    begin
      new ( p );
      p^.v := v;
      p^.next := G [ u ];
      G [ u ] := p;
    end;
  end;

  // Wyznaczamy stopień grafu

  dg := 0;

  for v := 0 to n - 1 do          // Przechodzimy przez kolejne wierzchołki grafu
  begin
    dv := 0;                      // Zerujemy stopień wierzchołka
    p := G [ v ];                 // Przeglądamy sąsiadów wierzchołka v
    while p <> nil do
    begin
      if p^.v = v then inc ( dv, 2 ) // Pętle zliczamy za 2
      else            inc ( dv ); // Zwykłą krawędź zliczamy za 1
      p := p^.next;               // Następny sąsiad
    end;
    if dv > dg then dg := dv;     // Jeśli stopień jest większy od dg, to uaktualniamy
  end;

  // Wyświetlamy wynik

  writeln;
  writeln ( dg );
  writeln;

  // Usuwamy dynamiczne struktury

  for i := 0 to n - 1 do
  begin
    p := G [ i ];
    while p <> nil do
    begin
      r := p;
      p := p^.next;
      dispose ( r );
    end;
  end;
  SetLength ( G, 0 );

end.

C++

// Stopień grafu nieskierowanego
// Data   : 26.04.2014
// (C)2014 mgr Jerzy Wałaszek
//------------------------------

#include <iostream>

using namespace std;

// Definicja elementu listy sąsiedztwa

struct slistEl
{
  slistEl * next ;          // Następny element listy
  int v;                    // Wierzchołek docelowy
};

int main( )
{
  int n, m;                 // Liczba wierzchołków, liczba krawędzi
  slistEl **G;              // Graf
  int dg, dv, i, v, u;
  slistEl *p, *r;

  cin >> n >> m;            // Czytamy rozmiary grafu

  G = new slistEl * [ n ];  // Tworzymy zerowy graf G
  for( i = 0; i < n; i++ ) G [ i ] = NULL;

  // Odczytujemy definicje krawędzi grafu G

  for( i = 0; i < m; i++ )
  {
    cin >> v >> u;     // Czytamy wierzchołki
    p = new slistEl;   // Tworzymy rekord listy
    p->v = u;          // Wypełniamy go danymi
    p->next = G [ v ]; // Rekord dołączamy do listy sąsiedztwa wierzchołka v
    G [ v ] = p;

    if( v != u )       // To samo dla krawędzi odwrotnej o ile nie jest to pętla
    {
      p = new slistEl;
      p->v = v;
      p->next = G [ u ];
      G [ u ] = p;
    }
  }

  // Wyznaczamy stopień grafu

  dg = 0;

  for( v = 0; v < n; v++ )     // Przechodzimy przez kolejne wierzchołki grafu
  {
    dv = 0;                    // Zerujemy stopień wierzchołka
    for( p = G [ v ]; p; p = p->next ) // Przeglądamy sąsiadów wierzchołka v
      if( p->v == v ) dv += 2; // Pętle zliczamy za 2
      else          dv++;      // Zwykłą krawędź zliczamy za 1
    if( dv > dg ) dg = dv;     // Jeśli stopień jest większy od dg, to uaktualniamy
  }

  // Wyświetlamy wynik

  cout << endl << dg << endl << endl;

  // Usuwamy dynamiczne struktury

  for( i = 0; i < n; i++ )
  {
    p = G [ i ];
    while( p )
    {
      r = p;
      p = p->next;
      delete r;
    }
  }
  delete [ ] G;

  return 0;
}

Basic

' Stopień grafu nieskierowanego
' Data   : 26.04.2014
' (C)2014 mgr Jerzy Wałaszek
'------------------------------

' Definicja elementu listy sąsiedztwa

Type slistEl
  Dim As slistEl Ptr next ' Następny element listy
  Dim As Integer v        ' Wierzchołek docelowy
End Type

Dim As Integer n, m       ' Liczba wierzchołków, liczba krawędzi
Dim As slistEl Ptr Ptr G  ' Graf
Dim As Integer dg, dv, i, v, u
Dim As slistEl Ptr p, r

Open Cons For Input As #1

Input #1, n, m            ' Czytamy rozmiary grafu

G = new slistEl Ptr [ n ] ' Tworzymy zerowy graf G
For i = 0 To n - 1
  G [ i ] = 0
Next

' Odczytujemy definicje krawędzi grafu G

For i = 1  to m
  Input #1, v, u          ' Czytamy wierzchołki
  p = New slistEl         ' Tworzymy rekord listy
  p->v = u                ' Wypełniamy go danymi
  p->next = G [ v ]       ' Rekord dołączamy do listy sąsiedztwa wierzchołka v
  G [ v ] = p

  If v <> u Then          ' To samo dla krawędzi odwrotnej o ile nie jest to pętla
    p = new slistEl
    p->v = v
    p->next = G [ u ] 
    G [ u ] = p
  End If
Next

Close #1

' Wyznaczamy stopień grafu

dg = 0

For v = 0 To n - 1        ' Przechodzimy przez kolejne wierzchołki grafu
  dv = 0                  ' Zerujemy stopień wierzchołka
  p = G [ v ] 
  While p                 ' Przeglądamy sąsiadów wierzchołka v
    If p->v = v Then
      dv += 2             ' Pętle zliczamy za 2
    Else
      dv += 1             ' Zwykłą krawędź zliczamy za 1
    End If
    p = p->Next           ' Następny sąsiad
  Wend  
  If dv > dg Then dg = dv ' Jeśli stopień jest większy od dg, to uaktualniamy
Next

' Wyświetlamy wynik

Print
Print Using "&";dg
Print

' Usuwamy dynamiczne struktury

For i = 0 To n - 1
  p = G [ i ] 
  While p
    r = p
    p = p->Next
    Delete r
  Wend
Next
Delete [ ] G

End

Wynik:

8 22
0 1 0 3 0 3 0 4
1 1 1 3 1 4 1 5
2 3 2 3 2 5
3 3 3 4 3 7
4 5 4 6 4 7
5 5 5 6
6 6 6 7
7 7

9

Na początek: podrozdziału strony

W grafie skierowanym stopień wierzchołka jest sumą stopni wchodzących (ang. in-degree) i wychodzących (ang. out-degree ). Aby efektywnie wyznaczyć te stopnie, tworzymy pomocniczą tablicę DV o tylu elementach, ile wierzchołków posiada graf. Elementy tej tablicy będą zliczać stopnie wierzchołków grafu. W tym celu najpierw zerujemy wszystkie elementy tablicy DV, a następnie przechodzimy przez kolejne wierzchołki grafu. W danym wierzchołku v przeglądamy kolejnych sąsiadów u. Dla każdego sąsiada u zwiększamy o 1 DV [ v ] (krawędź wychodząca) oraz DV [ u ] (krawędź wchodząca ). Gdy przeglądniemy cały graf, należy wyszukać w tablicy DV największy element, który będzie stopniem grafu.

Algorytm wyznaczania stopnia grafu skierowanego

Wejście:

n	–	liczba wierzchołków w grafie G, n C.
G	–	graf zadany w dowolnie wybrany sposób, algorytm tego nie precyzuje.

Wyjście:

–

stopień grafu, d symbol

Zmienne pomocnicze:

DV	–	n elementowa tablica stopni wierzchołków o elementach całkowitych.
v, u	–	wierzchołki grafu, v, u C.

Lista kroków:

K01:	Utwórz n elementową tablicę DV i wyzeruj ją
K02:	Dla v = 0, 1, ..., n - 1: wykonuj kroki K03...K05	przechodzimy przez wszystkie wierzchołki grafu
K03:	Dla każdego sąsiada u wierzchołka v : wykonuj kroki K04...K05
K04	DV [ v ] ← DV [ v ] + 1	zwiększamy stopień wyjściowy v
K05:	DV [ u ] ← DV [ u ] + 1	zwiększamy stopień wejściowy u
K06:	d ← DV [ 0 ]	szukamy największego stopnia
K07:	Dla v = 1, 2, ..., n - 1: wykonuj krok K08
K08:	Jeśli DV [ v ] > d, to d ← DV [ v ]
K09	Zakończ z wynikiem d

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, a następnie wyznacza jego stopień. Graf może zawierać pętle oraz krawędzie wielokrotne. Dane wejściowe posiadają następującą postać:

Pierwsze dwie liczby oznaczają kolejno liczbę wierzchołków n oraz liczbę krawędzi m. Następne m par liczb definiuje wierzchołki grafu: wierzchołek startowy i docelowy krawędzi. W pętli oba wierzchołki pary są takie same.

Dane przykładowe (przekopiuj do schowka i wklej do okna konsoli ):

8 20
0 0 0 1
1 4 1 5 1 6 1 8
2 3 2 5 2 7
4 0 4 2 4 6 4 7 4 8
5 5
6 6 6 3 6 7
7 0
8 8

Pascal

// Stopień grafu skierowanego
// Data   : 26.04.2014
// (C)2014 mgr Jerzy Wałaszek
//---------------------------

program graph_degree;

// Definicja elementu listy sąsiedztwa
type
  PslistEl = ^slistEl;
  slistEl = record
    next : PslistEl;        // Następny element listy
    v : integer;            // Wierzchołek docelowy
  end;

var
  n, m : integer;           // Liczba wierzchołków, liczba krawędzi
  G : array of PslistEl;    // Graf
  DV : array of integer;    // Tablica stopni wierzchołków
  d, i, v, u : integer;
  p, r : PslistEl;
begin
  read ( n, m );            // Czytamy rozmiary grafu

  SetLength ( G, n );       // Tworzymy zerowy graf G
  SetLength ( DV, n );      // Tworzymy tablicę DV
  for i := 0 to n - 1 do
  begin
    G [ i ] := nil;         // Pusta lista
    DV [ i ] := 0;          // Stopień zerowy
  end;

  // Odczytujemy definicje krawędzi grafu G

  for i := 1 to m do
  begin
    read ( v, u );          // Czytamy wierzchołki
    new ( p );              // Tworzymy rekord listy
    p^.v := u;              // Wypełniamy go danymi
    p^.next := G [ v ];     // Rekord dołączamy do listy sąsiedztwa wierzchołka v
    G [ v ] := p;
  end;

  // Wyznaczamy stopień grafu

  for v := 0 to n - 1 do    // Przechodzimy przez kolejne wierzchołki grafu
  begin
    p := G [ v ];           // Przeglądamy listę sąsiadów wierzchołka v
    while p <> NIL do
    begin
      inc ( DV [ v ] );     // Zwiększamy stopień wyjściowy v
      inc ( DV [ p^.v ] );  // Zwiększamy stopień wejściowy sąsiada v
      p := p^.next;         // Następny sąsiad
    end;
  end;

  // Szukamy największego stopnia

  d := DV [ 0 ];
  for v := 1 to n - 1 do
    if DV [ v ] > d then d := DV [ v ];

  // Wyświetlamy wynik

  writeln;
  writeln ( d );
  writeln;

  // Usuwamy dynamiczne struktury

  for i := 0 to n - 1 do
  begin
    p := G [ i ];
    while p <> nil do
    begin
      r := p;
      p := p^.next;
      dispose ( r );
    end;
  end;
  SetLength ( G, 0 );
  SetLength ( DV, 0 );

end.

C++

// Stopień grafu skierowanego
// Data   : 26.04.2014
// (C)2014 mgr Jerzy Wałaszek
//---------------------------

#include <iostream>

using namespace std;

// Definicja elementu listy sąsiedztwa

struct slistEl
{
  slistEl * next;           // Następny element listy
  int v;                    // Wierzchołek docelowy
};

int main( )
{
  int n, m;                 // Liczba wierzchołków, liczba krawędzi
  slistEl **G;              // Graf
  int *DV;                  // Tablica stopni wierzchołków
  int d, i, v, u;
  slistEl *p, *r;

  cin >> n >> m;            // Czytamy rozmiary grafu

  G = new slistEl * [ n ];  // Tworzymy zerowy graf G
  DV = new int [ n ];       // Tworzymy tablicę DV
  for( i = 0; i < n; i++ )
  {
    G [ i ] = NULL;         // Pusta lista
    DV [ i ] = 0;           // Stopień zerowy
  }

  // Odczytujemy definicje krawędzi grafu G

  for( i = 0; i < m; i++ )
  {
    cin >> v >> u;          // Czytamy wierzchołki
    p = new slistEl;        // Tworzymy rekord listy
    p->v = u;               // Wypełniamy go danymi
    p->next = G [ v ];      // Rekord dołączamy do listy sąsiedztwa wierzchołka v
    G [ v ] = p;
  }

  // Wyznaczamy stopień grafu

  for( v = 0; v < n; v++ ) // Przechodzimy przez kolejne wierzchołki grafu
    for( p = G [ v ]; p; p = p->next ) // Przeglądamy listę sąsiadów wierzchołka v
    {
      DV [ v ] ++;          // Zwiększamy stopień wyjściowy v
      DV [ p->v ] ++;       // Zwiększamy stopień wejściowy sąsiada v
    }

  // Szukamy największego stopnia

  d = DV [ 0 ];
  for( v = 1; v < n; v++ )
    if( DV [ v ] > d ) d = DV [ v ];

  // Wyświetlamy wynik

  cout << endl << d << endl << endl;

  // Usuwamy dynamiczne struktury

  for( i = 0; i < n; i++ )
  {
    p = G [ i ];
    while( p )
    {
      r = p;
      p = p->next;
      delete r;
    }
  }
  delete [ ] G;
  delete [ ] DV;

  return 0;
}

Basic

' Stopień grafu skierowanego
' Data   : 26.04.2014
' (C)2014 mgr Jerzy Wałaszek
'---------------------------

' Definicja elementu listy sąsiedztwa

Type slistEl
  Dim As slistEl Ptr Next ' Następny element listy
  Dim As Integer v        ' Wierzchołek docelowy
End Type

Dim As Integer n, m       ' Liczba wierzchołków, liczba krawędzi
Dim As slistEl Ptr Ptr G  ' Graf
Dim As Integer Ptr DV     ' Tablica stopni wierzchołków
Dim As Integer d, i, v, u
Dim As slistEl Ptr p, r

Open Cons For Input As #1
  
Input #1, n, m            ' Czytamy rozmiary grafu

G = New slistEl Ptr [ n ] ' Tworzymy zerowy graf G
DV = New Integer [ n ]    ' Tworzymy tablicę DV
For i = 0 To n - 1
  G [ i ] = 0             ' Pusta lista
  DV [ i ] = 0            ' Stopień zerowy
Next

' Odczytujemy definicje krawędzi grafu G

For i = 1 To m
  Input #1, v, u       ' Czytamy wierzchołki
  p = New slistEl      ' Tworzymy rekord listy
  p->v = u             ' Wypełniamy go danymi
  p->next = G [ v ]    ' Rekord dołączamy do listy sąsiedztwa wierzchołka v
  G [ v ] = p
Next

' Wyznaczamy stopień grafu

For v = 0 To n - 1     ' Przechodzimy przez kolejne wierzchołki grafu
  p = G [ v ] 
  While p              ' Przeglądamy listę sąsiadów wierzchołka v
    DV [ v ] += 1      ' Zwiększamy stopień wyjściowy v
    DV [ p->v ] += 1   ' Zwiększamy stopień wejściowy sąsiada v
    p = p->Next        ' Następny sąsiad
  Wend
Next

' Szukamy największego stopnia

d = DV [ 0 ] 
For v = 1 To n - 1
  If DV [ v ] > d Then d = DV [ v ] 
Next

' Wyświetlamy wynik

Print
Print Using "&";d
Print
  
' Usuwamy dynamiczne struktury

For i = 0 To n - 1
  p = G [ i ] 
  While p
    r = p
    p = p->Next
    Delete r
  Wend
Next
Delete [ ] G
Delete [ ] DV

End

Wynik:

8 20
0 0 0 1
1 4 1 5 1 6 1 8
2 3 2 5 2 7
4 0 4 2 4 6 4 7 4 8
5 5
6 6 6 3 6 7
7 0
8 8

6

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.

Stopień grafu

Problem

Stopień grafu nieskierowanego

Algorytm wyznaczania stopnia grafu nieskierowanego

Wejście:

Wyjście:

Zmienne pomocnicze:

Lista kroków:

Przykładowe programy

Stopień grafu skierowanego

Algorytm wyznaczania stopnia grafu skierowanego

Wejście:

Wyjście:

Zmienne pomocnicze:

Lista kroków:

Przykładowe programy