Zirvələrin dərəcələri (Həll təhlili)

Xətti massiv $deg$ təyin edək. $deg[i]$ gövdəsində, adjaçentlik matrisinin $i$-ci sətirindəki birliklərin sayı olan vertex $i$-nin dərəcəsi saxlanılır.

Yönsüz qrafda hər bir kənar iki dəfə nəzərə alınır: əgər $m$ adjaçentlik matrisidir və vertex $i$ və $j$ arasında kənar varsa, onda m[i][j] = m[j][i] = 1). Hər bir kənar üçün $(i,j)$, $deg[i]$ $1$ dəfə artırılır (kənar $(j,i)$ qarşılandıqda, deg[j] $1$ dəfə artacaq).

MisalQrafda verilmiş misal aşağıdakı kimidir:

Alqoritmin həyata keçirilməsi

Vertex dərəcələrinin saxlanması üçün $deg$ massivi təyin edək.

#define MAX 101
int deg[MAX];

Qrafın vertexlərinin sayını oxuyuruq $n$. Massivi $deg$ başlamış şəkildə təyin edirik.

scanf("%d",&n);
memset(deg,0,sizeof(deg));

Adjaçentlik matrisini oxuyuruq.

for(i = 0; i < n; i++)
for(j = 0; j < n; j++)
{

Qrafda $i$ və $j$ vertexləri arasında kənar varsa (dəyişənin $value$ dəyəri $1$-ə bərabərdirsə), $deg[i]$ bir artırılır.

  scanf("%d",&value);
  if (value == 1) deg[i]++;
}

Qrafın bütün vertexlərinin dərəcələrini çap edirik.

for(i = 0; i < n; i++)
  printf("%d\n",deg[i]);

Java həyata keçirilməsi

import java.util.*;

public class Main
{
  public static void main(String[] args)
  {
    Scanner con = new Scanner(System.in);

    int n = con.nextInt();
    int deg[] = new int[n];
    
    for(int i = 0; i < n; i++)
    for(int j = 0; j < n; j++)
    {
      int value = con.nextInt();
      if (value == 1) deg[i]++;
    }

    for(int i = 0; i < n; i++)
      System.out.println(deg[i]);      
    con.close();
  } 
} 

Python həyata keçirilməsi

Qrafın vertexlərinin sayını oxuyuruq $n$.

n = int(input())

Adjaçentlik matrisini $g$ və vertex dərəcələri siyahısını $deg$ başlamış şəkildə təyin edirik.

g = [[] for _ in range(n)]
deg = [0] * n

Adjaçentlik matrisini oxuyuruq.

for i in range(n):
  g[i] = list(map(int, input().split()))

Qrafın vertex dərəcələrini hesablayırıq. Vertex $i$-nin dərəcəsi $g$ matrisinin $i$-ci sətirinin elementlərinin cəminə bərabərdir.

for i in range(n):
  deg[i] = sum(g[i])

Qrafın bütün vertexlərinin dərəcələrini çap edirik.

for i in range(n):
  print(deg[i])