Amaliy ish №6. Graflar: nazariya asoslari, algoritmlar qidiruv

AMALIY ISH №6. GRAFLAR: NAZARIYA ASOSLARI, ALGORITMLAR
Qidiruv
Ma'lumotlar tuzilishi sifatida grafikalar ko'plab muammolarni hal qilishda keng qo'llaniladi. Ular
ma'lumotlar, jarayon modellari, dastur tuzilmalari va
va hokazo biz ikkita asosiy masalani ko'rib chiqamiz:
1) dasturlarda grafikalarni taqdim etish;
2) grafiklardagi algoritmlar.
G = (V,E) grafigi tepaliklar to'plami deb nomlangan bo'sh bo'lmagan V to'plamini o'z ichiga oladi
(tugunlar) grafigi , to'plam E, bu grafikning qirralari to'plami va
ko'p sonli elementlarning ko'p juftlariga qirralarning to'plamlari V ga ko’rsatish.
1. Qo'shni matritsa
Ko'pincha grafik qo'shni matritsa sifatida ifodalanadi a[n] [n], unda a ij = 1,
agar (vi ,vj ) tegishli bo'lsa E, va ij =0 aks holda.
Qo'shni matritsalar V2 taxminan E ga teng bo'lganda (qirralarning soni)eng yaxshi qo'llaniladi.,
ya'ni, grafik zich bo'lganda. A_ij yozuvi i qirralarni qancha chekka bilan bog'lashini bildiradi tepalik j va tepalik i bo'yicha.

Yo'naltirilgan grafik, quyida uning qo'shni matritsasi ko'rsatilgan

Yuqoridagi yo'naltirilgan grafikni ifodalovchi 6 x 6 matritsa.
#include
using namespace std;
int matrix[20][20]; //матрица смежности изначально 0
int count = 0;
//следующая функция используется для вывода
void displayMatrix(int v) {
int i, j;
for(i = 0; i < v; i++) {
for(j = 0; j < v; j++) {
cout << matrix[i][j] << " ";
}
cout << endl;
}
}
void add_edge(int u, int v){ //функция добавления ребра в матрицу
matrix[u][v] = 1;
matrix[v][u] = 1;
}
int main() {
int v = 6; //в графе 6 вершин
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);
}
2. Qo'shni cho’qqilar ro'yxati
Grafik qo'shni ro'yxat sifatida taqdim etilganda, qator, qatorlar soni yaratiladi
bu grafaning uchlari soniga teng. Massivning har bir i-qatorida tepalik raqamlari mavjud,
i-cho’qqisi bilan qo'shni, ko'chadan chiqarib tashlanadi. Ro'yxat elementlari soni quyidagilarni belgilaydi
digrafdagi natijaning maksimal darajasi yoki yo'naltirilmagan maksimal darajasi
graf. Ushbu usul ustunda oz miqdordagi qirralar mavjud bo'lganda eng yaxshi qo'llaniladi, ya'ni
grafik siyrak bo'lganda. Agar sizda muvozanatli grafik bo'lsa, ya'ni grafikning har bir yo'lida og'irligi bor, ya'ni keyingi ro'yxatda yo'llar uchun juftliklar bo'ladi (qo'shni, vazn).
#include
using namespace std;
void showList(vector adj[], int n){
for (int k=0; kcout << k << ": -> ( ";
for (int i=0; icout << adj[k][i] << " ";
cout << ")\n";
}
}
void addEdge(vector adj[], int u, int v){
adj[u].push_back(v);
adj[v].push_back(u);
}
int main()
{
int v = 5; //5 вершин
vector adj[v];
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);
showList(adj,v);
}