Grafy - zadanie na studiach

Question

Mam problem z zadaniem: Napisz program, który wczytuje liczbę wierzchołków i krawędzi oraz pary wierzchołków, a następnie tworzy macierz sąsiedztwa i wypisuje ją w czytelnej formie.

Czy mógłby ktoś wytłumaczyć powiązanie grafów z macierzami?

Comments

Rozważ zmianę kierunku studiów, bo jak z takimi zadaniami sobie nie radzisz to strach pomyśleć co będzie dalej.

---

Zgadzam się z manjaro, nic na siłę!

Answer 1

Twoje zdolności wyszukiwania w internecie są na zaskakującym poziomie, ale trudno:

n - liczba wierzchołków

k - liczba krawędzi

Macierz sąsiedztwa to macierz o wymiarach n×n której pole [i,j] oznacza liczbę krawędzi z i-tego do j-tego wierzchołka. W zależności od typu grafu (np. skierowany/nieskierowany) może to być trochę różne. Wikipedia

Zatem twój kod powinien wyglądać jakoś tak:

wczytaj n
wczytaj k
stwórz wyzerowaną macierz[n,n];
dla i = 1...k:
    wczytaj a, b (wierzchołki między którymi jest krawędź)
    macierz[a,b] = macierz[a,b] + 1
dla i = 1...n:
    dla j = 1...n:
        wypisz macierz[i,j]
    wypisz nową linię