Need Help with an algorithm-graph
CodeGuru Home VC++ / MFC / C++ .NET / C# Visual Basic VB Forums Developer.com
Results 1 to 6 of 6

Thread: Need Help with an algorithm-graph

  1. #1
    Join Date
    Nov 2011
    Posts
    3

    Need Help with an algorithm-graph

    Hello. I have an assignment to do on graphs and I'm a little confused. Basically i have to examine if a directed graph is a star graph or a ring graph and print both of them with an adjacency list and an adjacency matrix. Also i have to find which is the worst case of complexity for these algorithms.
    Can anyone help me?
    Thanks in advance!

  2. #2
    Lindley is offline Elite Member Power Poster
    Join Date
    Oct 2007
    Location
    Fairfax, VA
    Posts
    10,885

    Re: Need Help with an algorithm-graph

    Any connected graph with an equal number of vertices and edges must be a ring graph. (If it isn't connected, it must be a collection of disjoint ring graphs.)

    You can test for connectedness and ringness simultaneously with a depth-first-search, aborting if you ever encounter a vertex with other than 2 edges before you return to the original vertex. If you traversed all the vertices, you have a ring graph.

    Star graphs are even easier. Assuming no self-edges, just check whether or not every vertex except one has 1 edge, and the last has n-1 edges.

  3. #3
    Join Date
    Nov 2011
    Posts
    3

    Re: Need Help with an algorithm-graph

    Thanks a lot for the help.Another thing,can this program be made in C? and if yes, i need to use arrays, right?

  4. #4
    Join Date
    Apr 1999
    Posts
    27,418

    Re: Need Help with an algorithm-graph

    Quote Originally Posted by Dominus_Mors View Post
    Thanks a lot for the help.Another thing,can this program be made in C?
    Why do you think it can't be made in 'C'? Some of the most sophisticiated pieces of software have been built using 'C'
    i need to use arrays, right?
    There is no "need" to use arrays in any program you create. Whether arrays makes it easier, that is another story.

    Regards,

    Paul McKenzie

  5. #5
    Join Date
    Nov 2011
    Posts
    3

    Re: Need Help with an algorithm-graph

    BY asking i mean if this is easy to be made in C. And yes you're right C is one of the best languages after assembly. and the array thing you need to make efficient programs,with any means necessary! By the way,thanks.

  6. #6
    Lindley is offline Elite Member Power Poster
    Join Date
    Oct 2007
    Location
    Fairfax, VA
    Posts
    10,885

    Re: Need Help with an algorithm-graph

    Just about any programming language will be able to do graph algorithms fairly easily. The efficiency will be determined much more by the choice of algorithm than by the language. The most difficult part will be deciding what data structure you will use to store the graph.

Tags for this Thread

Posting Permissions

  • You may not post new threads
  • You may not post replies
  • You may not post attachments
  • You may not edit your posts
  •  


Azure Activities Information Page

Windows Mobile Development Center


Click Here to Expand Forum to Full Width

This is a CodeGuru survey question.


Featured


HTML5 Development Center