Cześć wszystkim, od niedawna zajmuję się programowaniem. Obecnie jestem na etapie poznawania grafów. Moim największym problemem jest to że rozumiem jak działa BFS i DFS, umiem to napisać, ale na tym moja wiedza się kończy. Gdy przychodzi moment, w którym muszę sprawdzić czy najkrótszą ścieżkę w grafie czy też czy graf jest spójny nie potrafię tego zupełnie zrobić. Mając przykład grafu:
4 2
1 2
3 4
A później wpisując liczby do tablic
n=2
1 2
1 3
Jak mogę sprawdzić czy te wierzchołki będą miały pomiędzy sobą krawędź (1 i 2 będą miały, ale 1 i 3 już nie) Prosiłbym kogoś o pomoc i bliższe przybliżenie mi posługiwania się grafami :)
0
0
Polecam zaprzyjaźnić się książką do algorytmów. Skoro nie rozumiesz, tzn, że ze mało czasu przeznaczyłeś na naukę. Widać to nawet w pytaniu, które jest zadane nieprecyzyjnie.
Samo sprawdzenie czy istnieje krawędź pomiędzy wierzchołkami to przeiterowanie po liście sąsiedztwa lub sprawdzenie wartości pod zadanymi indeksami w macierzy sąsiedztwa (Są też inne reprezentacje grafu, ale nie chcę Ci mieszać). Sprawdzenie czy istnieje ścieżka w najprostszej implementacji to przeszukiwanie grafu połączone z odpowiednim znakowaniem wierzchołków.
No nie obraź się, ale zacznij czytać książki.