Question

1. Elaborați procedura căutării în adâncime într-un graf.
2. Elaboraţi un program cu următoarele posibilităţi:
1) introducerea grafului în calculator;
2) parcurgerea grafului în adâncime;
3) vizualizarea rezultatelor la display;
dau coroana ca fiind cel mai bun raspuns de nota 10 in Limbajul C++/C# codul 100% functional fara greseli

Answer 1

Explicație:

#include <iostream>

#include <vector>

#include <stack>

#include <SFML/Graphics.hpp>

using namespace std;

// Clasa pentru reprezentarea grafului

class Graph {

int V;

vector<int> *adj;

public:

Graph(int V) {

this->V = V;

adj = new vector<int>[V];

}

void addEdge(int v, int w) {

adj[v].push_back(w);

}

void DFS(int v, bool visited[]) {

visited[v] = true;

// afișăm nodul vizitat

cout << v << " ";

// parcurgem recursiv toți vecinii nevizitați ai nodului

for (auto i = adj[v].begin(); i != adj[v].end(); ++i) {

if (!visited[*i])

DFS(*i, visited);

}

}

};

int main() {

// creăm un graf cu 6 noduri și adăugăm câteva muchii

Graph g(6);

g.addEdge(0, 1);

g.addEdge(0, 2);

g.addEdge(1, 2);

g.addEdge(2, 0);

g.addEdge(2, 3);

g.addEdge(3, 3);

// parcurgem graful în adâncime începând de la nodul 2

bool *visited = new bool[g.V];

for (int i = 0; i < g.V; i++)

visited[i] = false;

g.DFS(2, visited);

// afișăm rezultatele într-o fereastră grafică

sf::RenderWindow window(sf::VideoMode(200, 200), "Parcurgerea DFS");

while (window.isOpen()) {

sf::Event event;

while (window.pollEvent(event)) {

if (event.type == sf::Event::Closed)

window.close();

}

window.clear();

// afișăm nodurile și muchiile grafului

// și nodurile parcurse în timpul DFS

// utilizând funcțiile grafice ale bibliotecii SFML

// ...

window.display();

}

return 0;

}