Problem z grafem

Question

Witam, jakim sposobem mógłbym zliczyć liczbę krawędzi w każdej ścieżce prowadzącej z danego wierzchołka w grafie, do wierzchołka docelowego? Proszę o pomoc 

 

Answer 1

Podczasz szukania drogi z jednego wierzchołka do drugiego rób "ilosc = ilosc + 1"

Answer 2

No to ja wiem, problem jest z "powtarzaniem" się ścieżek.

Comments

Na przyszlosc - na odpowiedzi, odpowiadaj poprzez "skomentuj" pod odpowiedzią.

---

Pisz w komentarzach pod odpowiedzią a nie jako kolejna odpowiedz.

A w jaki sposób szukasz ścieżek, że Ci się powtarzają ?

A może masz problem z powtarzaniem się krawędzi i wierzchołków w ścieżce ? Podczas szukania ścieżki trzeba zaznaczać, który wierzchołek już był odwiedzony.

---

Przeszukuję grf w głąb algorytmem DFS, i zapisuje daną ścieżkę w tablicy.

 

Odwiedzamy wierzchołek
Dopisujemy go do końca listy
Sprawdzamy, czy jest to wierzchołek docelowy
Ścieżka znaleziona
Przerywamy procedurę
inaczej próbujemy odwiedzać wszystkich nieodwiedzonych jeszcze sąsiadów
Jeśli sąsiad nie jest jeszcze odwiedzony,
to odwiedzamy go.
Jeśli ścieżka została znaleziona, kończymy DFS