Rozwiązania zadań 9-11 - listy sąsiedztwa

Zadanie 9

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.

 

Zadanie 10

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:

  1. 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.

  2. 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.

  3. Wyszukujemy w tablicy degree największą wartość i zapamiętujemy ją w zmiennej maxdegree.

  4. 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

 

 

Zadanie 11

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

 



List do administratora Serwisu Edukacyjnego Nauczycieli I LO

Twój email: (jeśli chcesz otrzymać odpowiedź)
Temat:
Uwaga: ← tutaj wpisz wyraz  ilo , inaczej list zostanie zignorowany

Poniżej wpisz swoje uwagi lub pytania dotyczące tego rozdziału (max. 2048 znaków).

Liczba znaków do wykorzystania: 2048

 

W związku z dużą liczbą listów do naszego serwisu edukacyjnego nie będziemy udzielać odpowiedzi na prośby rozwiązywania zadań, pisania programów zaliczeniowych, przesyłania materiałów czy też tłumaczenia zagadnień szeroko opisywanych w podręcznikach.



   I Liceum Ogólnokształcące   
im. Kazimierza Brodzińskiego
w Tarnowie

©2017 mgr Jerzy Wałaszek

Dokument ten rozpowszechniany jest zgodnie z zasadami licencji
GNU Free Documentation License.