Ma’ruza 12. Graflarni tasvirlash

Grafni qirralarning roʻyxati orqali tasvirlash.
Ushbu tasvirlashda qirralar uchlar juftligi bilan sanab o'tiladi.
Grafni elementlari qirralar bo’lgan bir o'lchovli massiv sifatida ifodalash mumkin.
Bitta qirrani ifodalash uchun quyidagi strukturadan foydalanish mumkin.
// qirralarning ro'yxatining bir elementining tuzilishi
struct Edge
{
public int beg;// bo’shlanish uchi raqami
public int end;// oxirgi uchi raqami
public int ves; // vaznlangan graf uchun qirra vazni
}
Grafni qo'shnilik ro'yxat orqali ifodalash quyidagi keltirilgan:
//Qo’shnilik ro’yxati orqali graf tasviri
class GraphEdge
{
public int n; // uchlar soni
public int m; // qirralar soni
public Edge[] Edg; //qo’shnilikning dinamik ro’yxati
public GraphEdge() { }
public GraphEdge(int n1, int m1, int[,] a)
{
n = n1;
m = m1;
Edg = new Edge[m];
int u, v;
for (int i = 0; i < m; i++)
{
v = a[i, 0]; u = a[i, 1];
Edg[i].beg = v; Edg[i].end = u;
}
}
public void Print()
{
Console.WriteLine("Grafning qirralari ro’yxati:");
for (int i = 0; i < m; i++)
{
Console.WriteLine();
Console.WriteLine($"Qirra:{i}, Uchlari: {Edg[i].beg} {Edg[i].end}");
}
}
}
Roʻyxatdagi elementlarning umumiy soni grafdagi qirralar soniga tengdir.


Graflarni bir tasvirlash turidan boshqasiga o'tkazish.
Faraz qilaylik, bizda qirralarning ro'yxati bilan ifodalangan graf mavjud bo’lib, biz uni qo'shnilik matritsa bilan tasvirlanadigan grafga aylantiramiz.
void GraphEdgeToGraphAdj(GraphEdge GE,GraphAdj GMA)
{
int u, v;
GMA.n = GE.n; GMA.m = GE.m;
GMA.Adj = new int[GMA.n, GMA.n];
for (int i = 0; i < GE.m; i++)
{
v = GE.Edg[i].beg; u = GE.Edg[i].end;
GMA.Adj[v, u] = GMA.Adj[u, v] = 1; // n -graf uchun
// GMA.Adj[v,u] =1; GMA.Adj[u,v] = -1; //orgraf uchun
}
}

Quyida ushbu sinflardan foydalanish dasturi keltirilgan.

static void Main(string[] args)

{
Console.Write("Graf uchlar sonini kiriting:");
int n = int.Parse(Console.ReadLine());
Console.Write("Graf qirralari sonini kiriting:");
int m = int.Parse(Console.ReadLine());
int[,] vect = new int[m, 2];
for(int i = 0; i < m; i++)
{
Console.Write($" {i+1} qirraning birinchi uchi raqamini kiriting:");
vect[i,0] = int.Parse(Console.ReadLine());
Console.Write($"{i+1} qirraning ikkinchi uchi raqamini kiriting:");
vect[i, 1] = int.Parse(Console.ReadLine());
}
GraphAdj gAdj = new GraphAdj(n, m, vect);
gAdj.Print();
GraphInc gInc = new GraphInc(n, m, vect);
gInc.Print();
GraphAdjList gAdjList = new GraphAdjList(n, m, vect);
gAdjList.Print();
GraphEdge gEdge = new GraphEdge(n, m, vect);
gEdge.Print();
GraphAdj gAdj1 = new GraphAdj();
GraphEdgeToGraphAdj(gEdge, gAdj1);
gAdj1.Print();
Console.ReadKey();
}

Dasturni bajarish misoli: