Find the degree of a particular vertex in a Graph

Approach

To find the degree of a vertex, find how many edges are going through the vertex.

The Graph is represented by an adjacency matrix. An Adjacency matrix is a two-dimensional square matrix of Boolean values (that is, 0 and 1). The graph's vertices are the row[i] and column[j]. In an adjacency matrix adj[i][j], 

        ✅ The value Zero represents the absence of an edge from vertex i to vertex j 

        ✅ The value One represents the presence of an edge from vertex i to vertex j. 

In the adjacency matrix, the row and column are the vertices. 

To solve the problem, create and initialize the variable degree with 0. For the input vertex (ver) value, iterate over the respective row in the adjacency matrix. For every, adj[ver][j] == 1, increase the degree value. 

Pseudo Code

Algorithm_find_degree(graph G, vertex v)
    Initialize degree = 0
    For i =0 to number of vertices: 
      If G[v][j] is equal to 1
      Increment degree
    If G[v][v] is equal to 1
      Increment degree
    Return degree

🧩 The user will input the adjacency matrix and the vertex whose degree is to be found. 

🧩 Initialize an int variable degree to zero. This variable will hold the degree of the input vertex.

🧩 Traverse the input vertex row of the adjacency matrix. If the cell value is equal to 1, then increment the value of degree.

🧩 Check for self-loop. If self-loop is present then increment degree.

🧩 Return the value of degree. 

Implementation in C++

// CPP program to find the degree of a vertex.
#include<iostream>
using namespace std;

// structure of a graph
struct graph
{
	// vertices
	int v; 

	// edges
	int e; 

	// direction from src to des
	int **dir;
};

// Returns degree of ver in the given graph
int findDegree(struct graph *G, int ver)
{
	// Traverse through the row of vertex ver and count the number of cells with value 1
	int degree = 0; 
	for (int i=0; i<G->v; i++){
		// if there is an edge increase the degree 
		if (G-> dir[ver][i] == 1)
		degree++; 
	}
	
	// check for self loop in graph
	if(G-> dir[ver][ver] == 1)
		degree++;
	return degree; 
}

struct graph *createGraph(int vertex,int edge)
{
	// G is a pointer of a graph
	struct graph *G = new graph;

	G->vertex = vertex;
	G->edge = edge;

	// allocate memory
	G->dir = new int*[vertex];

	for (int i = 0;i < vertex;i++)
	G->dir[i] = new int[vertex];

    G->dir[0][1] = 1; 
    G->dir[0][4] = 1;
    
    G->dir[1][0] = 1;
    G->dir[1][2] = 1;
    G->dir[1][3] = 1;
    G->dir[1][4] = 1;
    
    G->dir[2][1] = 1;
    G->dir[2][3] = 1;
    
    G->dir[3][1] = 1;
    G->dir[3][2] = 1;
    G->dir[3][4] = 1 ;
    
    G->dir[4][0] = 1 ;
    G->dir[4][1] = 1;
    G->dir[4][3] = 1;
    
     return G;

}

int main()
{

	int vertices = 5;
	int edges = 7;
	// call function to create a graph
	struct graph *G = createGraph(vertices, edges);

	//input vertex
	int ver = 1;

	// call function for finding the degree of the vertex 
	int degree = findDegree(G, ver);
	cout << degree << "\n";
	return 0;
}

You can also try this code with Online C++ Compiler

Run Code

Implementation in Java

import java.util.*;
import java.lang.*;
import java.io.*;

// Java program to find degree of a vertex.
class Graph_degree
{
	//Structure of Graph
	static class Graph
	{
		// vertices and edges
		int v, e;
		int[][] dir;

		//Graph Constructor
		Graph(int v, int e) {
			this.v = v;
			this.e = e;
			dir = new int[v][];
			for (int i = 0; i < v; i++)
			dir[i] = new int[v];
		}
	}
	static Graph createGraph(int v, int e)
	{
		Graph G = new Graph(v, e);

		// creating an adjacency matrix in which if there exists an edge between the vertices the value of G.dir[i][j] should be 1.
    	G.dir[0][1] = 1; 
    	G.dir[0][4] = 1;
    	
    	G.dir[1][0] = 1;
    	G.dir[1][2] = 1;
    	G.dir[1][3] = 1;
    	G.dir[1][4] = 1;
    	
    	G.dir[2][1] = 1;
    	G.dir[2][3] = 1;
    	
    	G.dir[3][1] = 1;
    	G.dir[3][2] = 1;
    	G.dir[3][4] = 1 ;
    	
    	G.dir[4][0] = 1 ;
    	G.dir[4][1] = 1;
    	G.dir[4][3] = 1;

		return G;
	}

