6-Amaliy mashg’uloti Графларни дастурда ифодалаш ва кўрикдан ўтказиш алгоритмлари дастурини тузиш. Графларда қисқа йўл топиш алгоритмлари

Adjacency Matrix

• Incidene matritsasi vakili u hisoblanayotganda O (Vx E) bo'sh joyni oladi. To'liq grafik uchun qirralarning soni V (V-1) / 2 bo'ladi. Shunday qilib, Incidene matritsasi xotirada katta joy egallaydi

Kirish



Chiqish

	E0	E1	E2	E3	E4	E5	E6	E7	E8
0	1	1	0	0	0	0	0	0	0
1	0	0	1	1	1	0	0	0	0
2	0	0	1	0	0	1	1	0	0
3	0	1	0	0	0	1	0	1	0
4	1	0	0	1	0	0	0	0	1
5	0	0	0	0	1	0	1	1	1

Algorithm

add_edge(u, v)

Kirish - chekkaning u va v {u, v}

Chiqish - G grafasining incedence matritsasi

Dastlab, incidene matritsasi uchun ed_cnt 0 ga teng chekka hisoblash mavjud.

#include

using namespace std;

int inc_arr[20][20]; // incidence matritsasini ushlab turish uchun dastlabki massiv

int ed_no = 0;

void displayMatrix(int v, int e) {

int i, j;

for(i = 0; i < v; i++) {

for(j = 0; j < e; j++) {

cout << inc_arr[i][j] << " ";}

cout << endl;}}

void add_edge(int u, int v) { // chekka raqami bilan matritsaga chekka qo'shish funktsiyasi

inc_arr[u][ed_no] = 1;

inc_arr[v][ed_no] = 1;

ed_no++; // chekka raqamini oshirish

}

main(int argc, char* argv[]) {

int v = 6; // grafada 6 ta tepalik mavjud

int e = 9; // grafada 9 ta chekka mavjud

add_edge(0, 4);

add_edge(0, 3);

add_edge(1, 2);

add_edge(1, 4);

add_edge(1, 5);

add_edge(2, 3);

add_edge(2, 5);

add_edge(5, 3);

add_edge(5, 4);

displayMatrix(v, e);

}

Qo'shnilik(qo'shni tugunlar) ro'yxati – bu A[n] massiv bo'lib, A[i] xar bir elementi i tugun bilan qo'shni tugunlar ro'yxatini o'zida saqlaydi.

Qo'shnilik(qo'shni tugunlar) ro'yxati qulaylik tomonlari quyidagilarda:

• 
  Joriy (berilgan) tugunga qo’shni tugunni izlash;
  
• 
  Tugun yoki qirra(yoy)larni qushish;
  
• 
  Siyrak graflar bilan ishlash.
  

Qo'shnilik(qo'shni tugunlar) ro'yxati noqulayliklari esa quyidagicha:

• 
  Qirra(yoy)ning mavjudligini tekshirish;
  
• 
  Tugun yoki qirra(yoy)larni o’chirish.
  

Adjacency List

Quyida grafik va unga teng keladigan qo'shni ro'yxatning namoyishi ko'rsatilgan.

// Adjascency List C++

#include

using namespace std;

// chekka qo'shish

void addEdge(vector adj[], int s, int d) {

adj[s].push_back(d);

adj[d].push_back(s);}

// Grafikni chop eting

void printGraph(vector adj[], int V) {

for (int d = 0; d < V; ++d) {

cout << "\n Tepalik "

<< d << ":";

for (auto x : adj[d])

cout << "-> " << x;

printf("\n");}}

int main() {

int V = 5;

// Grafik yaratish

vector adj[V];

// Qirralarning qo'shish

addEdge(adj, 0, 1);

addEdge(adj, 0, 2);

addEdge(adj, 0, 3);

addEdge(adj, 1, 2);

printGraph(adj, V);

}



Qirralar ro'yxati – qirralarning qo'shni tugunlar juftliklaridan iborat chiziqli ro'yxatdir.

Qo'shnilik(qo'shni tugunlar) ro'yxati qulaylik tomonlari quyidagilarda:

• 
  Qirra(yoy)larni qushish yoki o’chirish;
  
• 
  Yoylarning yuklanishi bo’yicha tartiblash;
  
• 
  Siyrak graflar bilan ishlash.
  

Qo'shnilik(qo'shni tugunlar) ro'yxati noqulayliklari esa quyidagicha:

• 
  Tugun va qirra(yoy)ning qo’shniligini aniqlash;
  
• 
  Berilgan tugunga intsidient qirra(yoy)larni tanlash.
  

Grafni qo'shni ro'yxatdagi qo'shilish va olib tashlash

Quyida grafik va uning qo'shni ro'yxati ko'rsatilgan:

Agar 1 va 4 orasidagi chekkani olib tashlash kerak bo'lsa, yuqoridagi grafik va qo'shni ro'yxat quyidagiga aylanadi:

Yondashuv: G'oyani grafikani vektorlar qatori sifatida ko'rsatishdir, shunda har bir vektor tepalikning qo'shni ro'yxatini aks ettiradi.

