Algoritmlarni loyihalash” fanidan laboratoriya ishlari

Amliy qism
Grafik - bu quyidagi ikki komponentdan iborat ma'lumotlar tuzilishi.
1. Tugunlar deb ham ataladigan cheklangan tepaliklar to'plami.
2. Shaklning tartiblangan juftligining cheklangan to'plami (u, v) chekka deb nomlanadi. Juftlik buyurtma qilingan, chunki (u, v) yo'naltirilgan grafik (di-grafik) holatida (v, u) bilan bir xil emas. Shaklning juftligi (u, v) u vertikaldan v tepaga qadar bir chekka borligini bildiradi, qirralarning vazni / qiymati / narxi bo'lishi mumkin.
Grafikalar hayotdagi ko'plab dasturlarni namoyish qilish uchun ishlatiladi: Grafikalar tarmoqlarni aks ettirish uchun ishlatiladi. Tarmoqlar shahar yoki telefon tarmog'idagi yoki elektron tarmoqdagi yo'llarni o'z ichiga olishi mumkin. Graflar, shuningdek, LinkIn, Facebook kabi ijtimoiy tarmoqlarda qo'llaniladi. Masalan, Facebook-da har bir odam vertex (yoki tugun) bilan ifodalanadi. Har bir tugun tuzilishga ega va shaxs identifikatori, ismi, jinsi va joyi kabi ma'lumotlarni o'z ichiga oladi. Grafikning ko'proq ilovalari uchun buni ko'ring.
Quyida 5 ta tepalikka ega bo'lgan yo'naltirilmagan grafikaga misol keltirilgan.

Quyidagi ikkitasi grafikaning eng ko'p ishlatiladigan tasvirlari.
1. Yaqinlik matritsasi
2. Yaqinlik ro'yxati
Shuningdek, boshqa hodisalar ham mavjud, "Intsident Matrix" va "Incident List". Grafik tasvirini tanlash vaziyatga xosdir. Bu butunlay bajariladigan operatsiyalar turiga va ulardan foydalanish qulayligiga bog'liq.
Yaqinlik ro'yxati:
Bir qator ro'yxatlar ishlatiladi. Massivning kattaligi tepalar soniga teng. Massiv bir qator bo'lsin []. Kirish massivi [i] ith vertexga qo'shni bo'lgan tepalar ro'yxatini aks ettiradi. Ushbu tasvir vaznli grafikani ko'rsatish uchun ham ishlatilishi mumkin. Qirralarning og'irliklari juftliklar ro'yxati sifatida ifodalanishi mumkin. Yuqorida keltirilgan grafikning qo'shni ro'yxati ko'rsatilgan.



Topshiriqlar.

1. 
   Graflarning ro’yxat tuzilmasidan foydalanib yuqoridagi chizmani dasturiy kodi tuzilsin va ekranga chiqarilsin.
   

2. 
   Graflarning ro’yxat tuzilmasidan foydalanib yuqoridagi chizmani dasturiy kodi tuzilsin va ekranga chiqarilsin.
   

3. 
   Graflarning ro’yxat tuzilmasidan foydalanib yuqoridagi chizmani dasturiy kodi tuzilsin va ekranga chiqarilsin.
   

4. 
   Graflarning ro’yxat tuzilmasidan foydalanib yuqoridagi chizmani dasturiy kodi tuzilsin va ekranga chiqarilsin.
   

5. 
   Graflarning ro’yxat tuzilmasidan foydalanib yuqoridagi chizmani dasturiy kodi tuzilsin va ekranga chiqarilsin.
   

6. 
   Graflarning ro’yxat tuzilmasidan foydalanib yuqoridagi chizmani dasturiy kodi tuzilsin va ekranga chiqarilsin.
   

7. 
   Graflarning ro’yxat tuzilmasidan foydalanib yuqoridagi chizmani dasturiy kodi tuzilsin va ekranga chiqarilsin.
   

8. 
   Graflarning ro’yxat tuzilmasidan foydalanib yuqoridagi chizmani dasturiy kodi tuzilsin va ekranga chiqarilsin.
   

9. 
   Graflarning ro’yxat tuzilmasidan foydalanib yuqoridagi chizmani dasturiy kodi tuzilsin va ekranga chiqarilsin.
   

10. 
    Graflarning ro’yxat tuzilmasidan foydalanib yuqoridagi chizmani dasturiy kodi tuzilsin va ekranga chiqarilsin.
    

Javob
#include
using namespace std;
// stores adjacency list items
struct adjNode {
int val, cost;
adjNode* next;
};
// structure to store edges
struct graphEdge {
int start_ver, end_ver, weight;
};
class DiaGraph{
// insert new nodes into adjacency list from given graph
adjNode* getAdjListNode(int value, int weight, adjNode* head) {
adjNode* newNode = new adjNode;
newNode->val = value;
newNode->cost = weight;
newNode->next = head; // point new node to current head
return newNode;
}
int N; // number of nodes in the graph
public:
adjNode **head; //adjacency list as array of pointers
// Constructor
DiaGraph(graphEdge edges[], int n, int N) {
// allocate new node
head = new adjNode*[N]();
this->N = N;
// initialize head pointer for all vertices
for (int i = 0; i < N; ++i)
head[i] = nullptr;
// construct directed graph by adding edges to it
for (unsigned i = 0; i < n; i++) {
int start_ver = edges[i].start_ver;
int end_ver = edges[i].end_ver;
int weight = edges[i].weight;
// insert in the beginning
adjNode* newNode = getAdjListNode(end_ver, weight, head[start_ver]);
// point head pointer to new node
head[start_ver] = newNode;
}
}
// Destructor
~DiaGraph() {
for (int i = 0; i < N; i++)
delete[] head[i];
delete[] head;
}
};
// print all adjacent vertices of given vertex
void display_AdjList(adjNode* ptr, int i)
{
while (ptr != nullptr) {
cout << "(" << i << ", " << ptr->val
<< ", " << ptr->cost << ") ";
ptr = ptr->next;
}
cout << endl;
}
// graph implementation
int main()
{
// graph edges array.
graphEdge edges[] = {
// (x, y, w) -> edge from x to y with weight w
{0,1,2},{0,2,4},{1,4,3},{2,3,2},{3,1,4},{4,3,3}
};
int N = 6; // Number of vertices in the graph
// calculate number of edges
int n = sizeof(edges)/sizeof(edges[0]);
// construct graph
DiaGraph diagraph(edges, n, N);
// print adjacency list representation of graph
cout<<"Graph adjacency list "<for (int i = 0; i < N; i++)
{
// display adjacent vertices of vertex i
display_AdjList(diagraph.head[i], i);
}
return 0;
}