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:

dg : stopień grafu, dg ∈ C.

Elementy 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: ; przechodzimy przez kolejne
     wykonuj kroki K02…K06 ; wierzchołki grafu
K03:   dv ← 0 ; zerujemy stopień wierzchołka
K04    Dla każdego sąsiada u wierzchołka v : ; przechodzimy
       wykonuj krok K05 ; przez sąsiadów wierzchołka v
K05:     Jeśli u = v,
         to dv ← dv+2 ; pętle zliczamy za 2,
         inaczej dv ← dv+1 ; zwykłe krawędzie za 1
K06:   Jeśli dv > dg, ; ustalamy stopień grafu
       to dg ← dv
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
  PSLel = ^SLel;
  SLel = record
    // Następny element listy
    next : PSLel;
    // Wierzchołek docelowy
    v : integer;
  end;

var
  // Liczba wierzchołków,
  // liczba krawędzi
  n, m : integer;
  // Graf
  G : array of PSLel;
  dg, dv, i, v, u : integer;
  p, r : PSLel;

begin
  // Czytamy rozmiary grafu
  read(n, m);
  // Tworzymy zerowy graf G
  SetLength(G, n);
  for i := 0 to n-1 do
    G[i] := nil;
  // Odczytujemy definicje
  // krawędzi grafu G
  for i := 1 to m do
  begin
    // Czytamy wierzchołki
    read(v, u);
    // Tworzymy rekord listy
    new(p);
    // Wypełniamy go danymi
    p^.v := u;
    // Rekord dołączamy
    // do listy sąsiedztwa
    // wierzchołka v
    p^.next := G[v];
    G[v] := p;
    // To samo dla krawędzi
    // odwrotnej,
    // o ile nie jest to pętla
    if v <> u then
    begin
      new(p);
      p^.v := v;
      p^.next := G[u];
      G[u] := p;
    end;
  end;
  // Wyznaczamy stopień grafu
  dg := 0;
  // Przechodzimy przez kolejne
  // wierzchołki grafu
  for v := 0 to n-1 do
  begin
    // Zerujemy stopień
    // wierzchołka
    dv := 0;
    // Przeglądamy sąsiadów
    // wierzchołka v
    p := G[v];
    while p <> nil do
    begin
      if p^.v = v then
        // Pętle zliczamy za 2
        inc(dv, 2)
      else
        // Zwykłą krawędź
        // zliczamy za 1
        inc(dv);
      // Przeglądamy sąsiadów
      // wierzchołka v
      // Następny sąsiad
      p := p^.next;
    end;
    // Jeśli stopień jest większy
    // od dg, to uaktualniamy
    if dv > dg then dg := dv;
  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 SLel
{
  // Następny element listy
  SLel * next;
  // Wierzchołek docelowy
  int v;
};

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

  // Czytamy rozmiary grafu
  cin >> n >> m;
  // Tworzymy zerowy graf G
  G = new SLel * [n];
  for(i = 0; i < n; i++)
    G[i] = nullptr;
  // Odczytujemy definicje
  // krawędzi grafu G
  for(i = 0; i < m; i++)
  {
    // Czytamy wierzchołki
    cin >> v >> u;
    // Tworzymy rekord listy
    p = new SLel;
    // Wypełniamy go danymi
    p->v = u;
    // Rekord dołączamy do
    // listy sąsiedztwa
    // wierzchołka v
    p->next = G[v];
    G[v] = p;
    // To samo dla krawędzi
    // odwrotnej o ile nie
    // jest to pętla
    if(v != u)
    {
      p = new SLel;
      p->v = v;
      p->next = G[u];
      G[u] = p;
    }
  }
  // Wyznaczamy stopień grafu
  dg = 0;
  // Przechodzimy przez kolejne
  // wierzchołki grafu
  for(v = 0; v < n; v++)
  {
    // Zerujemy stopień wierzchołka
    dv = 0;
    // Przeglądamy sąsiadów
    // wierzchołka v
    for(p = G[v]; p; p = p->next)
      // Pętle zliczamy za 2
      if(p->v == v) dv += 2;
      // Zwykłą krawędź zliczamy za 1
      else dv++;
    // Jeśli stopień jest większy
    // od dg, to uaktualniamy
    if(dv > dg) dg = dv;
  }
  // 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 SLel
  ' Następny element listy
  Dim As SLel Ptr next
  ' Wierzchołek docelowy
  Dim As Integer v
End Type

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

Open Cons For Input As #1
' Czytamy rozmiary grafu
Input #1, n, m
' Tworzymy zerowy graf G
G = new SLel Ptr [n]
For i = 0 To n-1
  G[i] = 0
