4-amaliy mashg’uloti. Bog'langan ro'yxat. Saralash masalalari. Qidiruv usullari. Daraxtlar bilan ishlash masalalari. Graflar: nazariya asoslari, algoritmlar

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);
}