Program obliczający stopień wszystkich wierzchołków grafu.

0

A więc mam do wykonanie takie zadanie:

Napisać program, w którym użytkownik podaje graf i otrzymuje informację o stopniu wszystkich wierzchołków oraz stopniu grafu.

Użytkownik podaje liczbę wierzchołków, oraz krawędzi grafu. Następnie program tworzy macierz sąsiedztwa. Potem podlicza ile krawędzi wychodzi od każdego wierzchołka, zapisuje je, a najwyższy stopień jest zarazem stopniem grafu.

Problem polega na tym, że dołączyłem na kurs niedawno i mam spore zaległości. Nie mogę skumać na jakiej zasadzie z liczby wierzchołków i krawędzi powstaje macierz sąsiedztwa.

Znalazłem coś takiego:

// Reprezentacja grafu, za pomoca listy incydencji, gdzie liste zastapiono typem vector
// www.algorytm.org

#include<iostream>
#include<vector>

using namespace std;

int main()
{
    int V, E;     // V - liczba wierzcholkow, E - liczba krawedzi
    cout << "Liczba wierzcholkow: ";
    cin >> V;
    cout << "Liczba krawedzi: ";
    cin >> E;

    vector<int> *ZA = new vector<int>[V+1];    // mozna tez wykorzystac liste, nie ma to roznicy

    for(int i=1; i<=E; i++)       // wprowadz wierzcholki i krawedzie
    {
        int a, b;
        cout << "Krawedz " << i << ": ";
        cin >> a >> b;
        ZA[a].push_back(b);
        ZA[b].push_back(a);
    }

    for(int i=1; i<=V; i++)     // wypisujemy graf
    {
        cout << endl << "Sasiedzi wierzcholka " << i << ": ";
        for(vector<int>::iterator it = ZA[i].begin(); it != ZA[i].end(); ++it) cout << *it << ", ";
    }

    delete []ZA;     // zwalniamy pamiec
}

Wszystko spoko tyle, że nie znam C++. Ogarniam tylko czyste C i dlatego spora część tego kodu jest dla mnie niezrozumiała. Swój program zamierzam również napisać w C. Z tego kodu rozumiem tylko początek, czyli wprowadzanie danych, a najważniejszego tworzenia macierzy nie mogę zrozumieć.

0
  1. Kod napisał jakiś dewiant, bo połączenie stosowania vector i new w ten sposób to jakaś choroba psychiczna.
  2. Nigdy nie uda ci się "skumać na jakiej zasadzie z liczby wierzchołków i krawędzi powstaje macierz sąsiedztwa", bo macierz sąsiedztwa powstaje z wprowadzonych krawędzi.
  3. Zastosowano new tam gdzie należy użyć vector
  4. Zastosowano vector tam gdzie należy użyć list (i jest istotna różnica mimo że w komentarzu masz inaczej)
  5. Deklaracja powinna wyglądać mniej więcej tak:
typedef list<size_t> Incidence;
typedef vector<Incidence> Graph;
Graph ZA(V);
0

Powiedzmy, że mam 6 wierzchołków i 7 krawędzi. Macierz sąsiedztwa będzie wielkości 6x6. Teraz pytanie jak ją wypełnić. Jeśli mam narysowany graf, to jest to proste, bo jeśli wierzchołek a łączy się krawędzią z wierzchołkiem b, to wpisuję 1, a jeśli nie to 0. Nie wiem tylko skąd program ma wiedzieć kiedy co wpisać skoro on nie będzie miał przed sobą obrazka.

0

Czy na pewno musisz mieć obrazek?
Czy informacja że wierzchołek 3 jest połączony z wierzchołkiem 5 nie będzie wystarczająca żeby wiedzieć gdzie wstawić tą jedynkę?

0

Oczywiście będzie to wystarczająca informacja. Czy to znaczy, że oprócz liczby wierzchołków i krawędzi użytkownik będzie musiał jeszcze wprowadzić dodatkowe dane? Np. który wierzchołek łączy się z którym?

0

Jest to mój kod, chociaż napisany dawno temu i obecnie nie uważam go za szczególnie dobry, ale mogę wybronić kilka rzeczy.

pomijany jest element [0]

