Grafy - szukanie cykli

0

Witam !
Krótko mówiąc, mam zrobić program, którego zadaniem będzie szukanie cykli prostych w grafie nieskierowanym, którego krawędzie mają wagi (w związku z tym będę musiał także wyświetlać sumy wag poszczególnych cykli). Na razie wiem, że będę musiał wykorzystać przerobiony trochę algorytm przeszukiwania w głąb i w związku z tym nasuwają mi się pytania odnośnie, która reprezentacja grafu będzie lepsza:

  1. z wykorzystaniem macierzy sąsiedztwa, tylko że w taki sposób, że zamiast "1", która reprezentuje istnienie danej krawędzi między wierzchołkami, wpisywałbym wartość wagi krawędzi (wartość tej wagi ma być rzeczywista nieujemna, więc jakby nie istniała to wpisałbym jakoś ujemną). To co zniechęca mnie do tej reprezentacji to "pamięciożerność" w przypadku macierzy rzadkich, tzn. gdy mamy mało krawędzi a sporo wierzchołków.
  2. po prostu zrobienie klasy wierzchołka, krawędzi i grafu, gdzie klasa wierzchołka będzie miała jakąś listę wierzchołków, krawędź wskazanie na dwa wierzchołki oraz wagę, no i graf będzie miala jakies wektory/listy wierzchołków i grafów. W dodatku do wierzchołka bym dodał wartość bool _isVisited, ktora by sie przydala do algorytmu dfs (zamiast robienia jakieś całej tablicy wartości logicznych, która by przetrzymala info czy dany wierzchołek odwiedzony).
    Program pisany w c++.
    Z góry dziękuje za pomoc.
2

Jasne, że 2. Do tego algorytmu potrzebujesz łatwego dostępu do wszystkich sąsiadów danego wierzchołka, a to lepiej zapewnia reprezentacja 2.

struct edge {
  int weight;
  size_t neighbor_id;
};

struct vertex {
  std::list<edge> neighbors;
  bool is_visited;
  vertex() : is_visited(false) {}
};

std::list<vertex> graph; 

Taka reprezentacja będzie zarówno prosta jak i dobra. Możesz też pobawić się z std::shared_ptr.

2

Każdy z istniejących algorytmów działających na grafie można zrealizować na trzech reprezentacjach grafu:

  1. Macierz sąsiedztwa
  2. Lista sąsiedztwa
  3. Reprezentacja strukturalna (np: jak podał @pingwindyktator)

Bardzo nieliczne algorytmy są łatwiejsze w implementacji w przypadku wyboru reprezentacji nr 1.
Z algorytmów grafowych które są łatwiejsze w przypadku wyboru reprezentacji nr 2, kojarzy mi się jedyni trzymanie danych w pliku.

0

Oki... Dziękuje Wam bardzo za rozwianie wątpliwości. Jeszcze muszę się dopytać "przełożonych", czy mogę korzystać z struktur z std i w sumie można zabierac się do roboty. Jeszcze raz dziękuje za pomoc

0
Sarnapa napisał(a):

Jeszcze muszę się dopytać "przełożonych", czy mogę korzystać z struktur z std ...
Jeżeli nie można z std to znajdziesz to samo w boost, jeżeli zaś nie można korzystać z boost lub struktur - to moja rada uciekaj stamtąd.

0

Nie no, zabranianie korzystania ze struktur to głupota niesamowita, natomiast często zabrania się korzystania z kontenerów w std rzeczywiście, żeby najpierw napisać je samemu. Moja rada w tym przypadku - sam zaklep listę, przyda się na kolejne zajęcia dopóki nie będziecie mogli używać tej z std :D

0

Raczej powinienem, ale wolę się upewnić, bo gdzie indziej spotykałem się z takimi "rygorami".

0

