# Need Help with an algorithm-graph

• November 28th, 2011, 12:23 PM
Dominus_Mors
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?
• November 28th, 2011, 01:05 PM
Lindley
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.
• November 28th, 2011, 02:06 PM
Dominus_Mors
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?
• November 28th, 2011, 02:23 PM
Paul McKenzie
Re: Need Help with an algorithm-graph
Quote:

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'
Quote:

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
• November 28th, 2011, 02:42 PM
Dominus_Mors
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.
• November 28th, 2011, 03:37 PM
Lindley
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.