Pominąłem element 0 i najczęściej pomijam przy grafach, bo z reguły grafy numeruje się od 1 i tak również najczęściej jest w zadaniach, więc ja najczęściej pomijam indeks 0 przy grafach, bo inaczej musiałbym wczytywać i wypisywać liczby przesunięte o 1 co jest wg mnie nie wygodne (potencjalne miejsce do popełnienia głupiego błędu). Ale jak kto woli.

Kod napisał jakiś dewiant, bo połączenie stosowania vector i new w ten sposób to jakaś choroba psychiczna.(...)

Dawno odwiedzałem mojego psychiatrę i tak wyszło :p.
A na serio to najczęściej po prostu robię globalnie graf w ten sposób:

vector<int> graph[500000]; 

tyle, że w ten sposób trzeba modyfikować kod gdy chce się wprowadzić jakaś bardzo dużą ilość wierzchołków i dałem w ten sposób - to umożliwia wprowadzenie dowolnej ilości, ale oczywiście to był mój błąd bo lepszym wyborem byłoby wprowadzenie stałej na początku:

const int MX = 50000; 

i ludzie mogliby to modyfikować. No cóż - bywa, ale wtedy dopiero się nauczyłem pisać graf i tak zrobiłem (to było prawie 2 lata temu), bo założyłem, że ktoś może chcieć wprowadzić bardzo dużą liczę - jak teraz sobie myślę to jednak spora stała by wystarczyła.

Zastosowano new tam gdzie należy użyć vector

Ale tu blefujesz - użyłem wektora odpowiednio, tylko tworzę go dynamicznie podczas działania programu.

Zastosowano vector tam gdzie należy użyć list (i jest istotna różnica mimo że w komentarzu masz inaczej)

Tutaj też mówisz nieprawdę. Owszem jest pewna różnica, ale niekoniecznie należy używać listy. To się nazywa lista sąsiedztwa, ale w praktyce mając do dyspozycji STL najczęściej wygodniej i lepiej ją implementować przy pomocy wektora i najczęściej ludzie obecnie właśnie tak robią gdy piszą w C++.
Tu masz małe porównanie: http://was.zaa.mimuw.edu.pl/?q=node/31

Generalnie to co bym w szczególności obecnie poprawił to tak mniej-więcej by wyglądało (nie użyłbym pewnie strumieni, bo w sumie głównie używam printf/scanf, ale to akurat nie ma znaczenia, bo to nie jest kod gdzie bardzo liczy się prędkość wczytywania i wypisywania danych):

#include <iostream>
#include <vector>

using namespace std;

const int MX = 500000;

vector<int> graph[MX];
int V, E;

int main() {
    cout << "Liczba wierzcholkow: ";
    cin >> V;
    cout << "Liczba krawedzi: ";
    cin >> E;

    for (int i = 1; i <= E; i++) {
        int a, b;
        cout << "Krawedz " << i << ": ";
        cin >> a >> b;
        graph[a].push_back(b);
        graph[b].push_back(a);
    }

    for (int i = 1; i <= V; i++) {
        cout << endl << "Sasiedzi wierzcholka " << i << ": ";
        for (vector<int>::iterator it = graph[i].begin(); it != graph[i].end(); ++it)
		      cout << *it << ", ";
    }

    return 0;
}

 

@MarcinB01

Następnie program tworzy macierz sąsiedztwa.

W takim razie ten kod Ci nic nie pomoże, bo tu jest tworzona lista sąsiedztwa, ale reprezentacja grafu za pomocą macierzy sąsiedztwa w C jest o wiele łatwiej (inaczej musiałbyś sam tworzyć listy i robić operacje na tych listach sąsiedztwa).

0

Twój program działa u mnie bez zarzutu. Z jego pomocą mógłbym napisać swoją wersję. Problem w tym, że z C++ nigdy nie miałem styczności. Tylko czyste C. Może ma ktoś namiar na podobny program, ale napisany w czystym C ? Ewentualnie mógłby ktoś wytłumaczyć fragmenty kodu, które najbardziej odbiegają od C?
Na początku wprowadzam liczbę krawędzi i wierzchołków. To jasne. Potem pętla for pyta o wierzchołki, które są końcami każdej krawędzi po kolei, ale już taka składnia jest dla mnie niezrozumiała:

