Witam, jakie macie propozycje prezentacji grafów w C++?
mile widziany kod :)
0
0
I. e. macierz sąsiedztwa, wektor krawędzi i wierzchołków.
0
Macierz adjacencji, macierz incydencji, lista sąsiedztwa.
0
możecie dokładniej opisać te metody?
0
Macierz adiacencji to macierz VxV gdzie dla wierzchołków v1,v2 masz np. wartość 1 jeśli krawędź istnieje lub 0 jeśli nie
Macierz incydencji to macierz VxE gdzie dla krawędzi e masz np. wartość 1 przy dokładnie 2 wierzchołkach które ta krawędź łaczy
W przypadku listy sąsiedztwa masz tablicę wierzchołków i dla każdego wierzchołka masz listę jedno/dwukierunkową ze wskaźnikami do wierzchołków które są połączone krawędzią z tym wierzchołkiem.
0
Wszystko zależy od tego, co chcesz zrobić. Jakie operacje wykonywać na grafie, jaka jest struktura grafu. Graf skierowany? Rzadki? Usuwanie wierzchołków może zmieniać identyfikatory pozostałych? Jest masa czynników wpływających na wybór reprezentacji.
0
witam, zadam dziwne pytanie
do czego może służyć algorytm DFS i BFS, na czy m polega ich różnica, co mogę np. za ich pomocą znaleźć?
0
Tak trudno użyć googli / zajrzeć do książki?
0
ok, już wiem,
jaki to graf spójny, a jaki przechodni ?
0
Znalezienie odpowiedzi na te pytanie jest łatwiejsze niż na poprzednie. Graf spojony - to jest zbyt proste do znalezienia. jeżeli chodzi o graf przechodni to zapewne chodzi o domknięcie przechodnie.
1
Nie no koleś, tym postem to już rozwaliłeś mnie...
http://pl.wikipedia.org/wiki/Graf_sp%C3%B3jny
http://pl.wikipedia.org/wiki/Domkni%C4%99cie_przechodnie#Domkni.C4.99cie_przechodnie_grafu
0
w jaki sposób proponujecie reprezentować graf do przeszukiwania metodą BFS a jaką do DFS? tak aby było to najszybsze, oraz jak prezentować poszczególne dane?
0
Jeżeli graf jest rzadki to lista sąsiedztwa będzie odpowiednia. W obu algorytmach potrzebujesz łatwego iterowania po sąsiadach.
0
czyli proponujesz zastosowanie listy, w której węzłami będą numery wierzchołków, zaś elementy listy będą zawierać wskaźniki na inną listę, której elementy zawierają numery sąsiednich wierzchołków
0
W c++: robisz tablicę wektorów. Tablica ma rozmiar odpowiadający liczbie wierzchołków grafów.
0
a jak konkretnie to zrealizować, bo ja zacząłem robić listę jednokierunkową z numerem węzła oraz wskaźnikiem na liste (stl) zawierającą następników, ale nie wiem w końcu czy ja potrzebuje mieć zapamiętaną listę następników każdego węzła czy nie potrzebuję (w algorytmie BSF / DSF)
0
Utwórz wektor wektorów lub wektor list.
0
Może zainteresuj się http://www.boost.org/doc/libs/1_46_1/libs/graph/doc/index.html , skoro to c++. Żeby nie wynajdywać koła na nowo.