• Najnowsze pytania
  • Bez odpowiedzi
  • Zadaj pytanie
  • Kategorie
  • Tagi
  • Zdobyte punkty
  • Ekipa ninja
  • IRC
  • FAQ
  • Regulamin
  • Książki warte uwagi

Problem z grafem

Object Storage Arubacloud
0 głosów
122 wizyt
pytanie zadane 10 listopada 2015 w C i C++ przez arctura12 Nowicjusz (160 p.)

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 ;)

 

2 odpowiedzi

0 głosów
odpowiedź 10 listopada 2015 przez furas Maniak (53,800 p.)
Podczasz szukania drogi z jednego wierzchołka do drugiego rób "ilosc = ilosc + 1"
0 głosów
odpowiedź 10 listopada 2015 przez arctura12 Nowicjusz (160 p.)
No to ja wiem, problem jest z "powtarzaniem" się ścieżek.
komentarz 10 listopada 2015 przez criss Mędrzec (172,590 p.)
Na przyszlosc - na odpowiedzi, odpowiadaj poprzez "skomentuj" pod odpowiedzią.
komentarz 10 listopada 2015 przez furas Maniak (53,800 p.)
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.
komentarz 10 listopada 2015 przez arctura12 Nowicjusz (160 p.)
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

Podobne pytania

0 głosów
0 odpowiedzi 98 wizyt
pytanie zadane 14 listopada 2022 w HTML i CSS przez MacGyver Nowicjusz (120 p.)
0 głosów
1 odpowiedź 294 wizyt
pytanie zadane 28 grudnia 2021 w Java przez xFanti Obywatel (1,350 p.)
0 głosów
0 odpowiedzi 532 wizyt
pytanie zadane 23 kwietnia 2021 w C i C++ przez Mavimix Dyskutant (8,420 p.)

92,762 zapytań

141,686 odpowiedzi

320,499 komentarzy

62,106 pasjonatów

Motyw:

Akcja Pajacyk

Pajacyk od wielu lat dożywia dzieci. Pomóż klikając w zielony brzuszek na stronie. Dziękujemy! ♡

Oto polecana książka warta uwagi.
Pełną listę książek znajdziesz tutaj.

Akademia Sekuraka

Niedawno wystartował dodruk tej świetnej, rozchwytywanej książki (około 940 stron). Mamy dla Was kod: pasja (wpiszcie go w koszyku), dzięki któremu otrzymujemy 10% zniżki - dziękujemy zaprzyjaźnionej ekipie Sekuraka za taki bonus dla Pasjonatów! Książka to pierwszy tom z serii o ITsec, który łagodnie wprowadzi w świat bezpieczeństwa IT każdą osobę - warto, polecamy!

...