Next
' Odczytujemy definicje krawędzi grafu G
For i = 1  to m
  ' Czytamy wierzchołki
  Input #1, v, u
  ' Tworzymy rekord listy
  p = New SLel
  ' Wypełniamy go danymi
  p->v = u
  ' Rekord dołączamy do listy
  ' sąsiedztwa wierzchołka v
  p->next = G[v]
  G[v] = p
  ' To samo dla krawędzi odwrotnej
  ' o ile nie jest to pętla
  If v <> u Then
    p = new SLel
    p->v = v
    p->next = G[u]
    G[u] = p
  End If
Next
Close #1
' Wyznaczamy stopień grafu
dg = 0
' Przechodzimy przez kolejne
' wierzchołki grafu
For v = 0 To n-1
  ' Zerujemy stopień wierzchołka
  dv = 0
  p = G[v]
  ' Przeglądamy sąsiadów wierzchołka v
  While p
    If p->v = v Then
      ' Pętle zliczamy za 2
      dv += 2
    Else
      ' Zwykłą krawędź zliczamy za 1
      dv += 1
    End If
    ' Następny sąsiad
    p = p->Next
  Wend 
  ' Jeśli stopień jest większy od dg,
  ' to uaktualniamy
  If dv > dg Then dg = dv
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

Python (dodatek)

# Stopień grafu nieskierowanego
# Data: 18.12.2024
# (C)2024 mgr Jerzy Wałaszek
#------------------------------

# Definicja klasy elementu listy sąsiedztwa
class SLel:
    def __init__(self):
        # Następny element listy
        self.next = None
        # Wierzchołek docelowy
        self.v = 0


# Czytamy rozmiary grafu
x = input().split()
n = int(x[0])
m = int(x[1])
# Tworzymy zerowy graf G
g = [None] * n
# Odczytujemy definicje krawędzi grafu G
for i in range(m):
    # Czytamy wierzchołki
    x = input().split()
    v = int(x[0])
    u = int(x[1])
    # Tworzymy rekord listy
    p = SLel()
    # Wypełniamy go danymi
    p.v = u
    # Rekord dołączamy do listy
    # sąsiedztwa wierzchołka v
    p.next = g[v]
    g[v] = p
    # To samo dla krawędzi odwrotnej
    # o ile nie jest to pętla
    if v is not u:
        p = SLel()
        p.v = v
        p.next = g[u]
        g[u] = p
# Wyznaczamy stopień grafu
dg = 0
# Przechodzimy przez kolejne
# wierzchołki grafu
for v in range(n):
    # Zerujemy stopień wierzchołka
    dv = 0
    p = g[v]
    # Przeglądamy sąsiadów wierzchołka v
    while p:
        if p.v == v:
            # Pętle zliczamy za 2
            dv += 2
        else:
            # Zwykłą krawędź zliczamy za 1
            dv += 1
        # Następny sąsiad
        p = p.next
    # Jeśli stopień jest większy od dg,
    # to uaktualniamy
    if dv > dg: dg = dv
# Wyświetlamy wynik
print()
print(dg)
print()
# Usuwamy dynamiczne struktury
for i in range(n):
    while g[i]:
        g[i] = g[i].next
del g

Wynik:

do podrozdziału do 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:

d : stopień grafu, d ∈ C.

Elementy 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: ; przechodzimy przez wszystkie
     wykonuj kroki K03…K05 ; 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):

9 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
  PSLel = ^SLel;
  SLel = record
    // Następny element listy
    next : PSLel;
    // Wierzchołek docelowy
    v : integer;
  end;

var
  // Liczba wierzchołków,
  // liczba krawędzi
  n, m : integer;
  // Graf
  G : array of PSLel;
  // Tablica stopni wierzchołków
  DV : array of integer;
  d, i, v, u : integer;
  p, r : PSLel;
