Ma’ruza 12. Graflarni tasvirlash

Ma’ruza 12.
Graflarni tasvirlash.
Graflarni kompyuterda tasvirlash uchun bir qancha usullar mavjud:

• 
  Qo'shnilik matritsasi;
  
• 
  Hodisa matritsasi;
  
• 
  Qo'shnilik ro'yxati;
  
• 
  Qirralar ro'yxati.
  

Grafni qo'shnilik matritsa orqali tasvirlash.
Grafni qo'shnilik matritsa nuqtai nazaridan tasvirlash uchun quyidagi sinfdan foydalanish mumkin:
class GraphAdj
{
public int n; // uchlar soni
public int m; // qirralar soni
public int [,] Adj; //qo’shnilik matritsasi
public GraphAdj() { }
public GraphAdj(int n1,int m1,int [,]a)
{
n = n1;
m = m1;
int u, v;
Adj = new int[n, n];
for (int i = 0; i < m; i++)
{
v = a[i, 0]; u=a[i,1];
Adj[v,u] = Adj[u,v] = 1; //n-graf uchun
// Adj[v,u] =1; Adj[u,v] = -1; //orgraf uchun
}
}

public void Print()

{
Console.WriteLine("Grafning qo’shnilik matritsasi:");
for (int i = 0; i < n; i++)
{
Console.WriteLine();
for (int j = 0; j < n; j++)
Console.Write($" {Adj[i, j]}");
Console.WriteLine();
}
}
}

Ushbu sinfda konstruktorda grafning qo'shnilik matritsasi shakllantiriladi, bu erda uchlar soni, qirralarning soni va uchlarning boshlang'ich va oxirgi indekslari bilan qirralarning ro'yxatini o'z ichiga olgan massiv parametr sifatida uzatiladi.

Matritsani ekranda ko'rsatish uchun Print() usuli qo'llaniladi.
Agar graf zich bo'lsa, u holda graflarni qo'shni matritsalar orqali tasvirlash qulay hisoblanadi. Matritsa O(V²) xotira birliklarini talab qiladi va ishga tushirish vaqti O(V²). Agar qirralarning soni V² ga proporsional bo’lsa, u holda qirralarning uchlarini o'qish uchun O(V²) vaqt kerak bo'ladi. Agar araf siyrak bo'lsa, matritsani ishga tushirish qirra uchlarini kiritish vaqtida ustunlik qiladi.