reprezentacja grafów w C++

Witam!

Mam takie pytanie: jak najlepiej zrobić reprezentację grafów w C++? Chodzi mi np. o reprezentację wierzchołków, krawędzi itp. Czy dobrze jest stosować klasy/struktury? Jeżeli tak to w jaki sposób?
Problem wynika z algorytmów do przeszukiwania grafów, znajdowania najkrótszej ścieżki itp. W literaturze wszystko jest napisane w pseudokodzie i mam problem z przeniesieniem tego do C++.
Gdyby ktoś miał jakieś reprezentacje Bellmana-Forda, Dijkstry, Kruskala, Prima albo inne to też prosiłbym o zapodanie ;)

Pozdrawiam

Graf można reprezentować za pomocą zwykłej dwuwymiarowej tablicy n x n, gdzie n- ilosc wierzchołków. Polega to na tym, że w komórce o indeksie i,j wpisana jest wartość drogi od wierzchołka o numerze i do wierzchołka j.

Oczywiście można użyć też struktur. Znajdź i rozgryź implementacje listy na wskaźnikach np tu. Wtedy stworzenie drzewa nie będzie dla ciebie problemem.

Taaak dwuwymiarowa tablica jest spoko, ale dla n=100000 już nie przechodzi pamięciowo. Polecam tablicę vectorów z STL. Jak to poznasz, to napisanie reprezentacji grafu to będzie 5 minut, a nie kilka godzin implementowania drzew (jak dobrze pójdzie :) )

Ogólnie warto się zapoznać z stl, gdyż to naprawdę może bardzo dużo ułatwić. Vector na początek, a potem priority_queue i już będziesz umiał praktycznie dijkstre bez całej znajomości i implementacji stosu ;p

To jak ktoś może się nauczyć czegoś jak wszystko ma mieć gotowe. Powinien choć raz sam wszystko napisać, stos, kolejkę, drzewa, grafy, itp.
Graf powinieneś zaimplementować jako listę sąsiedzką czyli tablice wierzchołków i każdy wierzchołek ma listę powiązań i dla każdego wierzchołka zazwyczaj trzyma się 2-3 integery potrzebne od przeszukiwańDo , kolorowania, grupowania, itp.
A kolejka priorytetowa też nie jest trudna, najczęściej robi się ją jako kopiec w tablicy, ale też można jak drzewo. Do Dijkstry można użyć kopca, listy lub tablicy, jak sortujesz przez scalanie to to wszystko jedno.
B-F tylko na listach sąsiedzkich bo przy listach złożoność to O(nm), a w tablicy O(n^3)
Nie wiem jak można w ogóle powiedzieć, że bez drzew się obejdzie. Przecież Prim czy Kruskal tworzą właśnie takie drzewa. Do prima trzeba mieć kolejkę piorytetową, do Kruskala wystarczy tablica, bo sprytnie go robiąc złożoność jest O(logn), więc bardzo mała.
Edit:
I nie wiem skąd te kilka godzin ma zająć, napisanie struktury w której jest implementowany graf z funkcją dodawania ścieżek/ usuwania i czyszczenia to żaden problem.

Force napisał(a)

To jak ktoś może się nauczyć czegoś jak wszystko ma mieć gotowe. Powinien choć raz sam wszystko napisać, stos, kolejkę, drzewa, grafy, itp.
Dokładnie

Force napisał(a)

Graf powinieneś zaimplementować jako listę sąsiedzką czyli tablice wierzchołków i każdy wierzchołek ma listę powiązań i dla każdego wierzchołka zazwyczaj trzyma się 2-3 integery potrzebne od przeszukiwańDo , kolorowania, grupowania, itp.

Jeśli chodzi o reprezentacje to jak dla mnie:

• lista następników - chyba najbardziej rozsądna, chociaż nie dla wszystkich problemów ( sprawdzanie istnienia incydencji można zrobić lepiej )
• macierz sąsiedztwa - najłatwiejsza jak dla mnie 1 albo 0 i wszystko w temacie, taka na szybko
• macierz grafu - dla smakoszy, fajnie się pisze, mimo że, na początku wydaje się extra trudna

No i trzeba dobierać do problemu.

gosciu123456 napisał(a)

Witam!

Mam takie pytanie: jak najlepiej zrobić reprezentację grafów w C++? Chodzi mi np. o reprezentację wierzchołków, krawędzi itp. Czy dobrze jest stosować klasy/struktury? Jeżeli tak to w jaki sposób?
Problem wynika z algorytmów do przeszukiwania grafów, znajdowania najkrótszej ścieżki itp. W literaturze wszystko jest napisane w pseudokodzie i mam problem z przeniesieniem tego do C++.
Gdyby ktoś miał jakieś reprezentacje Bellmana-Forda, Dijkstry, Kruskala, Prima albo inne to też prosiłbym o zapodanie ;)

Pozdrawiam

Boost ma.