begin
  // Czytamy rozmiary grafu
  read(n, m);
  // Tworzymy zerowy graf G
  SetLength(G, n);
  // Tworzymy tablicę DV
  SetLength(DV, n);
  for i := 0 to n-1 do
  begin
    // Pusta lista
    G[i] := nil;
    // Stopień zerowy
    DV[i] := 0;
  end;
  // Odczytujemy definicje
  // krawędzi grafu G
  for i := 1 to m do
  begin
    // Czytamy wierzchołki
    read(v, u);
    // Tworzymy rekord listy
    new(p);
    // Wypełniamy go danymi
    p^.v := u;
    // Rekord dołączamy do listy
    // sąsiedztwa wierzchołka v
    p^.next := G[v];
    G[v] := p;
  end;
  // Wyznaczamy stopień grafu
  // Przechodzimy przez kolejne
  // wierzchołki grafu
  for v := 0 to n-1 do
  begin
    // Przeglądamy listę
    // sąsiadów wierzchołka v
    p := G[v];
    while p <> NIL do
    begin
      // Zwiększamy stopień
      // wyjściowy v
      inc(DV[v]);
      // Zwiększamy stopień
      // wejściowy sąsiada v
      inc(DV[p^.v]);
      // Następny sąsiad
      p := p^.next;
    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 SLel
{
  // Następny element listy
  SLel * next;
  // Wierzchołek docelowy
  int v;
};

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

  // Czytamy rozmiary grafu
  cin >> n >> m;
  // Tworzymy zerowy graf G
  G = new SLel * [n];
  // Tworzymy tablicę DV
  DV = new int [n];
  for(i = 0; i < n; i++)
  {
    // Pusta lista
    G[i] = nullptr;
    // Stopień zerowy
    DV[i] = 0;
  }
  // Odczytujemy definicje
  // krawędzi grafu G
  for(i = 0; i < m; i++)
  {
    // Czytamy wierzchołki
    cin >> v >> u;
    // Tworzymy rekord listy
    p = new SLel;
    // Wypełniamy go danymi
    p->v = u;
    // Rekord dołączamy do listy
    // sąsiedztwa wierzchołka v
    p->next = G[v];
    G[v] = p;
  }
  // Wyznaczamy stopień grafu
  // Przechodzimy przez kolejne
  // wierzchołki grafu
  for(v = 0; v < n; v++)
    // Przeglądamy listę sąsiadów
    // wierzchołka v
    for(p = G[v]; p; p = p->next)
    {
      // Zwiększamy stopień
      // wyjściowy v
      DV[v] ++;
      // Zwiększamy stopień
      // wejściowy sąsiada v
      DV[p->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 SLel
  ' Następny element listy
  Dim As SLel Ptr Next
  ' Wierzchołek docelowy
  Dim As Integer v
End Type

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

Open Cons For Input As #1
' Czytamy rozmiary grafu
Input #1, n, m
' Tworzymy zerowy graf G
G = New SLel Ptr [n]
' Tworzymy tablicę DV
DV = New Integer [n]
For i = 0 To n-1
  ' Pusta lista
  G[i] = 0
  ' Stopień zerowy
  DV[i] = 0
Next
' Odczytujemy definicje krawędzi grafu G
For i = 1 To m
  ' Czytamy wierzchołki
  Input #1, v, u
  ' Tworzymy rekord listy
  p = New SLel
  ' Wypełniamy go danymi
  p->v = u
  ' Rekord dołączamy do listy
  ' sąsiedztwa wierzchołka v
  p->next = G[v]
  G[v] = p
Next
' Wyznaczamy stopień grafu
' Przechodzimy przez kolejne
' wierzchołki grafu
For v = 0 To n-1
  p = G[v]
  ' Przeglądamy listę
  ' sąsiadów wierzchołka v
  While p
    ' Zwiększamy stopień
    ' wyjściowy v
    DV[v] += 1
    ' Zwiększamy stopień
    ' wejściowy sąsiada v
    DV[p->v] += 1
    ' Następny sąsiad
    p = p->Next
  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

Python (dodatek)

# Stopień grafu skierowanego
# Data: 19.12.2024
# (C)2024 mgr Jerzy Wałaszek
#---------------------------

# Definicja klasy elementu listy sąsiedztwa
class SLel:
    def __init__(self):
        # Następny element listy
        self.next = None
        # Wierzchołek docelowy
        self.v = 0


# Czytamy rozmiary grafu
x = input().split()
n = int(x[0])
m = int(x[1])
# Tworzymy zerowy graf G
g = [None] * n
# Tworzymy tablicę DV
dv = [0] * n
# Odczytujemy definicje krawędzi grafu G
for i in range(m):
    # Czytamy wierzchołki
    x = input().split()
    v = int(x[0])
    u = int(x[1])
    # Tworzymy rekord listy
    p = SLel()
    # Wypełniamy go danymi
    p.v = u
    # Rekord dołączamy do listy
    # sąsiedztwa wierzchołka v
    p.next = g[v]
    g[v] = p
# Wyznaczamy stopień grafu
# Przechodzimy przez kolejne
# wierzchołki grafu
for v in range(n):
    p = g[v]
    # Przeglądamy listę
    # sąsiadów wierzchołka v
    while p:
        # Zwiększamy stopień
        # wyjściowy v
        dv[v] += 1
        # Zwiększamy stopień
        # wejściowy sąsiada v
        dv[p.v] += 1
        # Następny sąsiad
        p = p.next
# Szukamy największego stopnia
d = dv[0]
for v in range(1,n):
    if dv[v] > d: d = dv[v]
# Wyświetlamy wynik
print()
print(d)
print()
# Usuwamy dynamiczne struktury
for i in range(n):
    while g[i]:
        g[i] = g[i].next
del g, dv

Wynik:

9 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

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.

Stopień grafu

Problem

Stopień grafu nieskierowanego

Algorytm wyznaczania stopnia grafu nieskierowanego

Wejście:

Wyjście:

Elementy pomocnicze:

Lista kroków:

Przykładowe programy

Stopień grafu skierowanego

Algorytm wyznaczania stopnia grafu skierowanego

Wejście:

Wyjście:

Elementy pomocnicze:

Lista kroków:

Przykładowe programy