Chegarani qo'shish: chekka qo'shish shu chekka bilan bog'langan ikkala tepalikni bir-birining ro'yxatiga kiritish orqali amalga oshiriladi. Masalan, (u, v) orasidagi chekka qo'shilishi kerak bo'lsa, u v ning vektorlar ro'yxatida va v u ning vektorlar ro'yxatida saqlanadi. (Orqaga surish)

Chegarani o'chirish: (u, v) orasidagi chekkani o'chirish uchun u ning qo'shni ro'yxati v topilguncha va undan o'chirilguncha o'tadi. Xuddi shu amal v. (O'chirish) uchun ham amalga oshiriladi.

// Yuqoridagi yondashuvni C ++ dasturida amalga oshirish

#include

using namespace std;

// ga chekka qo'shish uchun yordamchi funktsiya

// yo'naltirilmagan grafik.

void addEdge(vector adj[], int u, int v){

adj[u].push_back(v);

adj[v].push_back(u);}

// an-dagi chekkani o'chirish uchun yordamchi funktsiya

// yo'naltirilmagan grafik.

void delEdge(vector adj[], int u, int v){

// Birinchi vektor ro'yxati orqali o'tish

// va undan ikkinchi elementni olib tashlash

for (int i = 0; i < adj[u].size(); i++) {

if (adj[u][i] == v) {

adj[u].erase(adj[u].begin() + i);

break;}}

// Ikkinchi vektor ro'yxati orqali o'tish

// va undan birinchi elementni olib tashlash

for (int i = 0; i < adj[v].size(); i++) {

if (adj[v][i] == u) {

adj[v].erase(adj[v].begin() + i);

break;}}}

// Qo'shni ro'yxatni chop etish uchun yordamchi funktsiya

// grafani aks ettirish

void printGraph(vector adj[], int V){

for (int v = 0; v < V; ++v) {

cout << "vertex " << v << " ";

for (auto x : adj[v])

cout << "-> " << x;

printf("\n");}

printf("\n");}

int main(){

int V = 5;

vector adj[V];

// Misol rasmda ko'rsatilgandek chekka qo'shish

addEdge(adj, 0, 1);

addEdge(adj, 0, 4);

addEdge(adj, 1, 2);

addEdge(adj, 1, 3);

addEdge(adj, 1, 4);

addEdge(adj, 2, 3);

addEdge(adj, 3, 4);

// adjacency matrix chiqarish

printGraph(adj, V);

// edge ni o'chirish (1, 4)

// misol rasmda ko'rsatilgandek

delEdge(adj, 1, 4);

// adjacency matrix ni chiqarish

printGraph(adj, V);

return 0;}



3. Graflarda ko'rik o'tkazish

Grafni ko'rikdan o'tkazish (Graph traversal) – bu berilgan tugundan boshlab barcha tugunlarni bir martadan ko'rib chiqish amalidir.

Ko’rikdan o’tkazish ikkita usuli mavjud:

Chuqurligiga (tubiga) qarab qidirish (Depth-First Search – DFS)

Kengligiga (eniga) qarab qidirish (Breadth-First Search – BFS)

Bu usullar berilgan X tugundan boshlab bironta konteynerni qo'llagan holda barcha tugunlarni ko'rib chiqadi.

Chuqurlikka qarab ko'rishda stek tuzilmasi qo'llaniladi.

Kenglikka qarab ko'rishda esa navbat tuzilmasidan foydalaniladi.

Tubiga qarab ko’rikni o’tqazish psevdokodi quyidagicha amalga oshiriladi

Kirish: n = 4, e = 6

2 -> 0, 0 -> 2, 1 -> 2, 0 -> 1, 3 -> 3, 1 -> 3

Chiqish: tepalikdan DFS 2: 2 0 1 3

DFS diagrammasi:

Algoritm:

Tugun va tashrif buyurilgan qator indeksini oladigan rekursiv funktsiyani yarating.

Joriy tugunni tashrif buyurgan sifatida belgilang va tugunni chop eting.

Barcha qo'shni va belgilanmagan tugunlarni aylanib o'ting va qo'shni tugun ko'rsatkichi bilan rekursiv funktsiyani chaqiring.

// dan DFS o'tkazilishini chop etish uchun C ++ dasturi

// berilgan grafadagi berilgan tepalik

#include

using namespace std;

// Grafik klassi yo'naltirilgan grafikani ifodalaydi

// qo'shni ro'yxatidan foydalanib

class Graph {

int V; // Tepaliklar soni

// o'z ichiga olgan qatorga ko'rsatgich

// qo'shni ro'yxatlar

list* adj;

// DFS tomonidan qo'llaniladigan rekursiv funktsiya

void DFSUtil(int v, bool visited[]);

public:

Graph(int V); // Konstruktor

// grafikka chekka qo'shish funktsiyasi

void addEdge(int v, int w);

// tepaliklarning DFS o'tishi

// v dan foydalanish mumkin

void DFS(int v);};

Graph::Graph(int V){

this->V = V;

adj = new list[V];}

void Graph::addEdge(int v, int w){

adj[v].push_back(w); }// V ning ro'yxatiga w ni qo'shing.

void Graph::DFSUtil(int v, bool visited[]){

// Joriy tugunni tashrif buyurgan sifatida belgilang va

// uni chop eting

visited[v] = true;

cout << v << " ";

// Qo'shni bo'lgan barcha tepaliklar uchun takrorlang

// ushbu tepalikka

list::iterator i;

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

if (!visited[*i])

DFSUtil(*i, visited);}

// tepaliklarning DFS oralig'ida v ga erishish mumkin.

// Bu rekursiv DFSUtil () dan foydalanadi

void Graph::DFS(int v){

// Barcha tepaliklarni tashrif buyurilmagan deb belgilang

bool* visited = new bool[V];

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

visited[i] = false;

// Rekursiv yordamchi funktsiyani chaqiring

// DFS-ni bosib o'tishni chop etish uchun

DFSUtil(v, visited);}

int main(){

// Yuqoridagi diagrammada berilgan grafikani 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 << "Quyidagi birinchi traversal chuqurligi"

" (tepalik 2 dan boshlab) \n";

g.DFS(2);

return 0;

}

Natija: Quyidagi birinchi traversal chuqurligi (tepalik 2 dan boshlab) : 2013

Kenglik bo'yicha birinchi qidiruv yoki grafik uchun BFS

Grafika uchun kenglik birinchi o'tish (yoki qidirish) daraxtning birinchi kenglik bo'ylab harakatlanishiga o'xshaydi ( ushbu xabarning 2-uslubiga qarang ). Daraxtlardan farqli o'laroq, grafikalar tsikllarni o'z ichiga olishi mumkin, shuning uchun biz yana bitta tugunga kelishimiz mumkin. Tugunni bir necha marta qayta ishlashga yo'l qo'ymaslik uchun biz mantiqiy tashrif buyurilgan qatordan foydalanamiz. Oddiylik uchun barcha tepaliklarga boshlang'ich tepalikdan erishish mumkin deb taxmin qilinadi.
Masalan, quyidagi grafada biz o'tishni 2-chi tepadan boshlaymiz. 0-chi cho'qqiga kelganda, uning barcha qo'shni tepalarini izlaymiz. 2 ham 0 ga teng bo'lgan vertexdir. Agar biz tashrif buyurgan tepalarni belgilamasak, u holda yana 2 qayta ishlanib, u tugamaydigan jarayonga aylanadi. Quyidagi grafikning birinchi kengligi 2, 0, 3, 1 ga teng.


Quyida berilgan manbadan oddiy Breadth First Traversal dasturining amallari keltirilgan.

// Berilganidan BFS o'tishini chop etish dasturi

// manba vertex. BFS (int s) tepaliklarni kesib o'tadi

// lardan foydalanish mumkin.

#include

#include

using namespace std;

// Bu sinf yordamida yo'naltirilgan grafikani ifodalaydi

// qo'shni ro'yxatining namoyishi

class Graph{

int V; // tepaliklar soni

// Yaqinlikni o'z ichiga olgan qatorga ko'rsatgich

// ro'yxatlar

list *adj;

public:

Graph(int V); // Konstruktor

// grafaga chekka qo'shish funktsiyasi

void addEdge(int v, int w);

// berilgan manbadan BFS o'tkazilishini chop etadi

void BFS(int s);};

Graph::Graph(int V){

this->V = V;

adj = new list[V];}

void Graph::addEdge(int v, int w){

adj[v].push_back(w);} // V ning ro'yxatiga w ni qo'shing.

void Graph::BFS(int s){

// Barcha tepaliklarni tashrif buyurilmagan deb belgilang

bool *visited = new bool[V];

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

visited[i] = false;

// BFS uchun navbat yaratish

list queue;

// Joriy tugunni tashrif buyurgan sifatida belgilang va uni ro'yxatdan o'tkazing

visited[s] = true;

queue.push_back(s);

// 'i' barcha qo'shni joylarni olish uchun ishlatiladi

// tepalik tepalari

list::iterator i;

while(!queue.empty()){

// Tepalikni navbatdan oling va uni chop eting

s = queue.front();

cout << s << " ";

queue.pop_front();

// Dequiatsiyalangan barcha qo'shni tepaliklarni oling

// vertex s. Agar qo'shni joyga tashrif buyurilmagan bo'lsa,

// keyin tashrif buyurganligini belgilang va uni ro'yxatdan o'tkazing

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

if (!visited[*i]){

visited[*i] = true;

queue.push_back(*i);}}}}

// Grafik klassi usullarini sinash uchun haydovchi dasturi

int main()

{

// Yuqoridagi diagrammada berilgan grafikani 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 << "Quyidagi kenglik birinchi traversal "

<< "(tepalik 2 dan boshlab) \n";

g.BFS(2);

return 0;

}
Quyida birinchi kenglik bo'ylab o'tish (2 vertikaldan boshlab)

2 0 3 1