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:
- 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.
- 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.