Степені вершин (Розбір)

Объявімо лінійний масив $deg$. У комірці $deg[i]$ будемо зберігати ступінь вершини $i$, яка дорівнює кількості одиниць у $i$-му рядку матриці суміжності.

У неорієнтованому графі кожне ребро враховується двічі: якщо $m$ — матриця суміжності та між вершинами $i$ та $j$ є ребро, то m[i][j] = m[j][i] = 1). Для кожного ребра $(i,j)$ збільшуємо $deg[i]$ на $1$ (коли зустрінеться ребро $(j,i)$, то deg[j] збільшиться на $1$).

Приклад

Граф, наведений у прикладі, має наступний вигляд:

Реалізація алгоритму

Объявімо масив $deg$ для зберігання ступенів вершин.

#define MAX 101
int deg[MAX];

Читаємо кількість вершин графа $n$. Ініціалізуємо масив $deg$.

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

Читаємо матрицю суміжності.

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

Якщо в графі є ребро між вершинами $i$ і $j$ (значення $value$ дорівнює $1$), збільшуємо $deg[i]$ на одиницю.

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

Виводимо ступені всіх вершин графа.

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

Java реалізація

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 реалізація

Читаємо кількість вершин графа $n$.

n = int(input())

Ініціалізуємо матрицю суміжності $g$ та список ступенів вершин $deg$.

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

Читаємо матрицю суміжності.

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

Виконуємо обчислення ступенів вершин графа. Ступінь вершини $i$ дорівнює сумі елементів $i$-го рядка матриці суміжності $g$.

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

Виводимо ступені всіх вершин графа.

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