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

# Thread: Need Help with an algorithm-graph

1. Junior Member
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. Elite Member Power Poster
Join Date
Oct 2007
Location
Seattle, WA
Posts
10,895

## 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. Junior Member
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. Elite Member Power Poster
Join Date
Apr 1999
Posts
27,449

## Re: Need Help with an algorithm-graph

Originally Posted by Dominus_Mors
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. Junior Member
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. Elite Member Power Poster
Join Date
Oct 2007
Location
Seattle, WA
Posts
10,895

## 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.

#### Posting Permissions

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

Click Here to Expand Forum to Full Width

On-Demand Webinars (sponsored)