Undirected graph -- computing the degree of a node in compressed storage

Undirected graph —— Computing the degree of a node in compressed storage

• Problem description

Yes n An undirected graph with nodes , Use adjacency storage as the storage structure , To reduce storage space , Use the array to save only the lower triangular matrix in the way of row master mapping , Please give the mapping formula , And write an algorithm to calculate the degree of a given node .

• Algorithmic thought
  The given adjacency matrix is shown in the figure , If you use an array to compress a storage matrix , And only the lower triangle part is stored , Then the formula stored in the element is as follows

As shown in the figure ：

So the element aij The subscript of in the array is （i-1)(i-2)/2+j-1
i-2: Altogether i-2 term
i-1: First and last
（i-1)(i-2)/2： The first i The number of all line elements before the line
j-1:aij The first i The number of elements in front of the row and column

Algorithm description ： Because after compressed storage ,aij The information of upper triangle degree will be lost , Therefore, the degree of nodes can only be calculated by its in degree and the out degree of its lower triangular part .
How to calculate ：
1） First consider the second i Out of line , Just calculate according to the formula j Element number and number j The storage subscript of the row element , And judge whether it is 1, To make statistics, there are ：

	for(j=1;j<i;j++){
    
		k=(i-1)*(i-2)/2+j-1;
		if(a[k]==1) count++;
	} 

2） Consider penetration ： Consider the j The elements of the column , Also calculate the subscript , Judge whether it is 1 that will do .

for(j=n;j>i;j--){
    
		k=(j-1)*(j-2)/2+i-1;
		if(a[k]==1) {
    
			count++;		
		}
	}

• Algorithm implementation

#include<stdio.h> 

int CountD(int a[],int n,int key){
    
	if(n==0) return 0;
	int i=key,j,count=0,k;
	for(j=n;j>i;j--){
    
		k=(j-1)*(j-2)/2+i-1;
		if(a[k]==1) {
    
			count++;		
		}
	}
	for(j=1;j<i;j++){
    
		k=(i-1)*(i-2)/2+j-1;
		if(a[k]==1) count++;
	} 
	return count;
}
int main(){
    
	int a[]={
    1,
	 		 1,0,
			 0,1,1,
			 1,1,0,1};
	int c=CountD(a,5,3);//5 Stage serial number is 3 The degree of node  
	printf("%d",c);
	
}