Prezentowane materiały są przeznaczone dla uczniów szkół ponadgimnazjalnych. Autor artykułu: mgr Jerzy Wałaszek, wersja1.0 |
©2011 mgr
Jerzy Wałaszek
|
Napisz program, który sprawdza, czy graf zadany listami sąsiedztwa jest grafem nieskierowanym lub skierowanym. Która z reprezentacji grafów jest dla tego zadania najlepsza?
Zadanie można rozwiązać np. tak:
Przechodzimy przez kolejne elementy tablicy list sąsiedztwa. Każda lista skojarzona jest z określonym wierzchołkiem grafu i przechowuje wierzchołki, do których prowadzą krawędzie z tego wierzchołka. Wystarczy przejść do każdego z tych wierzchołków i sprawdzić, czy na ich listach sąsiedztwa występuje wierzchołek wyjściowy. Jeśli nie, to graf nie jest grafem nieskierowanym, ponieważ posiada przynajmniej jedną krawędź, którą można przejść tylko w jednym kierunku. Jeśli przeglądniemy wszystkie wierzchołki i ich sąsiadów i nie stwierdzimy krawędzi jednokierunkowej, to graf będzie grafem nieskierowanym.
Code::Blocks | |
bool isnodigraph = true; // Zmienna testowa // Przeglądamy kolejne wierzchołki grafu for(i = 0; isnodigraph && (i < n); i++) // dla każdego wierzchołka przeglądamy sąsiadów for(list<int>::iterator it1 = A[i].begin(); isnodigraph && (it1 != A[i].end()); it1++) { isnodigraph = false; // u sąsiadów szukamy krawędzi zwrotnej for(list<int>::iterator it2 = A[* it1].begin(); it2 != A[* it1].end(); it2++) if(* it2 == i) { isnodigraph = true; // krawędź znaleziona break; } } // Wyświetlamy wynik cout << endl; if(isnodigraph) cout << "GRAF NIESKIEROWANY" << endl; else cout << "GRAF SKIEROWANY" << endl; |
|
4 5 1 0 2 0 0 3 3 1 3 2 GRAF SKIEROWANY |
4 10 1 0 0 1 2 0 0 2 0 3 3 0 3 1 1 3 3 2 2 3 GRAF NIESKIEROWANY |
Odpowiedź na drugą część pytania proszę opracować we własnym zakresie - należy rozważyć ilość krawędzi w stosunku do liczby wierzchołków.
Napisz program, który wyszukuje w grafie skierowanym wszystkie wierzchołki o najwyższym stopniu. Graf zadany jest listami sąsiedztwa.
W grafie skierowanym listy sąsiedztwa dają nam bezpośrednio informację tylko o stopniach wyjściowych wierzchołków - liczba elementów na liście sąsiedztwa jest równa stopniowi wyjściowemu wierzchołka. Stopnie wejściowe musimy zliczać przeglądając wierzchołki docelowe na listach. Zatem rozwiązanie zadania będzie się składało z kilku kroków:
Utworzymy tablicę degree, w której będziemy obliczać dla każdego wierzchołka jego stopień. Tablica ta będzie miała tyle elementów ile jest wierzchołków w grafie - indeksy elementów będą odpowiadały numerom wierzchołków. Na początku wszystkie elementy tablicy degree muszą zostać wyzerowane.
Przeglądamy kolejne listy sąsiedztwa. Dla każdego elementu na liście zwiększamy o 1 element tablicy degree o indeksie równym numerowi listy oraz element o indeksie równym numerowi wierzchołka, do którego prowadzi krawędź - czyli wierzchołka umieszczonego na liście sąsiedztwa.
Wyszukujemy w tablicy degree największą wartość i zapamiętujemy ją w zmiennej maxdegree.
Przeglądamy tablicę degree i wypisujemy numery elementów, których wartość jest równa maxdegree.
Code::Blocks |
// Tworzymy dynamicznie tablicę degree int * degree = new int[n]; // Zerujemy tablicę degree for(i = 0; i < n; i++) degree[i] = 0; // Zliczamy stopnie wierzchołków for(i = 0; i < n; i++) for(list<int>::iterator it = A[i].begin(); it != A[i].end(); it++) { degree[i]++; // Stopień wyjściowy degree[*it]++; // Stopień wejściowy } // Szukamy maksymalnego stopnia int maxdegree = degree[0]; for(i = 1; i < n; i++) if(degree[i] > maxdegree) maxdegree = degree[i]; // Wyświetlamy wyniki cout << endl << "deg(" << maxdegree << ") :"; for(i = 0; i < n; i++) if(degree[i] == maxdegree) cout << " " << i; cout << endl; // Czyścimy pamięć delete [] degree; |
4 9 1 0 1 1 2 0 3 0 0 3 3 1 2 2 3 2 2 3 deg(5) : 2 3 |
Jeśli graf jest nieskierowany, to program można znacznie uprościć, gdyż stopień wierzchołka jest wtedy zawsze równy długości skojarzonej z nim listy sąsiedztwa - list tych nie musimy wcale przeglądać, wystarczy wykorzystać funkcję składową size(), która zwraca liczbę elementów umieszczonych na liście. Również nie musimy tworzyć osobnej tablicy degree. Rozwiązanie jest następujące:
Code::Blocks |
// Szukamy maksymalnego stopnia unsigned maxdegree = A[0].size(); for(i = 1; i < n; i++) if(A[i].size() > maxdegree) maxdegree = A[i].size(); // Wyświetlamy wyniki cout << endl << "deg(" << maxdegree << ") :"; for(i = 0; i < n; i++) if(A[i].size() == maxdegree) cout << " " << i; cout << endl; |
12 14 0 3 1 3 1 2 2 5 5 6 3 4 4 6 3 8 4 10 6 11 7 8 8 9 9 10 10 11 deg(4) : 3 |
Mamy graf nieskierowany, który reprezentuje zbiór osób oraz informację o tym, które osoby ze sobą współpracują. Graf zadany jest listami sąsiedztwa. Napisz program, który wyszuka wszystkie różne trójki współpracujących nawzajem osób.
Najpierw musimy określić, co będzie rozwiązaniem tego zadania. Mamy graf, który reprezentuje grupę osób oraz współpracę pomiędzy nimi - dwa wierzchołki są połączone krawędzią, jeśli osoby reprezentowane przez te wierzchołki współpracują ze sobą.
6 9 0 2 0 4 0 5 1 3 1 4 1 5 2 4 3 4 3 5 |
Na przykład: w naszym grafie współpracują ze sobą osoby 0-2, 0-4, 0-5. Pomiędzy tymi wierzchołkami są krawędzie. Nie współpracują ze sobą osoby 0-1, 0-3. Pomiędzy tymi wierzchołkami nie ma krawędzi.
Wybieramy w grafie jeden wierzchołek, np. 0:
Przechodzimy kolejno przez wszystkich jego sąsiadów (2, 4, 5):
Dla każdego z sąsiadów sprawdzamy, czy jego sąsiedzi są również sąsiadami wierzchołka 0:
0 - 2 - 4 - wyprowadzamy |
0 - 4 - 2 - nie wyprowadzamy |
Brak trójki dla 0 - 5 |
Jeśli znajdziemy taką trójkę (4 jest sąsiadem 2 oraz 0), to wyprowadzamy ją tylko wtedy, gdy kolejne wierzchołki (startowy, sąsiad, wspólny sąsiad) tworzą ciąg rosnący. Unikniemy w ten sposób permutacji tych trójek (0 - 2 - 4, 0 - 4 - 2, 2 - 0 - 4, 2 - 4 - 0, 4 - 0 - 2, 4 - 2 - 0). Tę samą procedurę stosujemy dla pozostałych wierzchołków grafu. Ponieważ trójka musi być uporządkowana rosnąco, to przeglądanie wierzchołków możemy ograniczyć do przedziału od 0 do n - 3. Wynika stąd również, że w trakcie przeglądania wierzchołków możemy pominąć sprawdzanie, jeśli sąsiad ma numer mniejszy od wierzchołka wyjściowego (w takiej sytuacji ewentualna trójka została znaleziona już wcześniej).
Code::Blocks |
// Znajdowanie w grafie spójnych trójek // Graf nieskierowany // Listy sąsiedztwa // (C)2011 mgr Jerzy Wałaszek //----------------------------- #include <iostream> #include <iomanip> #include <list> using namespace std; int main() { int n,m,i,v1,v2; // Odczytujemy n i m cin >> n >> m; // Tworzymy tablicę n pustych list list<int> * A; A = new list<int> [n]; // Wczytujemy poszczególne krawędzie i umieszczamy informację o nich na listach for(i = 0; i < m; i++) { cin >> v1 >> v2; // Do listy A[v1] dodajemy wierzchołek v2 A[v1].push_back(v2); // Do listy A[v2] dodajemy wierzchołek v1, aby krawędź była obukierunkowa if(v1 != v2) A[v2].push_back(v1); } // Przechodzimy przez kolejne wierzchołki grafu od 0 do n-3 cout << endl; for(i = 0; i < n - 2; i++) // Dla każdego wierzchołka przechodzimy przez jego sąsiadów for(list<int>::iterator it1 = A[i].begin(); it1 != A[i].end(); it1++) // Jeśli sąsiad ma numer większy od i, sprawdzamy, czy któryś z jego sąsiadów // jest również sąsiadem wierzchołka i-tego if(i < * it1) for(list<int>::iterator it2 = A[*it1].begin(); it2 != A[*it1].end(); it2++) if(*it1 < *it2) for(list<int>::iterator it3 = it1; it3 != A[i].end(); it3++) if(*it3 == *it2) { cout << i << " - " << *it1 << " - " << *it2 << endl; break; } cout << endl; // Usuwamy tablicę list z pamięci komputera delete [] A; return 0; } |
6 9 0 2 0 4 0 5 1 3 1 4 1 5 2 4 3 4 3 5 0 - 2 - 4 1 - 3 - 4 1 - 3 - 5 |
I Liceum Ogólnokształcące |
Pytania proszę przesyłać na adres email: i-lo@eduinf.waw.pl
W artykułach serwisu są używane cookies. Jeśli nie chcesz ich otrzymywać,
zablokuj je w swojej przeglądarce.
Informacje dodatkowe