Descrierea proiectului
Grafuri, arbori și arbori binari în C++
Acest proiect este o aplicație C++ de consolă dedicată studiului grafurilor neorientate, grafurilor orientate, arborilor și arborilor binari, oferind prelucrări interactive din meniu și generarea unui raport complet în output/out.txt.
Compatibilitate
Proiectul funcționează pe Windows, macOS și Linux.
Proiectul poate fi deschis, compilat și rulat cu MinGW, Code::Blocks, Visual Studio Code și alte IDE-uri compatibile C++, precum Visual Studio, CLion, Qt Creator sau Dev-C++.
Documentație
Acest proiect este însoțit de documentația Microsoft Word aferentă proiectului, iar această documentație conține 37 de pagini.
Ce conține proiectul
- src/ conține fișierele sursă principale: main.cpp, Graf.cpp, Arbore.cpp, ArboreBinar.cpp și Utils.cpp.
- include/ conține fișierele header Graf.h, Arbore.h, ArboreBinar.h și Utils.h.
- data/input/ conține fișierele de intrare pentru graf neorientat, graf orientat, arbore, arbore binar, fișierul universal in.txt și datele elevului din contact.txt.
- data/generated/ conține fișierele de test generate automat de aplicație.
- output/ conține raportul final generat în fișierul out.txt.
- build/ conține fișierele obținute la compilare.
- bin/ conține executabilul proiectului.
- Makefile oferă compilarea și rularea din terminal.
- README.md descrie structura proiectului și modul de utilizare.
Module și rolul lor
- main.cpp gestionează introducerea teoretică, meniul principal, submeniurile, încărcarea fișierelor și generarea raportului final.
- Graf.cpp și Graf.h implementează reprezentările grafurilor și algoritmii de bază pentru grafuri orientate și neorientate.
- Arbore.cpp și Arbore.h implementează operațiile specifice arborilor, precum rădăcina, vectorul de tați, nivelurile, LCA, distanța, centrele și diametrul.
- ArboreBinar.cpp și ArboreBinar.h implementează operațiile specifice arborilor binari, inclusiv parcurgeri, statistici și proprietăți speciale.
- Utils.cpp și Utils.h oferă funcții de citire, validare, formatare, afișare și utilitare pentru consolă.
Structura meniului proiectului
La pornire, aplicația afișează o scurtă introducere teoretică despre grafuri, arbori, arbori binari și algoritmii utilizați, după care utilizatorul intră în meniul principal.
-
Lucru cu graf neorientat - deschide submeniul dedicat analizării unui graf neorientat citit din fișier.
- 1. Citire din data/input/graf_neorientat.txt - încarcă în memorie un graf neorientat din fișierul dedicat.
- 2. Afișare muchii / matrice / listă - afișează muchiile grafului și reprezentările sale principale.
- 3. DFS recursiv - execută parcurgerea în adâncime în varianta recursivă dintr-un nod de start ales.
- 4. DFS iterativ - execută parcurgerea în adâncime în varianta iterativă.
- 5. BFS - realizează parcurgerea pe niveluri a grafului pornind din nodul selectat.
- 6. Grade, noduri izolate și terminale - calculează gradele nodurilor și identifică nodurile izolate sau terminale.
- 7. Componente conexe și conexitate - verifică dacă graful este conex și afișează componentele conexe.
- 8. Detectare ciclu și verificare arbore - verifică prezența ciclurilor și dacă graful poate fi considerat arbore.
- 9. Drum simplu și drum minim între două noduri - caută un drum simplu și drumul minim între două noduri date.
- 10. Comparație reprezentări - prezintă diferențele dintre matricea de adiacență și lista de adiacență.
- 0. Înapoi - revine în meniul principal.
-
Lucru cu graf orientat - deschide submeniul pentru operații pe grafuri orientate.
- 1. Citire din data/input/graf_orientat.txt - încarcă din fișier un graf orientat pentru prelucrări ulterioare.
- 2. Afișare arce / matrice / listă - afișează arcele grafului și reprezentările sale interne.
- 3. DFS recursiv - rulează parcurgerea DFS recursivă din nodul ales de utilizator.
- 4. DFS iterativ - rulează parcurgerea DFS iterativă.
- 5. BFS - execută parcurgerea BFS și afișează ordinea vizitării.
- 6. Grade interioare / exterioare - calculează pentru fiecare nod gradul interior și gradul exterior.
- 7. Noduri sursă / destinație - identifică nodurile sursă și nodurile destinație ale grafului orientat.
- 8. Conexitate slabă / tare - verifică dacă graful este slab conex și dacă este tare conex.
- 9. Detectare ciclu și sortare topologică - detectează ciclurile și afișează sortarea topologică atunci când aceasta este posibilă.
- 10. Drum simplu și drum minim - determină un drum simplu și un drum minim între două noduri introduse.
- 11. Comparație reprezentări - oferă o comparație între reprezentările folosite.
- 0. Înapoi - revine la meniul principal.
-
Lucru cu arbore - deschide submeniul pentru analiza unui arbore rădăcinat.
- 1. Citire din data/input/arbore.txt - încarcă arborele din fișierul dedicat.
- 2. Afișare muchii / matrice / listă - afișează muchiile și reprezentările arborelui.
- 3. Schimbare rădăcină - rerădăcinează arborele pentru a obține o altă organizare a nodurilor.
- 4. Vector de tați și niveluri - construiește și afișează vectorul de tați și nivelul fiecărui nod.
- 5. Înălțime, frunze, noduri interne - calculează indicatorii structurali de bază ai arborelui.
- 6. Drum de la rădăcină la un nod - afișează drumul unic dintre rădăcina curentă și nodul cerut.
- 7. Strămoși și descendenți - determină strămoșii și descendenții unui nod ales.
- 8. LCA și distanța dintre două noduri - calculează cel mai mic strămoș comun și distanța dintre două noduri.
- 9. Centre și diametru - identifică centrele arborelui și drumul de diametru maxim.
- 10. Afișare pe niveluri - afișează arborele organizat pe niveluri.
- 0. Înapoi - revine la meniul principal.
-
Lucru cu arbore binar - deschide submeniul pentru reprezentarea și prelucrarea arborilor binari.
- 1. Citire din data/input/arbore_binar.txt - încarcă arborele binar definit prin vectorii de fii.
- 2. Afișare vectori S, D și muchii - afișează vectorii de fii stâng și drept, precum și muchiile corespunzătoare.
- 3. Afișare matrice și listă de adiacență - afișează reprezentările arborelui binar sub formă de matrice și listă.
- 4. Preordine - execută parcurgerea preordine a arborelui binar.
- 5. Inordine - execută parcurgerea inordine a arborelui binar.
- 6. Postordine - execută parcurgerea postordine a arborelui binar.
- 7. Parcurgere pe niveluri - afișează nodurile pe niveluri folosind o parcurgere de tip BFS.
- 8. Înălțime și statistici de noduri - calculează înălțimea și statisticile principale ale nodurilor.
- 9. Proprietăți speciale - verifică dacă arborele este strict, complet, aproape complet, perfect, echilibrat, degenerat sau de căutare binară.
- 10. Oglindire - inversează subarborii stâng și drept pentru a obține imaginea în oglindă.
- 11. Drum până la un nod - afișează drumul de la rădăcină până la nodul cerut.
- 0. Înapoi - revine la meniul principal.
- Încarcă o structură din data/input/in.txt (format universal: tip 1-4) - citește rapid o singură structură pe baza codului de tip din fișierul universal.
- Generează fișiere exemplu de test în data/generated/ - creează automat fișiere noi de test pentru demonstrații și verificări.
- Generează raportul structurilor încărcate în output/out.txt - construiește un raport text cu toate structurile încărcate în sesiunea curentă.
- Citește datele elevului din data/input/contact.txt - încarcă datele elevului și le poate include în raportul final.
- Ieșire - închide aplicația.
