Guruh: swd026-2 Talaba: Muhammadov Murodjon 1-vazifa

“Ma’lumotlar tuzilmasi va algoritmlar» fanidan topshiriq bo’yicha hisobot
Topshiriq: 1
Guruh: SWD026-2
Talaba: Muhammadov Murodjon

1-vazifa Elementlardan iborat graf yaratilsin. Foydalanuvchi kiritgan element grafdan BFS usulida qidirib topilsin.

#include

using namespace std;

class Graph
{
int V; // Cho'qqilar soni
// Qo'shnilikni o'z ichiga olgan massivga ko'rsatgich
// ro'yxatlar
vectorint>> adj;
public:
Graph(int V); // Konstruktor
// grafikga chekka qo'shish funksiyasi
void addEdge(int v, int w);
// berilgan manbadan BFS o'tishini chop etadi s
void BFS(int s);
};
Graph::Graph(int V)
{
this->V = V;
adj.resize(V);
}
void Graph::addEdge(int v, int w)
{
adj[v].push_back(w);
}
void Graph::BFS(int s)
{
// Barcha uchlarini tashrif buyurilmagan deb belgilang
vector<bool> visited;
visited.resize(V,false);
// BFS uchun navbat yarating
list<int> queue;
// Joriy tugunni tashrif buyurilgan deb belgilang va uni navbatga qo'ying
visited[s] = true;
queue.push_back(s);
while(!queue.empty())
{
// Cho'qqini navbatdan ajratib oling va uni chop eting
s = queue.front();
cout << s << " ";
queue.pop_front();
// O'chirilgan barcha qo'shni uchlarini oling
// tepa s. Agar qo'shni tashrif buyurmagan bo'lsa,
// keyin tashrif buyurilganligini belgilang va uni navbatga qo'ying
for (auto adjecent: adj[s])
{
if (!visited[adjecent])
{
visited[adjecent] = true;
queue.push_back(adjecent);
}
}
}
}
// Grafik sinf usullarini sinab ko'rish uchun haydovchi dasturi
int main()
{
// Yuqoridagi diagrammada berilgan grafikni yarating
Graph g(4);
g.addEdge(0, 1);
g.addEdge(0, 2);
g.addEdge(1, 2);
g.addEdge(2, 0);
g.addEdge(2, 3);
g.addEdge(3, 3);
cout<< "(choqqi 2 dan boshlanadi) \n";
g.BFS(2);
return 0;
}