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

reprezentacja grafu nieskierowanego za pomocą wektora list

0 głosów
45 wizyt
pytanie zadane 16 grudnia 2020 w C i C++ przez kiuyama Nowicjusz (190 p.)

Cześć, jako zaliczenie przedmiotu muszę napisać program, który będzie przeszukiwał metodą DFS graf nieskierowany. Program ma wypisać, że graf jest dwudzielny lub nie, a jeśli jest, to dodatkowo wypisać jego 2 grupy. Graf ma być reprezentowany za pomocą wektora list. Mój problem polega na tym, że całkowicie pogubiłem się w jaki sposób mogę to zrobić. Wydaję mi się, że najprościej dla mnie byłoby użyć tych funkcji i zmiennych:

#include <iostream>
#include <vector>
#include <list>

using namespace std;

void DFS();
void dodaj_krawedz(vector<list<int>> lista_sasiedztwa, int u, int v) {
       lista_sasiedztwa[u].push_back(v);
       lista_sasiedztwa[v].push_back(u);
}

int main() {

int n;
vector<list<int>> lista_sasiedztwa;
vector<bool> odwiedzone;
vector<int> kolor;

}

Niestety nie mam pojęcia jak zrobić, żeby wyświetlać jedynie wierzchołki, które zostaną podane przez użytkownika, czyli np. jeśli nie poda wierzchołka 0 i 2, to przy wyświetlaniu grafu nie pojawią się te cyfry jako węzły. Mam również problem czy wpakować to w jakąś strukturę graf, czy może jednak zostawić tablice i zmienne w main'ie.

Proszę o wytłumaczenie, czas mi się kończy, a pomysłów brak ;(

 

 

 

komentarz 16 grudnia 2020 przez tkz Nałogowiec (41,420 p.)
Warto poznać problem od strony czysto teoretycznej. https://eduinf.waw.pl/inf/alg/001_search/0122.php
Chyba, że chcesz to komuś zlecić...
komentarz 16 grudnia 2020 przez kiuyama Nowicjusz (190 p.)
Właśnie trudno jest mi znaleźć przykłady dla wektora list, chyba, że to co widzę prawie wszędzie jest tym czego szukam... Robię co mogę, żeby to zrozumieć i chciałbym to napisać sam. Nawet nie wiem gdzie miałbym szukać kogoś, kto pomógł by mi to napisać. Wiem w jaki sposób działa przechodzenie grafu w głąb, ale od strony technicznej leżę, bo mieliśmy na uczelni jedynie miesiąc podstaw programowania i teraz sam muszę zrobić coś takiego. Byłbym wdzięczny jakby mi ktoś podał chociaż prosty przykład wyświetlenia grafu zapisanego w taki sposób.
komentarz 17 grudnia 2020 przez tkz Nałogowiec (41,420 p.)
https://stackoverflow.com/questions/39708305/dfs-implementation-in-c-using-adjacency-list-using-vector-and-linked-list O ile rozumiesz same założenia, już napisany kod nie powinien być aż tak trudny do zrozumienia. "DFS vector list c++" po wpisaniu tych czterech fraz jest milion wyników, jesem przekonany, że znajdziesz tam rozwiązanie.

Zaloguj lub zarejestruj się, aby odpowiedzieć na to pytanie.

Podobne pytania

0 głosów
2 odpowiedzi 224 wizyt
pytanie zadane 21 października 2015 w C i C++ przez szmq Pasjonat (22,820 p.)
0 głosów
1 odpowiedź 147 wizyt
pytanie zadane 26 kwietnia 2015 w C i C++ przez keresmi Użytkownik (770 p.)
+1 głos
1 odpowiedź 937 wizyt
pytanie zadane 11 maja 2015 w C i C++ przez keresmi Użytkownik (770 p.)

86,427 zapytań

135,187 odpowiedzi

300,309 komentarzy

57,184 pasjonatów

Motyw:

Akcja Pajacyk

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

Oto dwie polecane książki warte uwagi. Pełną listę znajdziesz tutaj.

...