Ma’ruza 12. Graflarni tasvirlash

Hodisa matritsasi orqali grafni tasvirlash.
Grafni hodisa matritsasi nuqtai nazaridan tasvirlash uchun quyidagi sinfdan foydalanish mumkin:
class GraphInc
{
public int n; // uchlar soni
public int m; // qirralar soni
public int[,] Inc; //qo’shnilik matritsasi
public GraphInc() { }
public GraphInc(int n1, int m1, int[,] a)
{
n = n1;
m = m1;
int u, v;
Inc = new int[n, m];
for (int i = 0; i < m; i++)
{
v = a[i, 0]; u = a[i, 1];
Inc[v , i] =Inc[u , i] = 1; //n -graf uchun
// Inc[v,i] =1; Inc[u,i]] =- 1; //orgraf uchun
}
}
public void Print()
{
Console.WriteLine("Grafni hodisa matritsasi:");
for (int i = 0; i < n; i++)
{
Console.WriteLine();
for (int j = 0; j < m; j++)\
Console.Write($" {Inc[i, j]}");
Console.WriteLine();
}
}
}
Grafni qo‘shnilik ro‘yxati orqali tasvirlash
Bu tasvirlashda v uch bilan bog‘langan barcha uchlar shu uch uchun qo‘shnilik ro‘yxatida keltiriladi. Ro'yxat bog'langan ro'yxatlar yordamida osongina amalga oshirilishi mumkin. Bu shuni anglatadiki, har bir v uch uchun biz bog'langan ro'yxatni yaratamiz va ro'yxatning tugunlari v ga qo'shni bo'lgan v va boshqa uchlar orasidagi bog'lanishlarni ifodalaydi.
Bog'langan ro'yxatlarning umumiy soni grafdagi uchlar soniga teng bo’ladi.
Quyida keltirilgan graf uchun qo'shnilik ro'yxatiga misol:


Qo’shnilik ro’yxati orqali graf quyidagicha e'lon qilinishi mumkin:
// qo’shnikik matritsasi bitta elementini tuzilmasi
class NodeAdj
{
public int num;// uch raqami
public int ves;// vaznlangan graf uchun
public NodeAdj next;// keyingi uch uchun ko’rsatkich
}
// qo’shnilik matritsasi orqali grafning tasvirlanishi
class GraphAdjList
{
public int n; // uchlar soni
public int m; // qirralar soni
public NodeAdj [] Adj; //qo’shnilikning dinamik ro’yxati
public GraphAdjList() { }
public GraphAdjList(int n1, int m1, int[,] a)
{
n = n1;
m = m1;
Adj = new NodeAdj[n];
int u, v;
for (int i = 0; i < n; i++)
{
Adj[i] = new NodeAdj();
Adj[i].num = i;
}
for (int i = 0; i < m; i++)
{
v = a[i, 0]; u = a[i, 1];
var tmp = new NodeAdj();
tmp.num = v;
if (Adj[u].next != null) tmp.next = Adj[u].next;
Adj[u].next = tmp;
tmp = new NodeAdj();
tmp.num = u;
if (Adj[v].next != null) tmp.next = Adj[v].next;
Adj[v].next = tmp;
}
}
public void Print()
{
Console.WriteLine("Grafning qo’shnilik matritsasi:");
for (int i = 0; i < n; i++)
{
Console.WriteLine();
NodeAdj tmp = Adj[i];
while (tmp != null)
{
Console.Write($" {tmp.num}");
tmp = tmp.next;
}
Console.WriteLine();
}
}
}