	static int findDegree(Graph G, int ver)
	{
		int degree = 0;
		// if the G[ver][i] is one i.e. of there exists an edge between i and j increment the degree
		for (int i = 0; i < G.v; i++) {
			if (G.dir[ver][i] == 1)
			degree++;
		}

		// check for self loop in graph
		if(G.dir[ver][ver] == 1) degree++;
			return degree;
	}

	public static void main(String[] args)
	{
		int vertices = 5;
		int edges = 7;

		// Create a Graph
		Graph G = createGraph(vertices, edges);

		// input vertex for which we want to find the degree
		int ver = 1;

		// call function to find the degree of the vertex
		int degree = findDegree(G, ver);
		System.out.println(degree);
	}
}

You can also try this code with Online Java Compiler

Run Code

Implementation in Python

# Python3 program to find degree of a vertex.
# Structure of Graph
class Graph:

	# vertices and edges
	v = None
	e = None
	direction = []

	# Graph Constructor
	def __init__(self, v, e):
	self.v = v
	self.e = e
	self.direction = [[0 for i in range(v)]
					for j in range(v)]


def createGraph(v, e):
	G = Graph(v, e)

	G.direction[0][1] = 1
	G.direction[0][4] = 1

	G.direction[1][0] = 1
	G.direction[1][2] = 1
	G.direction[1][3] = 1
	G.direction[1][4] = 1

	G.direction[2][1] = 1
	G.direction[2][3] = 1

	G.direction[3][1] = 1
	G.direction[3][2] = 1
	G.direction[3][4] = 1

	G.direction[4][0] = 1
	G.direction[4][1] = 1
    G.direction[4][3] = 1
    	
	return G


def findDegree(G, ver):
	degree = 0
	for i in range(G.v):
	if G.direction[ver][i] == 1:
	degree += 1
	if G.direction[ver][ver] == 1:
	degree += 1
	return degree


# Driver Code
if __name__ == "__main__":

	vertices = 5
	edges = 7

	# Creating a Graph
	G = createGraph(vertices, edges)

	ver = 0

	# Function calling
	degree = findDegree(G, ver)
	print(degree)

You can also try this code with Online Python Compiler

Run Code

Output: 

4

Time Complexity Analysis

For ‘v’ vertices in the Graph, we will traverse through all the vertices once, so the Time complexity is O(v), where ‘v’ is the number of vertices. 

Space Complexity Analysis

A two-dimensional square adjacency matrix is used, hence the space required will be O(v^2), where v is the number of vertices in the graph. 

Frequently Asked Questions

What is a Graph?

A Graph is a set of points called vertices, connected by edges. The vertices represent the data to be stored and the edges are the relationships between the vertices. 

What is Degree of a vertex in a Graph? 

Degree of a vertex is the number of edges coming out of the vertex. 

What is an Adjacency Matrix? 

An adjacency matrix is a square two dimensional boolean matrix such that for adjacency matrix adj[][] if adj[i][j] is equal to one, there exists an edge between the vertex i and j. 

Conclusion

Congratulations on finishing this article. In this article, we discussed the implementation code of how to find the degree of a vertex in a Graph. We started by discussing about graph, then discussed about the degree of a vertex and finally discussed about the pseudo code and the code in C++, Java and Python programming languages. 

If you liked this article and want to learn more, please read some of our articles 

🔥 Cycle Detection in Undirected Graph

🔥 BFS in Graph

🔥 DFS traversal

🔥 M-coloring Problem

🔥 Ternary Operator in C

Head to the Guided Path on the Coding Ninjas Studio and upskill in Data Structures and Algorithms, Competitive Programming, System Design, and many more courses.

If you want to Practice top Coding Problems, attempt mock tests, or read interview experiences, head to the Coding Ninjas Studio, our practice platform.

We wish you Good Luck!🎈 Please upvote our blog and help other ninjas grow.