Tutorialspoint.dev

Find the Degree of a Particular vertex in a Graph

Given a graph G(V,E) as an adjacency matrix representation and a vertex, find the degree of the vertex v in the graph.

Examples :

0-----1
|    |
|    |
|    |
2-----3
Input : ver = 0
Output : 3

Input : ver = 1
Output : 2



Algorithm:-

1. Create the graphs adjacency matrix from src to des 
2. For the given vertex then check if 
   a path from this vertices to other exists then
   increment the degree.
3. Return degree 

Below is the implementation of the approach.

C++

// CPP program to find 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 given graph
int findDegree(struct graph *G, int ver)
{    
    // Traverse through row of ver and count
    // all connected cells (with value 1)
    int degree = 0;         
    for (int i=0; i<G->v; i++)     
  
        // if src to des is 1 the degree count
        if (G-> dir[ver][i] == 1) 
            degree++;             
      
    return degree;         
}
  
struct graph *createGraph(int v,int e)
{   
    // G is a pointer of a graph
    struct graph *G = new graph; 
      
    G->v = v;
    G->e = e;
      
    // allocate memory
    G->dir = new int*[v];
      
    for (int i = 0;i < v;i++)
        G->dir[i] = new int[v];
      
    /*  0-----1
        |    |
        |    |
        |   |
        2-----3     */
      
      
    //direction from 0
    G->dir[0][1]=1;
    G->dir[0][2]=1;
    G->dir[0][3]=1;
      
    //direction from 1
    G->dir[1][0]=1;
    G->dir[1][3]=1;
      
    //direction from 2
    G->dir[2][0]=1;
    G->dir[2][3]=1;
      
    //direction from 3
    G->dir[3][0]=1;
    G->dir[3][1]=1;
    G->dir[3][2]=1;
      
    return G;
      
}
  
// Driver code
int main()
{
    int vertices = 4;
    int edges = 5;
    struct graph *G = createGraph(vertices, edges);
      
    // loc is find the degree of 
    // particular vertex
    int ver = 0; 
      
    int degree = findDegree(G, ver);
    cout << degree << " ";
    return 0;
}

Java

// Java program to find degree of a vertex.
  
class DegreeOfVertex 
{
    //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);
  
     /* 0-----1
        |    |
        |    |
        |   |
        2-----3 */
  
        //direction from 0
        G.dir[0][1] = 1;
        G.dir[0][2] = 1;
        G.dir[0][3] = 1;
  
        //direction from 1
        G.dir[1][0] = 1;
        G.dir[1][3] = 1;
  
        //direction from 2
        G.dir[2][0] = 1;
        G.dir[2][3] = 1;
  
        //direction from 3
        G.dir[3][0] = 1;
        G.dir[3][1] = 1;
        G.dir[3][2] = 1;
  
        return G;
    }
  
    static int findDegree(Graph G, int ver) 
    {
        int degree = 0;
        for (int i = 0; i < G.v; i++) {
            if (G.dir[ver][i] == 1)
                degree++;
        }
        return degree;
    }
  
    // Driver code
    public static void main(String[] args)
    {
        int vertices = 4;
        int edges = 5;
          
        // Creating a Graph
        Graph G = createGraph(vertices, edges);
          
        int ver = 0;
          
        // Function calling
        int degree = findDegree(G, ver);
        System.out.println(degree);
    }
}


Output:

3

// This code is contributed by rishabhdeepsingh98



This article is attributed to GeeksforGeeks.org

leave a comment

code

0 Comments

load comments

Subscribe to Our Newsletter