Macierz sąsiedztwa

Cześć wszystkim jako, że powoli uczę się algorytmów z jednej ze stron internetowych mam problem z kilkom podpunktami do zadania.

#include <iostream>

using namespace std;

int main( )
{
  int n, m, i, j, v1, v2;
  char ** A;

  cin >> n >> m;         // Czytamy liczbę wierzchołków i krawędzi

  A = new char * [ n ];  // Tworzymy tablicę wskaźników

  for( i = 0; i < n; i++ )
    A [ i ] = new char [ n ]; // Tworzymy wiersze

  // Macierz wypełniamy zerami

  for( i = 0; i < n; i++ )
    for( j = 0; j < n; j++ ) A [ i ][ j ] = 0;

  // Odczytujemy kolejne definicje krawędzi

  for( i = 0; i < m; i++ )
  {
    cin >> v1 >> v2;    // Wierzchołek startowy i końcowy krawędzi
    A [ v1 ][ v2 ] = 1; // Krawędź v1->v2 obecna
  }

  cout << endl;

  // Wypisujemy zawartość macierzy sąsiedztwa

  cout << "   ";
  for( i = 0; i < n; i++ ) cout << setw ( 3 ) << i;
  cout << endl << endl;
  for( i = 0; i < n; i++ )
  {
    cout << setw ( 3 ) << i;
    for( j = 0; j < n; j++ ) cout << setw ( 3 ) << ( int ) A [ i ][ j ];
    cout << endl;
  }

  // Usuwamy macierz

  for( i = 0; i < n; i++ ) delete [ ] A [ i ];
  delete [ ] A;

  cout << endl;

  return 0;
}
 

Napisz program, który dla danego grafu skierowanego wyznaczy dla każdego wierzchołka wszystkich jego sąsiadów.
Napisz program, który dla danego grafu skierowanego wyznaczy dla każdego wierzchołka wszystkie wierzchołki, dla których jest on sąsiadem..
Napisz program, który dla danego grafu skierowanego wyznaczy stopnie wychodzące i wchodzące wszystkich wierzchołków.
Napisz program, który dla danego grafu skierowanego wyznaczy wszystkie pętle, krawędzie dwukierunkowe oraz wierzchołki izolowane.

Mógłbym prosić o jakieś nakierowanie kompletnie nie rozumiem algorytmów z macierzy i list sąsiedztwa

Jak kompletnie nie Rozumiesz to lipa. Wróć do teorii, Przeczytaj, Upewnij się, że Rozumiesz wszystko bez wyjątku i dopiero zacznij zadania; inaczej to jest błądzenie pijanego we mgle.

Abstrahując od macierzy sąsiedztwa to poprawiłbym ten nieład, bo przez niego łatwo o proste pomyłki w kodzie. Podziel program na mniejsze fragmenty, powydzielaj to co trzeba do funkcji. Skoro jest to C++ to deklaruj zmienne blisko jej użycia, to nie jest stary C, który na takie rzeczy nie pozwalał, to samo się tyczy licznika w pętli for.

Nie wnikając zbytnio w to co faktycznie powinno być zaimplementowane to poniżej mam propozycję jak trochę upiększyć twój kod tak żeby stał się bardziej przejrzysty. Ten prosty zabieg pomoże ci popchnąć kodowanie do przodu:

#include <iostream>
#include <iomanip>
#include <vector>

using namespace std;

void drukuj_macierz(const vector<vector<int>>& tab) {
    for (size_t i = 0; i < tab.size(); i++) {
        for (size_t j = 0; j < tab[i].size(); j++) {
            cout << setw(3) << tab[i][j];
        }
        cout << endl;
    }
}

int wczytaj(const string& prompt) {
    int i;
    cout << "wczytaj <" << prompt << ">: ";
    cin >> i;
    return i;
}

int main() {
    int liczba_wierszy = wczytaj("liczbe wierszy");
    int liczba_kolumn  = wczytaj("liczbe kolumn");

    vector<vector<int>> macierz(liczba_wierszy, vector<int>(liczba_kolumn));

    int ilosc_wezlow = wczytaj("ilosc wezlow");
    for (int i = 0; i < ilosc_wezlow; i++) {
        cout << "Wczytaj krawedz " << i << ":\n";
        int v1 = wczytaj("wierzcholek startowy, wiersz");
        int v2 = wczytaj("wierzcholek koncowy, kolumna");

        macierz[v1][v2] = 1;
        drukuj_macierz(macierz);
    }
    return 0;
}

Jak cie zestaw pytań przerasta to na początku zajmij się tylko pierwszym, nie wszystko naraz. Weźmy taką listę krawędzi (wierzchołki 0..n, n=3):

1 2
0 2
0 3

daje to kwadratową macierz sąsiedztwa o wymiarze n+1 na n+1:

0 0 1 1
0 0 1 0
0 0 0 0
0 0 0 0

jest to po prostu inny zapis tej listy krawędzi, gdzie numer wiersza to jest węzeł początkowy, a numer kolumny to węzeł końcowy.

pyt 1). sąsiedzi v0 to są ci na których on wskazuje. Zatem bierzesz wiersz 0, i wypisujesz numery indeksów z jedynką, czyli 2 i 3. Funkcja znajdująca sąsiadów dla danego węzła mogły wyglądać mniej więcej tak:

vector<int> moi_sasiedzi(... macierz, ... nr_wezla) {
    vector<int> znaleziono;
    for (col = 0; col < macierz.size(); col++) {
        if (macierz[nr_wezla][col] == 1)
            znaleziono.push_back(col);
    }
    return znaleziono;
}

potem tylko przepytać dla każdego węzła.

pyt 2). v3 jest tylko sąsiadem v0, bo kolumna 3 ma wiersz 0 tam gdzie jest jedynka

pyt 3). Liczenie stopnia - zadajesz pytanie: ile sąsiadów ma węzeł v2? Dla grafu skierowanego oddzielnie liczysz wchodzące i wychodzące. W tym przypadku liczysz ile jest jedynek w kolumnie o indeksie 2 w macierzy kwadratowej sąsiedztwa. Tutaj jest ich 2, bo w liście krawędzi podane zostało 1->2 i 0->2, to będą wchodzące. Teraz bierzesz wiersz 2 i liczysz jedynki, jest ich zero bo do tego węzła nic nie wchodzi. Proste.

pętle to jak wierzchołek pokazuje sam na siebie, czyli 1 na przekątnej macierzy, warunek macierz[i][i] == 1

pętla kierunkowa ("ja pokazuję na ciebie, ty pokazujesz na mnie"), 1 na dwóch polach, które są symetryczne względnej przekątnej, warunek macierz[i][j] == 1 && macierz[j][i] == 1