reprezentacja grafu nieskierowanego za pomocą wektora list

Question

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 ;(

 

 

 

Comments

Warto poznać problem od strony czysto teoretycznej. https://eduinf.waw.pl/inf/alg/001_search/0122.php
Chyba, że chcesz to komuś zlecić...

---

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.

---

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.