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

Răspuns:

Explicație:

Procedura căutării în adâncime (DFS) într-un graf este următoarea:

Se selectează un nod de start.

Se marchează nodul de start ca vizitat și se adaugă într-o stivă.

Se extrage un nod din vârful stivei și se vizitează toți vecinii săi nevizitați.

Pentru fiecare vecin nevizitat, se marchează ca vizitat și se adaugă în stivă.

Se repetă pasul anterior până când stiva devine goală.

Programul în limbajul C++ pentru parcurgerea unui graf în adâncime și vizualizarea rezultatelor la display ar putea arăta astfel:

cpp

Copy code

#include <iostream>

#include <vector>

#include <stack>

using namespace std;

// Clasa pentru un nod în graf

class Node {

public:

   int val;

   bool visited;

   vector<Node*> neighbors;

   Node(int v) {

       val = v;

       visited = false;

   }

   void addNeighbor(Node* n) {

       neighbors.push_back(n);

   }

};

// Funcția pentru parcurgerea în adâncime a grafului

void dfs(Node* start) {

   stack<Node*> s;

   s.push(start);

   start->visited = true;

   while (!s.empty()) {

       Node* curr = s.top();

       s.pop();

       cout << curr->val << " ";

       for (Node* n : curr->neighbors) {

           if (!n->visited) {

               n->visited = true;

               s.push(n);

           }

       }

   }

}

int main() {

   // Crearea nodurilor și legarea lor într-un graf

   Node* node1 = new Node(1);

   Node* node2 = new Node(2);

   Node* node3 = new Node(3);

   Node* node4 = new Node(4);

   Node* node5 = new Node(5);

   node1->addNeighbor(node2);

   node1->addNeighbor(node3);

   node2->addNeighbor(node4);

   node3->addNeighbor(node4);

   node4->addNeighbor(node5);

   // Apelul funcției DFS și afișarea rezultatelor

   cout << "Parcurgerea in adancime a grafului este: ";

   dfs(node1);

   cout << endl;

   return 0;

}