• 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

VPS Starter Arubacloud
0 głosów
309 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 (42,000 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 (42,000 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 429 wizyt
pytanie zadane 21 października 2015 w C i C++ przez szmq Pasjonat (22,770 p.)
0 głosów
1 odpowiedź 226 wizyt
pytanie zadane 26 kwietnia 2015 w C i C++ przez keresmi Użytkownik (770 p.)
0 głosów
0 odpowiedzi 94 wizyt
pytanie zadane 14 listopada 2022 w HTML i CSS przez MacGyver Nowicjusz (120 p.)

92,454 zapytań

141,263 odpowiedzi

319,099 komentarzy

61,854 pasjonatów

Motyw:

Akcja Pajacyk

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

Oto polecana książka warta uwagi.
Pełną listę książek znajdziesz tutaj.

Akademia Sekuraka

Akademia Sekuraka 2024 zapewnia dostęp do minimum 15 szkoleń online z bezpieczeństwa IT oraz dostęp także do materiałów z edycji Sekurak Academy z roku 2023!

Przy zakupie możecie skorzystać z kodu: pasja-akademia - użyjcie go w koszyku, a uzyskacie rabat -30% na bilety w wersji "Standard"! Więcej informacji na temat akademii 2024 znajdziecie tutaj. Dziękujemy ekipie Sekuraka za taką fajną zniżkę dla wszystkich Pasjonatów!

Akademia Sekuraka

Niedawno wystartował dodruk tej świetnej, rozchwytywanej książki (około 940 stron). Mamy dla Was kod: pasja (wpiszcie go w koszyku), dzięki któremu otrzymujemy 10% zniżki - dziękujemy zaprzyjaźnionej ekipie Sekuraka za taki bonus dla Pasjonatów! Książka to pierwszy tom z serii o ITsec, który łagodnie wprowadzi w świat bezpieczeństwa IT każdą osobę - warto, polecamy!

...