cout << "Krawedz " << i << ": ";
        cin >> a >> b;
        graph[a].push_back(b);
        graph[b].push_back(a);

Podobnie w końcówce. Wiem co ta pętla robi, ale nie jestem w stanie przerobić jej na zwykłe C:

  for (int i = 1; i <= V; i++) {
        cout << endl << "Sasiedzi wierzcholka " << i << ": ";
        for (vector<int>::iterator it = graph[i].begin(); it != graph[i].end(); ++it)
                      cout << *it << ", ";
0

Twój program działa u mnie bez zarzutu. Z jego pomocą mógłbym napisać swoją wersję. Problem w tym, że z C++ nigdy nie miałem styczności. Tylko czyste C. Może ma ktoś namiar na podobny program, ale napisany w czystym C ? Ewentualnie mógłby ktoś wytłumaczyć fragmenty kodu, które najbardziej odbiegają od C?

Ale chcesz listę sąsiedztwa czy macierz sąsiedztwa, bo to są listy sąsiedztwa, a to są dwie różne reprezentacje. To jest pisane za pomocą STL-a - to jest biblioteka i w niej masz upakowane niektóre struktury danych, ale jak mówiłem to jest lista sąsiedztwa, a nie macierz. Macierz sąsiedztwa w C jest naprawdę trywialna - spróbuj to sam napisać i jak będziesz miał jakiś problem to napisz, bo nie wiem czego nie rozumiesz. Lista sąsiedztwa zaś jest znacznie trudniejsza do napisania w C/C++ bez STL-a - pisałem ją jakiś czas temu w C++ do jednego zadania na studiach (w tym semestrze na metodach programowania, czyli na algorytmach nie możemy używać STL-a w celach edukacyjnych :/) i niedługo napiszę do kolejnego grafowego (chociaż pewnie skopiuję z tamtego) i napisanie jej jest znacznie trudniejsze niż macierzy sąsiedztwa.

Na początku wprowadzam liczbę krawędzi i wierzchołków. To jasne. Potem pętla for pyta o wierzchołki, które są końcami każdej krawędzi po kolei, ale już taka składnia jest dla mnie niezrozumiała:
(...)
Podobnie w końcówce. Wiem co ta pętla robi, ale nie jestem w stanie przerobić jej na zwykłe C:

Jak napisałem wyżej nie przerobisz tego łatwo na zwykłe C, bo ten nie posiada odpowiednich bibliotek.

0

A więc zaczynam:

#include <stdio.h>
#include <stdlib.h>
 
main()
{
int V; //liczba wierzchołków
int K; //liczba krawędzi
printf("Podaj liczbę wierzchołków: \n");
scanf ("%d",&V);
printf("Podaj liczbę krawędzi: \n");
scanf ("%d",&K);
 

I już na starcie problem. Program ma teraz zapytać po kolei, który wierzchołek styka się z którymi wierzchołkami,
Np. "Z jakimi wierzchołkami sąsiaduje wierzchołek numer 1: " wpisujemy wierzchołki
"Z jakimi wierzchołkami sąsiaduje wierzchołek numer 2: " wpisujemy wierzchołki
itd.

W jaki sposób program powinien wczytywać te dane? Ma z tego powstać prosta macierz sąsiedztwa. Nie wiem tylko jak to zapisać w C.

0

Nie wiem co to za polityka? Ty w ogóle wiesz co to jest tablica? Bo żeby wczytać dane do macierzy sąsiedztwa musisz tylko wiedzieć co to jest tablica dwuwymiarowa i wpisać jedynki w odpowiednie miejsce.

0

Dla wyliczenia stopnia nawet nie potrzebujesz tablicy dwuwymiarowej jedynie:

#include<iostream>
#include<vector>
using namespace std;
 
int main()
  {
   size_t V, E,max=0;
   cout<<"Liczba wierzcholkow: "; cin>>V;
   cout<<"Liczba krawedzi: "; cin>>E; 
   vector<unsigned> St(V);
   for(size_t e=0;e<E;++e)
     {
      for(int i=0;i<2;++i)
        {
         unsigned x;
         cin>>x;
         if(max<++St[--x]) max=St[x];
        }
     }
   cout<<max<<endl;
   return 0;
  }

1 użytkowników online, w tym zalogowanych: 0, gości: 1