Serwis Edukacyjny w I-LO w Tarnowie Materiały dla uczniów liceum |
Wyjście Spis treści Wstecz Dalej Autor artykułu: mgr Jerzy Wałaszek |
©2024 mgr Jerzy Wałaszek |
ProblemNależy wyznaczyć stopień grafu. Stopień grafu (ang. graph degree) jest równy maksymalnemu stopniowi wierzchołka (ang. vertex degree) w tym grafie. Stopień wierzchołka to liczba krawędzi, które są incydentne z wierzchołkiem (pętle liczy się za 2). |
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.
n | : | liczba wierzchołków w grafie G, n C. |
G | : | graf zadany w dowolnie wybrany sposób, algorytm tego nie precyzuje. |
dg | : | stopień grafu, dg C. |
dv | : | stopień wierzchołka, dv C. |
v, u | : | wierzchołki grafu, v, u C. |
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 |
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):
|
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. |
// 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 |
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.
n | : | liczba wierzchołków w grafie G, n C. |
G | : | graf zadany w dowolnie wybrany sposób, algorytm tego nie precyzuje. |
d | : | stopień grafu, d C. |
DV | : | n elementowa tablica stopni wierzchołków o elementach całkowitych. |
v, u | : | wierzchołki grafu, v, u C. |
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 |
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):
|
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. |
// 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 |
Zespół Przedmiotowy Chemii-Fizyki-Informatyki w I Liceum Ogólnokształcącym im. Kazimierza Brodzińskiego w Tarnowie ul. Piłsudskiego 4 ©2024 mgr Jerzy Wałaszek |
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:
Serwis wykorzystuje pliki cookies. Jeśli nie chcesz ich otrzymywać, zablokuj je w swojej przeglądarce.
Informacje dodatkowe.