1. Not finding help here? Sign up for a free 30min tutor trial with Chegg Tutors
    Dismiss Notice
Dismiss Notice
Join Physics Forums Today!
The friendliest, high quality science and math community on the planet! Everyone who loves science is here!

C - Degree of a directed unweighted graph

  1. Jul 18, 2016 #1
    1. The problem statement, all variables and given/known data
    Given the representation of directed unweighted graph:
    Code (Text):

    typedef struct
    {
      int n;//num. of vertices
      void *info[MAX];//information of vertices
      int am[MAX][MAX];//adjacency matrix
    }GRAPH;
     
    Write a function
    Code (Text):
    int minDegree(GRAPH*);
    and
    Code (Text):
    int maxDegree(GRAPH*);
    that return the smallest and the largest degree of given graph.
    Write a function with variable number of arguments
    Code (Text):
    GRAPH *f_min(int n,...);
    by using the function minDegree() that returns the address of a graph with the smallest degree.
    Write a function with variable number of arguments
    Code (Text):
    GRAPH *f_max(int n,...);
    by using the function maxDegree() that returns the address of a graph with the largest degree.
    n is the number of input graphs.

    2. The attempt at a solution
    Maximum (minimum) degree of a directed graph is the total number of in-degree and out-degree edges of a vertex that has the largest (smallest) number of edges, with loops counted twice.

    So, the algorithm form finding the minimum and maximum degree of a directed graph is to:
    1. for each vertex, count the number of connecting edges, and if an edge is a loop, then multiply by two.
    2. return the smallest and the largest count.

    Could someone please suggest some code, because I am really stuck in implementation of this program?
     
  2. jcsd
  3. Jul 18, 2016 #2

    Mark44

    Staff: Mentor

    You need to take a stab at it first. You could start by fleshing out your algorithm a bit. A GRAPH structure contains information about the number of vertices, so how might you cycle through the vertices?

    For a given vertex, how can you use the adjacency matrix to find out which other vertices are connected to that vertex?

    To help you get a handle on this problem, it might be helpful to just make up a graph with, say five or so vertices connected in some way. Write the adjacency matrix for that graph, and go through the process manually of finding the degrees of the various paths.
     
Know someone interested in this topic? Share this thread via Reddit, Google+, Twitter, or Facebook

Have something to add?
Draft saved Draft deleted



Similar Discussions: C - Degree of a directed unweighted graph
  1. C\C++ help needed (Replies: 2)

  2. C++ . (Replies: 19)

Loading...