Przepraszam, że tak odświeżam temat, ale nie mialem czasu bo przygotowania do Sylwka i takie tam... Czy dałoby znaleźć radę wszystkie cykle mając info o istnieniu krawędzi tylko dla jednego wierzchołka, znaczy, że dodaję krawędź do listy krawędzi jednego wierzchołka ? Bo tak kombinuje i wydaje mi się, że klasyczny dfs to nie da rady, ale moze sa jakies inne sposoby ?

0

Jeżeli tylko jeden wierzchołek ma krawędzie to cykl może być tylko w przypadku kiedy krawędź łączy ten wierzchołek sam ze sobą.
Aczkolwiek może coś innego miałeś na myśli, np tworzysz graf skierowany, po czym stwierdzasz że nie jest skierowany i nic z tym nie robiąc chcesz zaimplementować jakiś algorytm.
W takim przypadku polecam jedną z reprezentacji grafu przedstawionych tu http://4programmers.net/Forum/1208261 - sprawi to że wszystkie algorytmy będą prostsze niż przy twojej reprezentacji grafu.

0

Znaczy ja mam graf nieskierowany bez takich pętli i ja się pytałem czy żeby odnaleźć wszystkie cykle to czy muszę w obu wierzchołkach danej krawędzi trzymać w liście krawędzi info o istnieniu danej krawędzi, czy tylko w jednym wierzchołku by wystarczyło (jakby co mam właściwie taką samą reprezentację jak podał @pingwindyktator ). Znaczy tą kwestię to już raczej rozwiązałem i po prostu wsadzam krawędzie do obu list krawędzi dla obu wierzchołków, ale teraz w sumie mam problem, czy rekurencyjne podejście do sprawy takie jak dla dfs gwarantuje nam na pewno odnalezienie wszystkich cykli. Bo tak próbowałem zrobić coś podobnego do tego http://eduinf.waw.pl/inf/alg/001_search/0133.php i wydaje mi się, że niektóre w niektórych grafach mogą zostać pominięte.

1

Wyobraź sobie taki niezbyt duży graf który wygląda jak siatka powiedzmy 2x2 czy wiesz ile tam jest różnych cykli? Poprawna odpowiedź 13 cykli
A może podejmiesz się policzenia ile tego będzie w siatce 5x5 ?
Do dowolnego algorytmu który operuje na cyklach wystarczą te 25 podstawowych cykli (dla siatki 5x5) pozostałe zaś są ich kombinacją i nie są potrzebne.
Więc nie wyszukuj wszystkich cykli, znajdź tylko te podstawowe, algorytm:

  1. Minimalne drzewo rozpinające
  2. Każdy nieużyta w minimalnym drzewie krawędź jest częścią jednego podstawowego cyklu.
  3. Pozostałą częścią cyklu jest najkrótsza droga w minimalnym drzewie.
0

A ja mam jeszcze takie pytanie... Dlaczeg o akurat minimalne drzewo rozpinające, a nie zwykłe rozpinające ? Bo z tego co czytalem, minimalne drzewo rozpinajace to takie drzewo rozpinajace, którego suma wag krawędzi jest najmniejsza z możliwych. Czemu ta własność gwarantuje nam właśnie znalezienie tych cykli ?
Btw. Znaczy w poprzednim poście chodziło mi własnie o znalezienie wszystkich takich cykli, żeby się nie powtarzały, czyli cykl 1 2 3 1 = 2 3 1 2
[EDIT] - a co jesli bede mial graf niespojny ?

1

Może być dowolne rozpinające, ale minimalne gwarantuje minimalne długości cykli.
Dla siatki 2x2 masz 13 niepowtarzających się cykli, ale potrzebujesz tylko cztery z nich.

Dla niespójnego najpierw dzielisz na kilka spójnych, po czym robisz jak opisano, dla każdego z nich.
Oczywistym jest też że DFS też sobie z niespójnym nie poradzi.

0

Okej... To wszystko wiem. Dzięki wielkie za pomoc !

1 użytkowników online, w tym zalogowanych: 0, gości: 1