Witam,
właśnie tworzę projekt za zajęcia z podstaw programowania. Tematem jest wyszukiwanie cyklu w grafie skierowanym. Na wejściu dostaję plik tekstowy zawierający krawędzie w formacie <wierzchołek_początkowy> -> <wierzchołek_końcowy> gdzie każda krawędź jest oddzielona przecinkiem. Wynikiem działania programu powinien być plik tekstowy zawierający wierzchołki należące do cyklu, każdy cykl w osobnej linii.
Głównym założeniem projektu jest brak możliwości korzystania z gotowych struktur i kontenerów.
Struktura którą sam zaprojektowałem to lista wierzchołków, gdzie każdy element zawiera swoją listę wskaźników na wierzchołki z którymi jest połączony.
Do tej pory udało mi się zaimplementować wczytywanie krawędzi z pliku i wypełnienie nimi mojej struktury oraz wypisywanie wszystkich elementów grafu (póki co w konsoli)
Stanąłem teraz przed głównym problemem czyli utworzeniem funkcji wyszukującej cykl i za żadne skarby nie umiem wymyślić porządnego algorytmu. I tu moja prośba do Was forumowicze! Czy potrafilibyście mnie nakierować jak zabrać się za tą funkcję itd.?
Oto kod mojego dotychczasowego programu
#include <iostream>
#include <sstream>
#include <string>
#include <fstream>
using namespace std;
struct krawedz;
struct wierzcholek
{
int numer;
wierzcholek *pNext;
krawedz *pKrawedzie;
};
struct krawedz
{
wierzcholek * pEdge;
krawedz * pDown;
};
wierzcholek * zwroc_adres_wierzcholka(wierzcholek *&pHead, int szukana)
{
if (!pHead)
{
return pHead = new wierzcholek{ szukana,pHead,0 };
}
auto p = pHead;
while (p->pNext && p->numer != szukana)
{
p = p->pNext;
}
if (p->numer == szukana)
{
return p;
}
p = new wierzcholek{ szukana,pHead,0 };
pHead = p;
return p;
}
void dodaj_krawedz(wierzcholek *& pHead, int pierwszy, int drugi)
{
wierzcholek *peak = zwroc_adres_wierzcholka(pHead, pierwszy);
wierzcholek *edge = zwroc_adres_wierzcholka(pHead, drugi);
auto glowa_podlisty = peak->pKrawedzie;
krawedz *p = new krawedz{ edge,glowa_podlisty };
glowa_podlisty = p;
peak->pKrawedzie = p;
}
string usun_strzalke(string &linia)
{
for (int i = 0; i < linia.size(); i++)
{
if (linia[i] == '-' || linia[i] == '>')
{
linia[i] = ' ';
}
}
return linia;
}
void wypisz_krawedzie(krawedz *pHead)
{
while (pHead)
{
cout << "krawedz: " << pHead->pEdge->numer << endl;
pHead = pHead->pDown;
}
}
void wypisz_wszystko(wierzcholek *pHead)
{
while (pHead)
{
cout << "wierzcholek: " << pHead->numer << endl;
wypisz_krawedzie(pHead->pKrawedzie);
pHead = pHead->pNext;
}
}
int main()
{
wierzcholek *glowa = 0;
ifstream plik_wejsciowy;
plik_wejsciowy.open("wejscie.txt");
string linia;
int wierzcholek_poczatkowy, wierzcholek_koncowy;
while (getline(plik_wejsciowy, linia, ','))
{
istringstream iss(usun_strzalke(linia));
iss >> wierzcholek_poczatkowy >> wierzcholek_koncowy;
//cout << wierzcholek_poczatkowy << endl << wierzcholek_koncowy << endl;
dodaj_krawedz(glowa, wierzcholek_poczatkowy, wierzcholek_koncowy);
}
wypisz_wszystko(glowa);
return 0;
}